Max (Sum

题目描述

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

考虑从 $1$ 到 $N$（含）之间选择 $k$ 个互不相同的整数。记所选整数的集合为 $S$。求下列表达式的最大值： $\displaystyle (\sum_{i \in S} A_i) - \max_{i \in S} B_i$。

输入格式

输入按照下列格式由标准输入给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

输出 $N$ 行。第 $i$ 行应当包含对应 $k=i$ 问题的答案。

3
4 1
5 6
3 2

3
5
6

2
0 1
0 1

-1
-1

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

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}$以下选择是最优的。

$k = 1$: $S = \{1\}$ $k = 2$: $S = \{1, 3\}$ $k = 3$: $S = \{1, 2, 3\}$

标签: AtCoder|abc348G

来源

AtCoder|abc348G