Quiz
Submit
解法
- d日で解けるかを二分探索
- カフェイン列は大きい順にソートしておき、各日の早いうちに飲む
- 同じ日の中で後に飲んだカフェインの「効きが弱くなる」
- 強いカフェインを1日の後半で飲むと減衰の影響を受けてしまう
- 一方、弱いカフェインを後半で飲むとmax(A[i], 0) なので減衰の影響を受けないため
その他
- d日に分割したときの「効く」総カフェイン量、累積和とかで高速化が必要と思っていたけれど不要だった
- 二分探索しているので総計算量がO(N logN)のため
レート
- 少し下がって1400ちょい
- コンテスト内に解けるべき問題だった
