Problem:


Score : 300 points

Problem Statement

There are N boxes arranged in a row.
Initially, the i-th box from the left contains a_i candies.

Snuke can perform the following operation any number of times:

Choose a box containing at least one candy, and eat one of the candies in the chosen box.

His objective is as follows:

Any two neighboring boxes contain at most x candies in total.

Find the minimum number of operations required to achieve the objective.

Constraints

2 ≤ N ≤ 10^5

0 ≤ a_i ≤ 10^9

0 ≤ x ≤ 10^9

Input

The input is given from Standard Input in the following format:

N x
a_1 a_2 ... a_N

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3 3
2 2 2

Sample Output 1

1

Eat one candy in the second box.
Then, the number of candies in each box becomes (2, 1, 2).

Sample Input 2

6 1
1 6 1 2 0 4

Sample Output 2

11

For example, eat six candies in the second box, two in the fourth box, and three in the sixth box.
Then, the number of candies in each box becomes (1, 0, 1, 0, 0, 1).

Sample Input 3

5 9
3 1 4 1 5

Sample Output 3

0

The objective is already achieved without performing operations.

Sample Input 4

2 0
5 5

Sample Output 4

10

All the candies need to be eaten.



Sample input:
3 3
2 2 2


Sample output:
1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,x=map(int,input().split())
    a=list(map(int,input().split()))
    ans=0
    for i in range(N):
        ans+=max(a[i]-x,0)
        a[i]=min(a[i],x)
    for i in range(N-1):
        if a[i]+a[i+1]>x:
            ans+=a[i]+a[i+1]-x
            a[i+1]=x-a[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, x = na()
a = na()

ans = 0
for i in range(n):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x

for i in range(n - 1):
    if a[i] + a[i + 1] > x:
        t = a[i] + a[i + 1] - x
        ans += t
        a[i + 1] -= t

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, x = mi()
    L = lmi()

    ans = 0
    sum_memo = 0
    for i in range(n):
        sum_memo += L[i]
        if sum_memo > x:
            diff = sum_memo - x
            ans += diff
            L[i] -= diff
            sum_memo = x
        if i != 0:
            sum_memo -= L[i-1]
    # print(L)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))

cnt = 0
for i in range(n-1):
    diff = (a[i] + a[i+1]) - x
    if diff <= 0:
        continue
    if diff <= a[i+1]:
        a[i+1] -= diff
    else:
        a[i] -= (diff - a[i+1])
        a[i+1] = 0
    cnt += diff
print(cnt)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
pre_a = 0
ans = 0
for a in A:
  if a > x - pre_a:
    ans += a - (x - pre_a)
    pre_a = x - pre_a
  else:
    pre_a = a

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(N - 1):
    diff = a[i] + a[i + 1] - x
    if diff > 0:
        ans += diff
        a[i + 1] = max(0, a[i + 1] - diff)
print(ans)

Submission status: Accepted

Solution code:
import sys

N, x = map(int, sys.stdin.readline().strip().split())
A = list(map(int, sys.stdin.readline().strip().split()))

ans = 0
tmp_sum = A[0]
for i in range(N-1):
    if A[i] + A[i+1] > x:
        diff = A[i] + A[i+1] - x
        ans += diff
        # 明示的に書かれていないが、A[i] > diff - A[i+i]  はないはず
        A[i+1] = 0 if A[i+1] < diff else A[i+1] - diff

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
k=0
count=0
if a[1]+a[0]>x and x>=a[0]:
    k=x-a[0]
    count+=a[1]+a[0]-x
elif a[1]+a[0]>x and x<a[0]:
    k=0
    count+=a[1]+a[0]-x
else:
    k=a[1]
for i in range(1,n-1):
    if k+a[i+1]<=x:
        k=a[i+1]
        
    elif x>=k:
        count+=k+a[i+1]-x
        k=x-k
    else:
        count+=k+a[i+1]-x
        k=0
print(count)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n-1):
  if a[i]+a[i+1] > x:
    k = min([a[i+1], a[i]+a[i+1]-x])
    a[i+1] -= k
    ans += k
    if a[i] > x:
      ans += a[i]-x
      a[i] = x

