G - Max (Sum - Max)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
長さ 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 としてあり得る値の最大値を求めよ。
制約
- 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
Score: 650 points
Problem Statement
You are given two integer sequences A and B of length N. For k = 1, 2, \ldots, N, solve the following problem:
- Consider choosing k distinct integers between 1 and N, inclusive. Let S be the set of chosen integers. Find the maximum value of \displaystyle (\sum_{i \in S} A_i) - \max_{i \in S} B_i.
Constraints
- 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}
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print N lines. The i-th line should contain the answer to the problem for k=i.
Sample Input 1
3 4 1 5 6 3 2
Sample Output 1
3 5 6
The following choices are optimal.
- k = 1: S = \{1\}
- k = 2: S = \{1, 3\}
- k = 3: S = \{1, 2, 3\}
Sample Input 2
2 0 1 0 1
Sample Output 2
-1 -1
Sample Input 3
6 9 7 2 4 7 1 -1000 0 3 4 8 5
Sample Output 3
6 10 17 20 22 -978