No.448

Ameくんが行う処理の難しさの最大値を $x$ に決めると, Yukiさんは $x$ より大きい難しさの処理をすべて行う必要がある. このときにYukiさんが十分に睡眠を取れるかどうかを調べれば, 決めた $x$ のときに処理がすべて行えるかどうかがわかる.

あとは二分探索で $x$ を決めれば, Ameくんが行う処理の難しさの最大値を最小化した値がわかる. この値を $m$ としておく.

Ameくんが行う処理の難しさの和をなるべく少なくするには, Yukiさんが行う処理の難しさの和をなるべく大きくすればいい.

Yukiさんが $i$ 番目の処理までに行う難しさの和の最大値を $A_i$ とする.

このとき, Yukiさんは $m$ より大きい処理は必ず行わなければならないので, $T_i - T_k \gt K$ となる最大の $k$ を考えると, $k+1 \dots i$ の間にそのような処理があれば, $i$ 番目の処理は行うことができないので,

$$A_i = A_{i-1}$$

となる. そうでなければ,

$$A_i = \max(A_{i-1}, A_k + D_i)$$

となる.

なお, $k$ はしゃくとり法でもいいし, 二分探索でもいい.