2048 年,第三十届 CSP 认证的考场上,作为选手的小明打开了第一题。
这个题的样例有 n 组数据,数据从 1∼n 编号,i 号数据的规模为 ai。
小明对该题设计出了一个暴力程序,对于一组规模为 u 的数据,该程序的运行时间为 u2。
然而这个程序运行完一组规模为 u 的数据之后,它将在任何一组规模小于 u 的数据上运行错误。
样例中的 ai 不一定递增,但小明又想在不修改程序的情况下正确运行样例,于是小明决定使用一种非常原始的解决方案:
将所有数据划分成若干个数据段,段内数据编号连续,接着将同一段内的数据合并成新数据,其规模等于段内原数据的规模之和,小明将让新数据的规模能够递增。
小明觉得这个问题非常有趣,并向你请教:
给定 n 和 ai,请你求出最优划分方案下,小明的程序的最小运行时间。
由于官方时间限制太紧张,我们将时限从2s提高到4s。
由于本题的数据范围较大,部分测试点的 ai 将在程序内生成。
第一行两个整数 n,type。nn 的意义见题目描述,type 表示输入方式。
对于type=1 的 23∼25 号测试点,ai 的生成方式如下:
给定整数 x,y,z,b1,b2,m,以及 m 个三元组 (pi,li,ri)。
输出一行一个整数,表示答案。
5 0
5 1 7 9 9
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 输入】
10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234
【样例 3 输出】
4972194419293431240859891640