問題一覧 > 通常問題

No.1826 Fruits Collecting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : IKyoproIKyopro / テスター : torisasami4torisasami4
9 ProblemId : 5346 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-21 21:47:43

問題文

umgくんは、$1$次元上の座標 $0$ にいます。今は時刻 $0$ です。umgくんは、空から降ってくるフルーツを集めることにしました。 umgくんは、時刻が $1$ 進むごとに、 $1$ 大きい座標に移動するか、 $1$ 小さい座標に移動するか、 その場にとどまるかを選択できます。 フルーツは全部で $N$ 個降ってくることがわかっており、 $1$ から $N$ までの番号がつけられています。 $i$ 番目のフルーツの価値は $V_i$ であり、時刻 $T_i$ に位置 $X_i$ に落ちてきます。 umgくんは、時刻 $T_i$ に位置 $X_i$ にいたとき(ちょうど着いた時も含む)のみ、$i$ 番目のフルーツを獲得することができます。

umgくんが適切に動いたとき、獲得したフルーツの価値の総和の最大値はいくつになるでしょうか?

入力

$N$
$T_1 \ X_1 \ V_1$
$T_2 \ X_2 \ V_2$
$\vdots$
$T_N \ X_N \ V_N$

  • $1\leq N \leq 2\times 10^5$
  • $1\leq T_i \leq 10^9$
  • $-10^9\leq X_i \leq 10^9$
  • $1\leq V_i \leq 10^9$

出力

答えを一行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
2 2 5
4 -3 10
7 6 12
出力
17

フルーツ1とフルーツ3を獲得するのが最適です。

サンプル2
入力
2
3 5 100000
10 -12 10000000
出力
0

サンプル3
入力
10
714285999 -270646698 674821981
145453038 -493065708 578571371
182454287 559505745 613524283
91187113 58976167 387606995
161055320 603771484 957805357
859495351 829271084 788215467
206954118 -473864425 246246653
371344794 -579231472 433788627
205330018 -483888481 20249846
440000042 164167853 119221407
出力
1062428976

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。