AT_abc348_g [ABC348G] Max (Sum - Max)

题目描述

给定两个长度为 $N$ 的整数序列 $A$ 和 $B$。对于 $k = 1, 2, \ldots, N$，请解决以下问题：

• 从 $1$ 到 $N$ 中选择 $k$ 个互不相同的整数。设选出的整数集合为 $S$，求 $\displaystyle\left(\sum_{i \in S} A_i\right) - \max_{i \in S} B_i$ 可能取得的最大值。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

请输出 $N$ 行。第 $i$ 行输出 $k=i$ 时问题的答案。

输入输出样例 #1

输入 #1

3
4 1
5 6
3 2

输出 #1

3
5
6

输入输出样例 #2

输入 #2

2
0 1
0 1

输出 #2

-1
-1

输入输出样例 #3

输入 #3

6
9 7
2 4
7 1
-1000 0
3 4
8 5

输出 #3

6
10
17
20
22
-978

说明/提示

限制条件

• $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}$

样例解释 1

以下是每种 $k$ 的最优选择方式。

• $k = 1$：$S = \{1\}$
• $k = 2$：$S = \{1, 3\}$
• $k = 3$：$S = \{1, 2, 3\}$

由 ChatGPT 4.1 翻译