102405: [AtCoder]ABC240 F - Sum Sum Max
Description
Score : $500$ points
Problem Statement
There are integer sequences $A, B, C$ of length $M$ each.
$C$ is represented by integers $x_1, \dots, x_N, y_1, \dots, y_N$. The first $y_1$ terms of $C$ are $x_1$, the subsequent $y_2$ terms are $x_2$, $\ldots$, the last $y_N$ terms are $x_N$.
$B$ is defined by $B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M)$.
$A$ is defined by $A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M)$.
Find the maximum value among $A_1, \dots, A_M$.
You will be given $T$ test cases to solve.
Constraints
- $1 \leq T \leq 2 \times 10^5$
- $1 \leq N \leq 2 \times 10^5$
- The sum of $N$ in a single file is at most $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$
Each case is in the following format:
$N$ $M$ $x_1$ $y_1$ $\vdots$ $x_N$ $y_N$
Output
Print $T$ lines. The $i$-th line $(1 \leq i \leq T)$ should contain the answer to the $i$-th test case.
Sample Input 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
Sample Output 1
4 53910 2000000002000000000
In the first test case, we have:
- $C = (-1, -1, 2, 2, 2, -3, -3)$
- $B = (-1, -2, 0, 2, 4, 1, -2)$
- $A = (-1, -3, -3, -1, 3, 4, 2)$
Thus, the maximum value among $A_1, \dots, A_M$ is $4$.
Input
题意翻译
## 题目描述 有三个数列 $A,B,C$。 其中 $C$ 表示为 $ x_1,\ \dots,\ x_N,\ y_1,\ \dots,\ y_N $ 的形式,意思是前 $y_1$ 个数为 $x_1$,之后 $y_2$ 个数为 $x_2$……最后 $y_N$ 个数为 $x_N$。 $B$ 为 $C$ 的前缀和数组。 $A$ 为 $B$ 的前缀和数组。 求 $A$ 中最大值。 ## 输入格式 对于每组数据, 第一行为两个数 $N$ 和 $M$, 第 $2$ 至 $N+1$ 行,第 $i$ 行为两个数 $x_{i-1}$ 和 $y_{i-1}$。 ## 输出格式 对于每组数据,输出一行一个整数表示答案 ## 样例 #1 ### 样例输入 #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 ``` ## 提示 ### 数据范围 - $ 1\ \leq\ T\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ \sum\ N\ \leq\ 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 $Output
问题描述
存在长度为$M$的整数序列$A, B, C$。
$C$由整数$x_1, \dots, x_N, y_1, \dots, y_N$表示。$C$的前$y_1$项为$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$中的最大值为$4$。