1443: 划分（partition）（2019 CCF CSP-S2 day2）
时间限制: 2 Sec 内存限制: 1024 MB提交: 2 解决: 0
[提交] [状态] [讨论版] [命题人:]
题目描述
输入
输出
一行一个整数，表示答案。
样例输入 Copy
5 0
5 1 7 9 9
样例输出 Copy
247
提示
【样例1解释】
最优的划分方案为{5,1},{7},{9},{9}。由5+1≤7≤9≤9知该方案合法。
答案为(5+1)2+72+92+92=247。
虽然划分方案{5},{1},{7},{9},{9}对应的运行时间比247小，但它不是一组合法方案，因为5>1。
虽然划分方案{5},{1,7},{9},{9}合法，但该方案对应的运行时间为251，比247大。
【样例2输入】
10 0
5 6 7 7 4 6 2 13 19 9
【样例2输出】
1256
【样例2解释】
最优的划分方案为{5},{6},{7},{7},{4,6,2},{13},{19,9}。
【样例3输入】 最优的划分方案为{5,1},{7},{9},{9}。由5+1≤7≤9≤9知该方案合法。
答案为(5+1)2+72+92+92=247。
虽然划分方案{5},{1},{7},{9},{9}对应的运行时间比247小，但它不是一组合法方案，因为5>1。
虽然划分方案{5},{1,7},{9},{9}合法，但该方案对应的运行时间为251，比247大。
【样例2输入】
10 0
5 6 7 7 4 6 2 13 19 9
【样例2输出】
1256
【样例2解释】
最优的划分方案为{5},{6},{7},{7},{4,6,2},{13},{19,9}。
10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234
【样例3输出】
4972194419293431240859891640
【样例4】
见选手目录下的partition/partition4.in 与partition/partition4.ans。
【样例5】
见选手目录下的partition/partition5.in 与partition/partition5.ans。
【数据范围】
|
测试点编号 |
n≤ |
ai≤ |
type= |
|
1∼3 |
10 |
10 |
0 |
|
4∼6 |
50 |
103 |
|
|
7∼9 |
400 |
104 |
|
|
10∼16 |
5000 |
105 |
|
|
17∼22 |
5×105 |
106 |
|
|
23∼25 |
4×107 |
109 |
1 |
1≤li≤ri≤109,0≤x,y,z,b1,b2<230。