103522: [Atcoder]ABC352 C - Standing On The Shoulders
Description
Score: $300$ points
Problem Statement
There are $N$ giants, named $1$ to $N$. When giant $i$ stands on the ground, their shoulder height is $A_i$, and their head height is $B_i$.
You can choose a permutation $(P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ and stack the $N$ giants according to the following rules:
-
First, place giant $P_1$ on the ground. The giant $P_1$'s shoulder will be at a height of $A_{P_1}$ from the ground, and their head will be at a height of $B_{P_1}$ from the ground.
-
For $i = 1, 2, \ldots, N - 1$ in order, place giant $P_{i + 1}$ on the shoulders of giant $P_i$. If giant $P_i$'s shoulders are at a height of $t$ from the ground, then giant $P_{i + 1}$'s shoulders will be at a height of $t + A_{P_{i + 1}}$ from the ground, and their head will be at a height of $t + B_{P_{i + 1}}$ from the ground.
Find the maximum possible height of the head of the topmost giant $P_N$ from the ground.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq B_i \leq 10^9$
- All input values are integers.
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 the answer.
Sample Input 1
3 4 10 5 8 2 9
Sample Output 1
18
If $(P_1, P_2, P_3) = (2, 1, 3)$, then measuring from the ground, giant $2$ has a shoulder height of $5$ and a head height of $8$, giant $1$ has a shoulder height of $9$ and a head height of $15$, and giant $3$ has a shoulder height of $11$ and a head height of $18$.
The head height of the topmost giant from the ground cannot be greater than $18$, so print $18$.
Sample Input 2
5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Sample Input 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
Sample Output 3
7362669937
Input
Output
问题描述
有$N$个巨人，分别名为1到$N$。当巨人$i$站在地面上时，他们的肩膀高度是$A_i$，头部高度是$B_i$。
你可以选择一个排列$(P_1, P_2, \ldots, P_N)$，其中$(1, 2, \ldots, N)$，并按照以下规则将$N$个巨人堆叠起来：
-
首先，将巨人$P_1$放在地面上。巨人$P_1$的肩膀离地面的高度为$A_{P_1}$，头部离地面的高度为$B_{P_1}$。
-
然后，按顺序$i = 1, 2, \ldots, N - 1$，将巨人$P_{i + 1}$放在巨人$P_i$的肩膀上。如果巨人$P_i$的肩膀离地面的高度为$t$，那么巨人$P_{i + 1}$的肩膀离地面的高度为$t + A_{P_{i + 1}}$，头部离地面的高度为$t + B_{P_{i + 1}}$。
找出最上面的巨人$P_N$头部离地面的最大可能高度。
限制条件
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq B_i \leq 10^9$
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
输出
打印答案。
样例输入1
3 4 10 5 8 2 9
样例输出1
18
如果$(P_1, P_2, P_3) = (2, 1, 3)$，那么从地面测量，巨人$2$的肩膀高度为$5$，头部高度为$8$，巨人$1$的肩膀高度为$9$，头部高度为$15$，巨人$3$的肩膀高度为$11$，头部高度为$18$。
最上面的巨人头部离地面的高度无法超过$18$，所以打印$18$。
样例输入2
5 1 1 1 1 1 1 1 1 1 1
样例输出2
5
样例输入3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
样例输出3
7362669937