[ABC348G] Max (Sum - Max)
题意翻译
给出 $N$，以及 $A_{1...N},B_{1...N}$。
对于每个 $k\in [1,N]$，找出一个 $1...N$ 的集合 $S$，满足 $|S|=k$ 且 $\sum\limits_{i\in S}A_i-\max\limits_{i\in S}B_i$ 最大，输出这个值。
$1\le N\le 2\times 10^5,\space |A_i|\le 10^9,\space |B_i|\le 2\times 10^{14}$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc348/tasks/abc348_g
長さ $ 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 $ についての問題の答えを出力せよ。
输入输出样例
输入样例 #1
3
4 1
5 6
3 2输出样例 #1
3
5
6输入样例 #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说明
### 制約
- $ 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} $
### Sample Explanation 1
以下の選び方がそれぞれ最適です。 - $ k\ =\ 1 $ : $ S\ =\ \{1\} $ - $ k\ =\ 2 $ : $ S\ =\ \{1,\ 3\} $ - $ k\ =\ 3 $ : $ S\ =\ \{1,\ 2,\ 3\} $