102663: [AtCoder]ABC266 D - Snuke Panic (1D)
Description
Score : $400$ points
Problem Statement
Takahashi is trying to catch many Snuke.
There are five pits at coordinates $0$, $1$, $2$, $3$, and $4$ on a number line, connected to Snuke's nest.
Now, $N$ Snuke will appear from the pits. It is known that the $i$-th Snuke will appear from the pit at coordinate $X_i$ at time $T_i$, and its size is $A_i$.
Takahashi is at coordinate $0$ at time $0$ and can move on the line at a speed of at most $1$.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.
Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.
Constraints
- $1 \leq N \leq 10^5$
- $0 < T_1 < T_2 < \ldots < T_N \leq 10^5$
- $0 \leq X_i \leq 4$
- $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$ $T_1$ $X_1$ $A_1$ $T_2$ $X_2$ $A_2$ $\vdots$ $T_N$ $X_N$ $A_N$
Output
Print the answer as an integer.
Sample Input 1
3 1 0 100 3 3 10 5 4 1
Sample Output 1
101
The optimal strategy is as follows.
- Wait at coordinate $0$ to catch the first Snuke at time $1$.
- Go to coordinate $4$ to catch the third Snuke at time $5$.
It is impossible to catch both the first and second Snuke, so this is the best he can.
Sample Input 2
3 1 4 1 2 4 1 3 4 1
Sample Output 2
0
Takahashi cannot catch any Snuke.
Sample Input 3
10 1 4 602436426 2 1 623690081 3 3 262703497 4 4 628894325 5 3 450968417 6 1 161735902 7 1 707723857 8 2 802329211 9 0 317063340 10 2 125660016
Sample Output 3
2978279323
Input
题意翻译
高桥君在数轴上挖了 $5$ 个坑，坐标为 $0,1,2,3,4$。一开始他在 $0$ 位置，每秒最多移动 $1$ 单位。 现有 $n$ 条 Snuke，第 $i$ 条大小为 $A_i$，在第 $T_i$ 时刻出现在坐标为 $X_i$ 的坑。**请注意出现仅发生在瞬间，下一时刻消失。** 高桥君能抓到第 $i$ 条 Snuke 当且仅当某时刻他在第 $T_i$ 时刻出现在 $X_i$。请计算他抓到的 Snuke 总大小最大值。Output
问题描述
高桥正在试图捕捉很多松鼠。
在数轴上有五个坑，分别在坐标0、1、2、3和4处，连接到松鼠的巢穴。
现在，将有N只松鼠从坑中出现。已知第i只松鼠将在时间$T_i$从坐标$X_i$的坑中出现，它的大小为$A_i$。
高桥在时间0时位于坐标0处，并且可以在数轴上以最多1的速度移动。
他只有在他正好在松鼠出现的坑的坐标时才能捕捉到松鼠。捕捉松鼠所需的时间可以忽略不计。
通过最优移动，找到高桥可以捕捉到的松鼠大小的最大和。
约束条件
- $1 \leq N \leq 10^5$
- $0 < T_1 < T_2 < \ldots < T_N \leq 10^5$
- $0 \leq X_i \leq 4$
- $1 \leq A_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入以标准输入给出以下格式：
$N$ $T_1$ $X_1$ $A_1$ $T_2$ $X_2$ $A_2$ $\vdots$ $T_N$ $X_N$ $A_N$
输出
以整数形式打印答案。
样例输入1
3 1 0 100 3 3 10 5 4 1
样例输出1
101
最优策略如下：
- 在坐标0处等待，以便在时间1时捕捉第一只松鼠。
- 移动到坐标4处，以便在时间5时捕捉第三只松鼠。
不可能同时捕捉到第一只和第二只松鼠，所以这是他能做的最好的了。
样例输入2
3 1 4 1 2 4 1 3 4 1
样例输出2
0
高桥无法捕捉到任何松鼠。
样例输入3
10 1 4 602436426 2 1 623690081 3 3 262703497 4 4 628894325 5 3 450968417 6 1 161735902 7 1 707723857 8 2 802329211 9 0 317063340 10 2 125660016
样例输出3
2978279323