分数: 500 点
问题陈述
有整数序列 A, B, C 长度 M 每个。
C 用整数表示 x_1, \dots, x_N, y_1, \dots, y_N。第一个 y_1 条款 C 是 x_1,后续 y_2 条款是 x_2, \ldots,最后一个 y_N 条款是 x_N.
B 定义为 B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).
A 定义为 A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).
找出其中的最大值 A_1, \dots, A_M.
你将得到 T 测试用例解决。 单个文件中的
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- 总和 N 最多 2 \times 10^5.
- 1 \leq M \leq 10^9
- |x_i| \leq 4 \, (1 \leq i \leq N)
- y_i \gt 0 \, (1 \leq i \leq N)
- \sum_{k = 1}^N y_k = M
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例的格式如下:
N M x_1 y_1 \vdots x_N y_N
输出
打印 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 7 -1 2 2 3 -3 2 10 472 -4 12 1 29 2 77 -1 86 0 51 3 81 3 17 -2 31 -4 65 4 23 1 1000000000 4 1000000000
示例输出 1
4 53910 2000000002000000000
在第一个测试用例中,我们有:
- C = (-1, -1, 2, 2, 2, -3, -3)
- B = (-1, -2, 0, 2, 4, 1, -2)
- A = (-1, -3, -3, -1, 3, 4, 2)
因此,其中的最大值 A_1, \dots, A_M is 4.