問題一覧 > 通常問題

No.2808 Concentration

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : watasou1543 / テスター : hirayuu_yc Magentor penguin8331 highlighter warabi0906 keisuke6 silv723 zeta7532 fact493 Yoyoyo8128
2 ProblemId : 11082 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:54:42

問題文

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

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

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

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

入力

入力は以下の形式で標準入力から与えられる。 
N   S   HN ~~~ S ~~~ H
X1   Y1   Z1X_{1} ~~~ Y_{1}~~~ Z_{1}
X2   Y2   Z2X_{2} ~~~ Y_{2} ~~~ Z_{2}
        ⋮~~~~~~~~ \vdots
XN  YN  ZNX_{N} ~~ Y_{N} ~~ Z_{N}

制約

  • 1≤N≤2×1051 \leq N \leq 2×10^5
  • 1≤S,H≤1091 \leq S,H \leq 10^9
  • 0≤Xi<Yi≤109(1≤i≤N)0 \leq X_{i} \lt Y_{i} \leq 10^{9} \left( 1 \leq i \leq N\right)
  • Yi<Xj(1≤i<j≤N)Y_{i} \lt X_{j} \left(1 \leq i \lt j \leq N \right)
  • 1≤Zi≤1091 \leq Z_i \leq 10^9
  • 入力はすべて整数

出力

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

サンプル

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

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

  • 10100+1.0110^{100}+1.01 分寝る
  • 11 つ目の話を聞き、知識を 44 増やす
  • 6.026.02 分寝る
  • 33 つ目の話を聞き、知識を 55 増やす
どう寝起きする時間を決めても 1010 以上の知識を得ることはできないため、これが最適です。
なお、22 つ目の話は 2.982.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もしくは右上の雲マークをクリックしてアカウントを作成してください。