Codeforces Round #822 (Div. 2)

  Cまで三完。

コンテストへのリンク

D. Slime Escape

　コンテスト中は主に区間DPを考えていて解けなかった。

　コンテスト後、解説を読んでもよく分からなかったけど、ちゃんと整理したらACできた。

　左右どちらに進むにせよ、得できるなら得をしたい。

　ので、累積和と、累積minを考え、累積和がプラスになった箇所について、「いくつ以上のHPがあれば得できるか」を調べる。

　それを貪欲に取っていけば良い。