分数: 650 点
问题陈述
给你两个整数序列 A 和 B 长度 N。对于 k = 1, 2, \ldots, N,解决以下问题:
- 考虑选择 k 之间的不同整数 1 和 N,包括在内。让 S 是所选整数的集合。找到最大值 \displaystyle (\sum_{i \in S} A_i) - \max_{i \in S} B_i.
约束
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- -2 \times 10^{14} \leq B_i \leq 2 \times 10^{14}
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
打印 N 行。的 i- 第行应包含问题的答案 k=i.
样本输入 1
3 4 1 5 6 3 2
示例输出 1
3 5 6
以下选择是最佳选择。
- k = 1: S = \{1\}
- k = 2: S = \{1, 3\}
- k = 3: S = \{1, 2, 3\}
示例输入 2
2 0 1 0 1
示例输出 2
-1 -1
示例输入 3
6 9 7 2 4 7 1 -1000 0 3 4 8 5
示例输出 3
6 10 17 20 22 -978