ARC 064 C - Boxes and Candies

問題文

N個の箱が一直線上にあり、各々にa_i個の玉が入っている。隣接する箱の玉の数の和をx個以下にするために、取り出す必要のある玉の数を答えよ。

解法

観察として、ある箱の玉を取ったら、その両側の箱に対して取るべき玉の数が少なくなる。 初期条件として、a_0x以下である必要がある。よって、max(0, a_0-x)の玉を取らなければならない。 a_0+a_1の和をx以下にするために、a_0a_1とのどちらから箱を取るのが良いか考えると、両側に箱を持つa_1の方が良いことが分かる。以上より、列の端のa_0x以下にし、次の箱で繰り返し帳尻合わせとして減らしていけば良い。

int main() {
  int N; ll x; cin >> N >> x;
  ll ans = 0;
  ll prev = 0;
  rep(i, N) {
    ll a; cin >> a;
    ll use = max(0LL, (prev + a) - x);
    ans += use;
    prev = a - use;
  }
  cout << ans << endl;
  return 0;
}