D - Snuke Panic (1D) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

高橋君はすぬけ君たちを捕まえようとしています。

数直線上の座標 0,1,2,3,4 の 5 箇所に穴があり、すぬけ君たちの巣につながっています。

これから 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 に 1 番目のすぬけ君を捕まえる
  • 座標 4 へ移動し、時刻 5 に 3 番目のすぬけ君を捕まえる

1 番目と 2 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。

入力例 2

3
1 4 1
2 4 1
3 4 1

出力例 2

0

高橋君はすぬけ君を 1 匹も捕まえることができません。

入力例 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

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