print(ans)

Submission status: Accepted

Solution code:
import sys

def resolve():
    readline=sys.stdin.readline
    n,x=map(int, readline().rstrip().split())
    arr=list(map(int, readline().rstrip().split()))
    ans=0
    for i in range(1,len(arr)):
        xx=arr[i-1]+arr[i]
        if xx > x:
            arr[i]-=(xx-x)
            ans+=(xx-x)
            if arr[i]<0:
                arr[i-1]+=arr[i]
                arr[i]=0
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0

if a[0] > x:
    ans += a[0] - x
    a[0] = x

for i in range(1, N):
    if a[i] + a[i - 1] > x:
        ans += a[i] - (x - a[i - 1])
        a[i] = x - a[i - 1]

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int, input().split())
a=[0]+list(map(int, input().split()))
ans=0
for i in range(n):
  eat=max(a[i]+a[i+1]-x,a[i+1]-2*x,0)
  ans+=eat
  a[i+1]-=eat
print(ans)

Submission status: Accepted

Solution code:
def eat(a, b):
    e = A[a] + A[b] - X
    if 0 < e <= A[b]:
        A[b] -= e
    elif e > A[b]:
        e -= A[b]
        A[b] = 0
        A[a] -= e

N, X = map(int, input().split())
A = list(map(int, input().split()))
before_eat = sum(A)
eat(-1, -2)
for i in range(N - 1):
    eat(i, i + 1)
print(before_eat - sum(A))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    if i != 0:
        y = A[i-1]+A[i]
    else:
        y = A[i]
    if y <= x:
        continue
    ans += y-min(x, y)
    A[i] -= y-min(x, y)
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=[int(i)for i in input().split()]
c=0
if a[0]>x:
  c=a[0]-x
  a[0]=x
for i in range(n-1):
  if a[i]+a[i+1]>x:
    c+=a[i]+a[i+1]-x
    a[i+1]=x-a[i]
print(c)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a = list(map(int,input().split()))

nec = [0 for i in range(n)]
fi = max(-x+(a[0]+a[1]),0)
nec[1] = max(0,a[1]-fi)
for i in range(2,n):
    sec = max(-x+(a[i]+nec[i-1]),0)
    nec[i]=a[i]-sec
    fi += sec

print(fi)

Submission status: Accepted

Solution code:
def main():
    n, x, *a = map(int, open(0).read().split())
    a = [0] + a
    ans = 0
    tmp = 0
    for i, j in zip(a, a[1:]):
        i -= tmp
        if (i + j - x) > 0:
            c = (i + j - x)
            ans += c
            tmp = c
        else:
            tmp = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, x, *a = map(int, open(0).read().split())
    a = [0] + a
    ans = 0
    tmp = 0
    for i, j in zip(a, a[1:]):
        i -= tmp
        if i + j - x > 0:
            c = i + j - x
            ans += c
            tmp = c
        else:
            tmp = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, x, *a = map(int, open(0).read().split())
    a = [0] + a
    ans = 0
    tmp = 0
    for i, j in zip(a, a[1:]):
        i -= tmp
        if i + j > x:
            c = (i + j) - x
            ans += c
            tmp = c
        else:
            tmp = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

N, X = getNM()
A = getList()
ans = 0
flag = True
while flag:
    flag = False
    for i in range(N - 2):
        minus1 = A[i] + A[i + 1] - X
        minus2 = A[i + 1] + A[i + 2] - X
        if minus1 > 0 and minus2 > 0:
            minuspoint = min(minus1, minus2, A[i + 1])
            A[i + 1] -= minuspoint
            ans += minuspoint
            flag = True
between = [A[i] + A[i + 1] - X for i in range(N - 1)]
for i in between:
    if i > 0:
        ans += i
print(ans)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
A = list(map(int,input().split()))
B = A.copy()
B = B[::-1]
ans = 0
tmp = 0
for i in range(n-1):
    if A[i] + A[i+1] >x:
        d = (A[i] + A[i+1]) -x
        tmp+= d
        if A[i+1] >=d:
            A[i+1] -=d
        else:
            A[i] = A[i] - (d-A[i+1])
            A[i+1] = 0
