Home => ProblemSet => 100.2019-05:划分
1794: 100.2019-05:划分
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
Input
Output
输出一行一个整数，表示答案。
Sample Input Copy
5 0
5 1 7 9 9
Sample Output Copy
247
HINT
样例二：
输入：
10 0
5 6 7 7 4 6 2 13 19 9
输出：
1256
样例三：
输入：
10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234
输出：
4972194419293431240859891640
【样例 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 解释】
最优的划分方案为
{5},{6},{7},{7},{4,6,2},{13},{19,9}。
输入：
10 0
5 6 7 7 4 6 2 13 19 9
输出：
1256
样例三：
输入：
10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234
输出：
4972194419293431240859891640
【样例 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 解释】
最优的划分方案为
{5},{6},{7},{7},{4,6,2},{13},{19,9}。