1122: 划分

Memory Limit:1024 MB Time Limit:10.000 S
Judge Style:Text Compare Creator:
Submit:15 Solved:8

Description

Input

Output

输出一行一个整数,表示答案。

HINT

5 0
5 1 7 9 9

247

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 \leq 7 \leq 9 \leq 95+1799 知该方案合法。

答案为 (5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247(5+1)2+72+92+92=247

虽然划分方案 \{5\}, \{1\}, \{7\}, \{9\}, \{9\}{5},{1},{7},{9},{9} 对应的运行时间比 247247 小,但它不是一组合法方案,因为 5 \gt 15>1

虽然划分方案 \{5\}, \{1,7\}, \{9\}, \{9\}{5},{1,7},{9},{9} 合法,但该方案对应的运行时间为 251251,比 247247 大。

【样例 2 解释】

最优的划分方案为 \{5\}, \{6\}, \{7\}, \{7\}, \{4,6,2\}, \{13\}, \{19,9\}{5},{6},{7},{7},{4,6,2},{13},{19,9}