A = B
ans = tmp
tmp=0
for i in range(n-1):
    if A[i] + A[i+1] >x:
        d = (A[i] + A[i+1])-x
        tmp+= d
        if A[i+1] >=d:
            A[i+1] -=d
        else:
            A[i] = A[i] - (d-A[i+1])
            A[i+1] = 0

print(min(ans,tmp))

Submission status: Accepted

Solution code:
N,x = map(int,input().split())
a=list(map(int,input().split()))
cnt=0
b=[0]*N

#0,2
b[0]=a[0] if a[0]<=x else x
cnt+= a[0]-b[0]

for i in range(1,N):
  b[i] = a[i] if b[i-1]+a[i]<=x else max(0,x-b[i-1])
  cnt += a[i]-b[i]
  
#print(b)
print(cnt)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    if i == 0:
        if A[i] <= x:
            continue
        eat = A[i] - x
        ans += eat
        A[i] = A[i] - eat
        continue
    if A[i-1]+A[i] <= x:
        continue
    eat = A[i-1] + A[i] - x
    ans += eat
    A[i] = A[i] - eat

print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(1, n):
    if A[i-1]+A[i] <= x:
        continue
    eat = A[i-1]+A[i] - x
    ans += eat
    A[i] = max(0, A[i]-eat)

print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = [int(i) for i in input().split()]

ans = 0
for i in range(1, N):
    if A[i-1]+A[i] > x:
        e = A[i-1]+A[i]-x
        ans += e
        if A[i] >= e:
            A[i] -= e
        else:
            A[i] = 0
print(ans)

Submission status: Accepted

Solution code:
N,x = map(int, input().split())
*A, = map(int, input().split())

#貪欲法
ans = 0
for i in range(N-1):
    if (A[i]+A[i+1])<=x:
        continue
    #xより大きい分だけ食べる
    eat = (A[i]+A[i+1])-x
    if eat<=A[i+1]:
        A[i+1] -= eat
    else:
        A[i+1] = 0
        A[i] = A[i]-(eat-A[i+1])
    ans = ans + eat
print(ans)

Submission status: Accepted

Solution code:
def eat(A,x):
    n = len(A)
    pt = 1
    output = 0
    while pt < n:
        if A[pt-1] + A[pt] > x:
            tmp = A[pt]
            A[pt] = max(0,x-A[pt-1])
            output += (tmp-A[pt])
        pt += 1
    if A[0] + A[1] > x:
        tmp = A[0]
        A[0] = max(0,x-A[1])
        output += (tmp-A[0])
    return output

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))

    ans = eat(a,x)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,x=list(map(int,input().split()))
a=list(map(int,input().split()))

op=0

for i in range(N-1):
    s=a[i]+a[i+1]
    opc=max(0,s-x)
    a[i+1]=max(0,a[i+1]-opc)
    op+=opc

