Snuke Panic (1D)

题目描述

Takahashi 正在尝试抓住许多 Snuke。 在数轴上有五个坑，坐标分别为 $0$、$1$、$2$、$3$ 和 $4$，与 Snuke 的巢相连。 现在，会有 $N$ 只 Snuke 从这些坑中出现。已知第 $i$ 只 Snuke 会在时间 $T_i$ 从坐标为 $X_i$ 的坑出现，且其大小为 $A_i$。 Takahashi 在时间 $0$ 时位于坐标 $0$，并且可以以最多速度 $1$ 在数轴上移动。
当且仅当他在出现的恰好时刻位于该坑的坐标时，他才能抓住从该坑出现的 Snuke。
抓住一只 Snuke 所需的时间可以忽略不计。 通过最优移动，求 Takahashi 能抓到的 Snuke 的大小总和的最大值。

输入格式

输入以标准输入给出，格式如下： $N$ $T_1$ $X_1$ $A_1$ $T_2$ $X_2$ $A_2$ $\vdots$ $T_N$ $X_N$ $A_N$

输出格式

以整数形式输出答案。

3
1 0 100
3 3 10
5 4 1

101

3
1 4 1
2 4 1
3 4 1

0

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

2978279323

提示

$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$ 输入中的所有数值均为整数。最优策略如下。

在坐标 $0$ 等待以在时间 $1$ 抓住第一只 Snuke。 前往坐标 $4$ 以在时间 $5$ 抓住第三只 Snuke。

同时抓住第一只和第二只 Snuke 是不可能的，因此这是他能做到的最优情况。
Takahashi 无法抓到任何 Snuke。

标签: AtCoder|abc266D

来源

AtCoder|abc266D