No.2808 Concentration
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 36
作問者 : watasou1543 / テスター : hirayuu_yc Magentor penguin8331 highlighter warabi0906 keisuke6 silv723 zeta7532 fact493 Yoyoyo8128
タグ : / 解いたユーザー数 36
作問者 : watasou1543 / テスター : hirayuu_yc Magentor penguin8331 highlighter warabi0906 keisuke6 silv723 zeta7532 fact493 Yoyoyo8128
問題文最終更新日: 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$ 増やす
なお、$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もしくは右上の雲マークをクリックしてアカウントを作成してください。