AtCoder Regular Contest 064: C - Boxes and Candies

solution

貪欲。$O(N)$。

$i$番目まで条件を満たしていて$a_i + a_{i+1} \ge x$とする。 $a_i$と$a_{i+1}$のどちらかを減らすのだが、$a_i$を減らすことに意味はないため$a_{i+1}$を減らせばよい。 $a_{i+1} \ge 0$の制約があることに注意。

implementation

#!/usr/bin/env python3
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    delta = max(0, a[i] + a[i+1] - x)
    a[i+1] -= delta
    if a[i+1] < 0:
        a[i] += a[i+1]
        a[i+1] = 0
    ans += delta
print(ans)