ARC 064 C - Boxes and Candies

問題文

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

解法

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

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;
}