← 返回题目列表

AtCoder · abc348_g

G. 最大值(总和 - 最大值)

中文机器翻译题面 查看原题

分数: 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