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+1≤7≤9≤9 知该方案合法。
答案为 (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}。