print(op)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
a = [int(i) for i in input().split()]
ans = 0
for i in range(n-1):
    if a[i] + a[i+1] <= x: continue
    ans += a[i] + a[i+1] - x
    a[i+1] = max(0,x - a[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
MOD = 10**9+7

n,x = map(int,input().split())
a = list(map(int,input().split()))
d = []
ans = 0
for i in range(n-1):
    d = a[i+1] + a[i]
    if d>=x:
        if a[i+1]>=d-x:
            a[i+1] = a[i+1] - (d-x)
            ans += d-x
        else:
            a[i+1] = 0
            a[i] -= d-x-a[i+1]
            ans += d-x-a[i+1]
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0

for i in range(1, N):
    s = A[i] + A[i-1]
    if s > x:
        y = s-x
        if A[i] > y:
            A[i] -= y
            A[i-1] -= y
            ans += y
        else:
            z = y - A[i]
            A[i] = 0
            A[i-1] -= A[i]
            A[i-1] -= z
            if i >= 2:
                A[i-2] -= z
            ans += y
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(n-1):
    if a[i]+a[i+1]>x:
        ans+=a[i]+a[i+1]-x
        if a[i]+a[i+1]-x<=a[i+1]:
            a[i+1]-=a[i]+a[i+1]-x
        else:
            a[i]=x
            a[i+1]=0
print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
i = 0
while i < N-1:
  if A[i]+A[i+1] > x:
    d = A[i]+A[i+1]-x
    ans += d
    A[i+1] = 0 if A[i+1] < d else A[i+1]-d
  i += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    if A[0] > x:
        res += A[0] - x
        A[0] = x

    for i in range(1, n):
        if A[i - 1] + A[i] > x:
            res += A[i] + A[i - 1] - x
            A[i] -= A[i] + A[i - 1] - x

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
lst = [int(x) for x in input().split()]
total = sum(lst)
for i in range(N - 1):
    if lst[i] + lst[i + 1] > x:
        lst[i + 1] = lst[i + 1] - min(max(lst[i] + lst[i + 1] - x, 0), lst[i + 1])
    if lst[i] + lst[i + 1] > x:
        lst[i] = lst[i] - min(max(lst[i] + lst[i + 1] - x, 0), lst[i])
print(total - sum(lst))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
A = list(map(int,input().split()))
Arev = A[::-1]
ans = 0
if A[0] > x:
    ans += A[0] - x
    A[0] = x
for i in range(1, n):
    if A[i] + A[i-1] > x:
        c = A[i] + A[i-1] - x
        A[i] -= c
        ans += c

ans2 = 0
if Arev[0] > x:
    ans2 += Arev[0] - x
    Arev[0] = x
for i in range(1, n):
    if Arev[i] + Arev[i-1] > x:
        c = Arev[i] + Arev[i-1] - x
        Arev[i] -= c
        ans2 += c

print(min(ans, ans2))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
a = inl()
sm = 0
if a[0]>x:
    sm = a[0]-x
    a[0] = x
for i in range(1,n):
    d = a[i]+a[i-1]-x
    if d>0:
        a[i] -= d
        sm += d
print(sm)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
if A[0] > x:
  ans = A[0] - x
  A[0] = x
for i in range(N-1):
    if A[i] + A[i+1] > x:
        ans += A[i]+A[i+1]-x
        A[i+1] = x-A[i]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


def solve(N: int, x: int):
    tokens = iterate_tokens()
    a = int(next(tokens))
    s = 0
    for _ in range(N-1):
        new = int(next(tokens))
        if a + new > x:
            s += a + new - x
            new -= min(new, a + new - x)
        a = new
    print(s)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = int(next(tokens))  # type: int
    solve(N, x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0

for i in range(n-1):
    t=a[i]+a[i+1]
    if t>x:
        if t-x<=a[i+1]:
            a[i+1]-=t-x
            ans+=t-x
        else:
            a[i]+=x-a[i+1]
            a[i+1]=0
            ans+=t-x

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lis = list(map(int,input().split()))
ans = 0
for i in range(n-1):
  if lis[i] + lis[i+1] > k:
    num = lis[i+1]+lis[i] -k
    ans += num
    if num >= lis[i+1]:
      num -= lis[i+1]
      lis[i+1] = 0
      lis[i] -= num
    else:
      lis[i+1] -= num
print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
As = list(map(int, input().split()))

# 隣り合う箱の和を取る
# sum_As = [0 for i in range(N-1)]
# for i in range(N-1):
#     sum_As[i] = As[i] + As[i+1]

count = 0
# 両側があふれていたら減らせるだけ減らそう
for i in range(1, N-1):
    if As[i-1]+As[i] > x and As[i]+As[i+1] > x:
        minus = min(As[i], As[i-1]+As[i]-x, As[i]+As[i+1]-x)
        As[i] -= minus
        count += minus

# 片側があふれていたら減らせるだけ減らそう
if As[0]+As[1] > x:
    minus = min(As[0], As[0]+As[1]-x)
    As[0] -= minus
    count += minus

for i in range(1, N-1):
    if As[i-1]+As[i] > x:
        minus = min(As[i], As[i-1]+As[i]-x)
        As[i] -= minus
        count += minus
    if As[i]+As[i+1] > x:
        minus = min(As[i], As[i]+As[i+1]-x)
        As[i] -= minus
        count += minus

if As[N-2]+As[N-1] > x:
    minus = min(As[N-1], As[N-2]+As[N-1]-x)
    As[N-1] -= minus
    count += minus

print(count)

Submission status: Accepted

Solution code:
def solve(n, x, a_list):
    
    ans = 0
    for i in range(len(a_list)-1):
        tmp = a_list[i] + a_list[i+1]
        if tmp > x:
            d = tmp - x
            ans += d
            if a_list[i+1] - d >= 0:
                a_list[i+1] = a_list[i+1] -d
            else:
                a_list[i] = a_list[i] - (d-a_list[i+1])
                a_list[i+1] = 0
    return ans

if __name__ == "__main__":
    n, x = [int(i) for i in input().split()]
    a_list = [int(i) for i in input().split()]
    print(solve(n, x, a_list))

Submission status: Accepted

Solution code:
n , x = map(int, input().split())
a = list(map(int,input().split()))
a2 =[0]*n
for i in range(n):
    if a[i]>x:
        a2[i]=x
    else:
        a2[i] = a[i]
s = 0
for i in range(n-1):
    if a2[i]+a2[i+1]>x:
        a2[i+1]=x-a2[i]
for i in range(n):
    s+=a[i]-a2[i]
print(s)

Submission status: Accepted

Solution code:
n,x = list(map(int, input().split()))
lst = [0]+list(map(int, input().split()))
ans = 0

for i in range(n):
    if lst[i]+lst[i+1]>x:
        ans+=(lst[i]+lst[i+1]-x)
        lst[i+1]-=(lst[i]+lst[i+1]-x)
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
s = a[0]
if a[0] > x:
    ans = (a[0] - x)
    s = x
for i in range(1, n):
    if a[i] + s > x:
        ans += ((a[i] + s) - x)
        s = x - s
    else:
        s = a[i]
print(ans)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,X = map(int,input().split())
A = list(map(int,input().split()))

ans = 0 
if A[0]>X:
    ans = A[0]-X
    A[0] -= ans

for i in range(N-1):
    r = max(A[i]+A[i+1]-X,0)
    A[i+1] -= r
    ans += r

print(ans)

Submission status: Accepted

Solution code:
n,x = list(map(int, input().split()))
a=list(map(int, input().split()))
ans = 0
if(a[0]>x):
    ans+=a[0]-x
    a[0]=x
for i in range(n-1):
    if(a[i]+a[i+1]>x):
        ans += a[i]+a[i+1]-x
        a[i+1] = x - a[i]
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, x = list(map(int, input().split()))
    A = list(map(int, input().split()))
    cnt = 0
    for i in range(N-1):
        if A[i] + A[i+1] > x:
            diff = (A[i] + A[i+1]) - x
            cnt += diff
            if A[i+1] < diff:
                A[i] = diff - A[i+1]
                A[i+1] = 0
            else:
                A[i+1] -= diff
    print(cnt)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [i for i in a]
b[0] = min(b[0], x)
for i in range(1, n):
    if b[i-1] + b[i] > x:
        b[i] = x - b[i-1]
print(sum(a) - sum(b))

Submission status: Accepted

Solution code:
N,x = map(int,input().split())
A = list(map(int,input().split()))
A_org = sum(A)
if A[0]>x:
	A[0]=x
for i in range(N-1):
	if A[i]+A[i+1]>x:
		A[i+1] = x-A[i]

print(A_org-sum(A))

Submission status: Accepted

Solution code:
N,x = map(int,input().split())
A = list(map(int,input().split()))
A_org = sum(A)
if A[0]>x:
	A[0]=x
for i in range(N-1):
	if A[i]+A[i+1]>x:
		A[i+1] = x-A[i]

print(A_org-sum(A))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    total = a[i] + a[i + 1]
    if total > x:
        a[i] -= max(0, total - x - a[i + 1])
        a[i + 1] = max(0, a[i + 1] - (total - x))
    ans += max(total - x, 0)
print(ans)

Submission status: Accepted

Solution code:
n, border = map(int, input().split())

boxes = [int(x) for x in input().split(' ')]

count = 0
for  i in range(n):
    if(boxes[i] > border):
        count += boxes[i] - border
        boxes[i] = border

for i in range(n-1):
    if(boxes[i] + boxes[i+1] > border):
        count += boxes[i] + boxes[i+1] - border
        boxes[i+1] -= boxes[i] + boxes[i+1] - border
        
print(count)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N, x = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    ans = 0
    for i, a in enumerate(A):
        if a > x:
            ans += a - x
            A[i] = x
    
    pre = 0
    for i, a in enumerate(A):
        if pre + a > x:
            A[i] = x - pre
            ans += a - A[i]
        pre = A[i]
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def LI(): return list(map(int,input().split()))
N,x = LI()
a = LI()
ans = 0
for i in range(N-1):
    if a[i]+a[i+1]>x:
        if a[i]>x:
            ans += a[i+1]
            a[i+1] = 0
            ans += a[i]-x
        else:
            ans += a[i+1]-(x-a[i])
            a[i+1] = x-a[i]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, x = LI()
a = LI()
ans = 0
for i in range(n):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x
    if i < n-1:
        if a[i] + a[i+1] > x:
            ans += (a[i] + a[i+1]) - x
            a[i+1] = x - a[i]
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    if a[i]>x:
        ans+=a[i]-x
        a[i]=x
for i in range(n-1):
    b=a[i]+a[i+1]
    if b>x:
        ans+=b-x
        a[i+1]-=b-x
print(ans)

Submission status: Accepted

Solution code:
N,x=map(int, input().split())
A=list(map(int, input().split()))
ans=0
ans+=max(0,A[0]-x)
A[0]=min(A[0],x)
if A[0]+A[1]>x:
    ans+=A[1]-(x-A[0])
    A[1]=x-A[0]
ans+=max(0,A[-1]-x)
A[-1]=min(A[-1],x)
if A[-2]+A[-1]>x:
    ans+=A[-2]-(x-A[-1])
    A[-2]=x-A[-1]
for i in range(1,N-1):
    if A[i-1]+A[i]>x:
        ans+=A[i]-(x-A[i-1])
        A[i]=x-A[i-1]
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, X = map(int,input().split())
    A = [0] + list(map(int, input().split()))
    ans = 0
    #A =[]*N個、for i in range(N-1)でやると、初項がXより大きい場合に対応できない。
    #より正確にいうと、A =[3, 3, 2] X = 1のようなケース。 A1>A3かつ A1+A2>X かつ　A2+A3 > Xのとき
    for i in range(N):
        diff = A[i] + A[i+1] - X
        if diff > 0:
            A[i+1] -= diff
            ans += diff
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 0
    if A[0] > x:
        ans += A[0] - x
        A[0] = x

    for i in range(n - 1):
        j = i + 1
        if j < n and A[i] + A[j] > x:
            diff = A[i] + A[j] - x
            ans += diff
            A[j] -= diff
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    N, L = map(int, input().split())
    *a, = map(int, input().split())

    def solve(a):
        dq = deque()
        s = 0
        ans = 0
        for x in a:
            if len(dq) > 1:
                t = dq.popleft()
                s -= t
            eat = max(0, s + x - L)
            if eat:
                x -= eat
                ans += eat
            s += x
            dq.append(x)
        return ans

    ans =solve(a) # reversed(a)確認しないとどうなるか

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    N, L = map(int, input().split())
    *a, = map(int, input().split())

    def solve(a):
        dq = deque()
        s = 0
        ans = 0
        for x in a:
            if len(dq) > 1:
                t = dq.popleft()
                s -= t
            eat = max(0, s + x - L)
            if eat:
                x -= eat
                ans += eat
            s += x
            dq.append(x)
        return ans

    ans = min(solve(a), solve(reversed(a)))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x = map(int, input().split())
a = list(map(int, input().split()))

ans = 0

for i in range(0, n-1):
    if a[i] + a[i+1] > x:
        ooi = a[i] + a[i+1] - x
        if ooi < a[i+1]:
            a[i+1] -= ooi
        else:
            a[i] -= (ooi-a[i+1])
            a[i+1] = 0
        ans += ooi

print(ans)