[CSP-S 2019] 划分
题目描述
小明的程序处理规模为 u 的数据需要 u2 的时间,而且只能按照规模非递减的顺序处理各组数据。现有 n 组数据,第 i 组的规模为 ai。
将数据按原有顺序划分成若干非空连续段,每段合并成一组新数据。若分界点为 0=k0<k1<⋯<kq=n,第 j 组新数据的规模为
sj=i=kj−1+1∑kjai.
要求 s1≤s2≤⋯≤sq。可以把全部数据合并成一组。求运行时间 ∑j=1qsj2 的最小值。
输入格式
第一行两个整数 n,type,分别表示原数据组数和输入方式。
- type=0 时,第二行直接给出 n 个整数 ai。
- type=1 时,第二行给出 x,y,z,b1,b2,m,接下来 m 行依次给出三元组 (pj,lj,rj)。
当 type=1 时,给定 b1,b2,对 3≤i≤n 依次生成
bi=(xbi−1+ybi−2+z)mod230.
其中 0=p0<p1<⋯<pm=n。当 pj−1<i≤pj 时,令
ai=(bimod(rj−lj+1))+lj.
输出格式
输出一行一个整数,表示最小运行时间。
样例 1
5 0
5 1 7 9 9
247
一种最优划分是 {5,1},{7},{9},{9},代价为 62+72+92+92=247。每个数单独成段时,前两个段和为 5,1,违反非递减条件。划分为 {5},{1,7},{9},{9} 的代价为 251。
样例 2
10 0
5 6 7 7 4 6 2 13 19 9
1256
一种最优划分是 {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
4972194419293431240859891640
样例 4 与 5
原赛选手附件中的文件分别是 partition/partition4.in、partition/partition4.ans,以及 partition/partition5.in、partition/partition5.ans。
数据范围
原赛题面规定 2≤n≤4×107,1≤ai≤109,type∈{0,1}。本地评测的直接输入另有 n=1 的测点。
生成数据时,1≤m≤105,1≤lj≤rj≤109,0≤x,y,z,b1,b2<230。
本地版本中,type=0 的答案不超过 4×1018。
| 原赛测试点 |
n 上限 |
ai 上限 |
type |
| 1–3 |
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 |