ABC214 C Distribution
$ dp_i
:=
$ i
番目のすぬけ君が宝石をもらう時刻の最小値 とすると,
$ dp_{i + 1} = min(dp_{i + 1}, min(T_i, dp_i + S_i))
となる. ただし,
$ dp_i
の値は
$ i > N
となっても更新される可能性があるため, このDPの遷移を
$ N + 1
のすぬけ君が
$ 1
番目のすぬけ君を指すことに注意して2周行えばよい.
実装例:
https://atcoder.jp/contests/abc214/submissions/25025041