102197: [AtCoder]ABC219 H - Candles
Description
Score : $600$ points
Problem Statement
There are $N$ candles on an infinite number line. The $i$-th candle is at the coordinate $X_i$. At time $0$, it has a length of $A_i$ and is lit. Each minute, the length of a lit candle decreases by $1$. When the length becomes $0$, it burns out, and its length does not change after that. Additionally, the length of an unlit candle does not change.
Takahashi is at the coordinate $0$ at time $0$. Each minute, he can move a distance of at most $1$. If there is a candle at his current coordinate, he can put out that candle. (If there are multiple candles there, he can put out all of them.) The time it takes to put out a candle is negligible.
Find the maximum possible total length of the candles remaining at $10^{100}$ minutes after time $0$, achieved by Takahashi's optimal course of actions.
Constraints
- $1 \leq N \leq 300$
- $-10^9 \leq X_i \leq 10^9$
- $1 \leq A_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $X_1$ $A_1$ $X_2$ $A_2$ $:$ $X_N$ $A_N$
Output
Print the answer.
Sample Input 1
3 -2 10 3 10 12 10
Sample Output 1
11
The third candle, which is at coordinate $12$, will burn out before Takahashi puts it out, regardless of Takahashi's behavior.
For the other two candles, if he goes to coordinate $-2$ in two minutes to put out the first and then goes to coordinate $3$ in five minutes to put out the second, the lengths of those candles will not change after that. The lengths of those candles remaining are $10-2=8$ and $10-2-5=3$, for a total of $8+3=11$, which is the maximum that can be achieved. Thus, print $11$.
Sample Input 2
5 0 1000000000 0 1000000000 1 1000000000 2 1000000000 3 1000000000
Sample Output 2
4999999994
Note that two or more candles may occupy the same coordinate and that the answer may not fit into a $32$-bit integer.
Input
题意翻译
$N$ 支蜡烛放在无限延伸的数轴上。$i$ 第一支蜡烛的坐标是 $x_i$，在 $0 $ 的时刻，蜡烛的长度是 $a_i $。点燃的蜡烛每 $1$，长度就短 $1$，当长度为 $0$ 时，蜡烛就会燃烧殆尽，之后长度不变。另外，被熄灭的蜡烛的长度不变。 高桥君在 $0$ 时刻坐标 $0$，每分钟可以移动不到 $1$。高桥君在与自己所在坐标相同的坐标上有蜡烛的情况下，能够将蜡烛的火熄灭。(同一坐标中有多个蜡烛的情况下可以一起吹灭)在这里，熄灭蜡烛所需的时间可以忽略不计。 请求出高桥采取适当行动时，从 $0$ 到 $ 10^{100}$ 分钟之后剩下的蜡烛长度之和可能的最大值。 ## 输入格式 输入以以下形式从标准输入给出: > $ N $ $ X_1 $ $ A_1 $ $ X_2 $ $ A_2 $ $ : $ $ X_N $ $ A_N $ ## 输出格式 输出剩下的蜡烛长度之和可能的最大值。Output
问题描述
在一条无限的数轴上有N支蜡烛。第i支蜡烛在坐标X_i处。在时间0，它的长度为A_i，并且是点燃的。每分钟，点燃的蜡烛的长度减少1。当长度变为0时，它会熄灭，此后它的长度不再改变。此外，未点燃的蜡烛的长度不会改变。
在时间0后的10^{100}分钟内，通过Takahashi的最佳行动方案，找出蜡烛剩余总长度的最大可能值。
限制条件
- 1 \leq N \leq 300
- -10^9 \leq X_i \leq 10^9
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入从标准输入给出以下格式：
$N$ $X_1$ $A_1$ $X_2$ $A_2$ $:$ $X_N$ $A_N$
输出
打印答案。
样例输入1
3 -2 10 3 10 12 10
样例输出1
11
在坐标12的第三支蜡烛，无论Takahashi的行为如何，都会在Takahashi将其熄灭之前熄灭。
对于其他两支蜡烛，如果他在两分钟内走到坐标-2将第一支熄灭，然后在五分钟内走到坐标3将第二支熄灭，那么这两支蜡烛的长度在那之后就不会改变。剩余的蜡烛长度分别为10-2=8和10-2-5=3，总和为8+3=11，这是可以达到的最大值。因此，打印11。
样例输入2
5 0 1000000000 0 1000000000 1 1000000000 2 1000000000 3 1000000000
样例输出2
4999999994
请注意，两支或多支蜡烛可以位于同一个坐标，并且答案可能不适用于32位整数。