問題一覧 > 通常問題

No.2808 Concentration

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : watasou1543watasou1543 / テスター : hirayuu_ychirayuu_yc MagentorMagentor penguin8331penguin8331 highlighterhighlighter warabi0906warabi0906 keisuke6keisuke6 silv723silv723 zeta7532zeta7532 fact493fact493 Yoyoyo8128Yoyoyo8128
2 ProblemId : 11082 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:54:42

問題文

watasou君は授業を受けています。

watasou君は未来予知ができるので、warabi先生が重要な話を $N$ 回行うことを知っています。授業開始時を $0$ 分後とすると、$i$ 番目の重要な話は $X_i+10^{100}+0.01$ 分後から $Y_i+10^{100}-0.01$ 分後まで行われ、最初から最後まで聞くことで $Z_i$ の知識を得られます。

watasou君は起きているとき、またその時に限り授業を聞くことができます。watasou君はwarabi先生の授業中に集中力を保てないため、連続して最大 $S$ 分間しか起きていることができません。また、一度寝ると最低でも $H$ 分間は起きることができません。

watasou君が寝起きする時間を上記の条件の下で自由に決められるとき、得ることの可能な知識の総和の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
$N ~~~ S ~~~ H$
$X_{1} ~~~ Y_{1}~~~ Z_{1}$
$X_{2} ~~~ Y_{2} ~~~ Z_{2}$
$~~~~~~~~ \vdots$
$X_{N} ~~ Y_{N} ~~ Z_{N}$

制約

  • $1 \leq N \leq 2×10^5$
  • $1 \leq S,H \leq 10^9$
  • $0 \leq X_{i} \lt Y_{i} \leq 10^{9} \left( 1 \leq i \leq N\right)$
  • $Y_{i} \lt X_{j} \left(1 \leq i \lt j \leq N \right)$
  • $1 \leq Z_i \leq 10^9$
  • 入力はすべて整数

出力

答えを出力してください。

サンプル

サンプル1
入力
4 2 2
1 3 4
5 8 6
9 11 5
12 13 2
出力
9

以下のように行動することで $9$ の知識を得ることができます。

  • $10^{100}+1.01$ 分寝る
  • $1$ つ目の話を聞き、知識を $4$ 増やす
  • $6.02$ 分寝る
  • $3$ つ目の話を聞き、知識を $5$ 増やす
どう寝起きする時間を決めても $10$ 以上の知識を得ることはできないため、これが最適です。
なお、$2$ つ目の話は $2.98$ 分間かけて行われるため、最初から最後まで聞くことができないことに注意してください。

サンプル2
入力
1 1 1
0 100 100
出力
0

サンプル3
入力
3 3 4
0 3 4
5 8 7
11 12 5
出力
9

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