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:
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
        A[i+1] = max(0,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-1):
  if a[i]<=x:
    if a[i]+a[i+1]<=x:
      continue
    else:
      ans+=a[i+1]-(x-a[i])
      a[i+1]=x-a[i]
  else:
    ans=a[i]-x
    a[i]=x
    ans+=a[i+1]
    a[i+1]=0
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
for i in range(1, n):
    tmp = max(0, A[i-1] + A[i] - x)
    A[i] = max(0, A[i]-tmp)
    cnt += tmp

print(cnt)

Submission status: Accepted

Solution code:
n, x =map(int, input().split())
a = list(map(int, input().split()))
s = [0]*(n-1)
ans=0
for i in range(1, n-1):
  temp = a[i]
  left = a[i-1]+temp
  right = a[i+1]+temp
  if left>x and right>x:
    t=min(right, left)-x
    if t<=a[i]:
      ans+=t
      a[i]-=t
    else:
      ans+=a[i]
      a[i]=0
    
#print(a)
#print(" ")
for i in range(n-1):
  temp = a[i]+a[i+1]
  if temp>x:
    t = temp-x
    ans+=t
    a[i]-=t
    if a[i]<0:
      t = 0-a[i]
      a[i+1]-=t
#print(a[-3:])
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):
  a,b = A[i],A[i+1]
  if a+b > x:
    if b-(x-a-b) >= 0:
      ans += a+b-x
      A[i+1] -= (a+b-x)
      A[i+1] = max(0,A[i+1])
    else:
      A[i+1] = 0
      A[i] -= ((x-a-b)-b)
      ans += (a-A[i])+(b-A[i+1])

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
ar=list(map(int,input().split()))
pr,ans=0,0
for e in ar:
    if(pr+e>x):
        l=pr+e-x
        ans+=l
        e-=l
    pr=e
print(ans)

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(1,n):
    if a[i]+a[i-1]>x:
        t=x-a[i-1]
        ans+=a[i]-t
        a[i]=t
        
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):
    s = a[i] + a[i+1]
    if s > x:
        ans += s - x
        a[i+1] = max(0, a[i+1]-(s-x))

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] > x:
        ans += a[i]-x
        a[i] = x
    if a[i]+a[i+1] > x:
        ans += a[i+1] + a[i] -x
        a[i+1] = x - a[i]
# print(a)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,x,*a = map(int,read().split())

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

Submission status: Accepted

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

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

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 - 1):
    if A[i] + A[i + 1] > x:
        d = A[i] + A[i + 1] - x
        ans += d
        if A[i + 1] - d < 0:
            A[i] -= d - A[i + 1]
            A[i + 1] = 0
        else:
            A[i + 1] -= d

print(ans)

Submission status: Accepted

Solution code:
import sys

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

ans=0
for i in range(n-1):
    next_sum=A[i]+A[i+1]
    if next_sum>x:
        if next_sum-x<=A[i+1]:
            A[i+1]=A[i+1]-(next_sum-x)
            ans=ans+(next_sum-x)
        else:
            ans=ans+A[i+1]
            if next_sum-x-A[i+1]<=A[i]:
                A[i]=A[i]-(next_sum-x-A[i+1])
                ans=ans+(next_sum-x-A[i+1])
            else:
                print(0)
                sys.exit()
            A[i+1]=0
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
import sys
import math
from collections import Counter, defaultdict, deque
import copy

# from itertools import product, permutations, combinations, combinations_with_replacement
# from itertools import accumulate
# from operator import itemgetter
# from bisect import bisect_bound_list,bisect
# from heapq import heappop,heappush
# from math import ceil,floor
# from copy import deepcopy
# from heapq import heappop,heappush,heapify
# import heapq


# def combinations(n, r):
# 	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# def gcd(a, b):
# 	if b == 0:
# 		return a
# 	else:
# 		return gcd(b, a%b)
 
# def lcm(a, b):
# 	return a // gcd(a, b) * b

# l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
# c = Counter(l)

# d = defaultdict(int)

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

# リストの要素を改行を挟んで表示する
p2D = lambda x: print(*x, sep="\n")
# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())

def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())

# 入力全てを整数に変換したものの配列を受け取る
# def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI(): return list(map(lambda x:int(x), sys.stdin.readline().split()))
def HI(): return list(map(lambda x:int(x)*(-1), sys.stdin.readline().split()))

# import numpy as np
# R, C = MI()
# S = np.array([LI() for _ in range(R)])
# ans = 0
# for i in range(2**R):
#     r = np.array([[i >> r & 1 for r in range(R)]])
#     X = np.sum(S.T ^ r, axis=1)
#     ans = max(ans, np.sum(np.maximum(X, R-X)))
# print(ans)


N,x = MI()
A = LI()
cnt = 0
for i in range(len(A)):
    if i > 0:
        if A[i-1] + A[i] > x:
            cnt += A[i-1] + A[i] - x
            A[i] = A[i] - (A[i-1] + A[i] - x)
    else:
        if A[i] > x:
            cnt += A[i] - x
            A[i] = x
print(cnt)

Submission status: Accepted

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

print(cnt)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

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

    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(n-1):
  p = a[i] + a[i+1] - x
  if p > 0:
    ans += p
    a[i+1] = max(0, a[i+1]-p)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, x = Is()
A = LI()
ans = 0
for i in range(n-1):
    y = A[i]+A[i+1] - x
    if y > 0:
        ans += y
        if A[i+1] >= y:
            A[i+1] -= y
        else:
            A[i+1] = 0
            A[i] -= y - A[i+1]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, X = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    before_a, cnt = 0, 0
    for a in A:
        c = max([before_a + a - X, 0])
        before_a = a - c
        cnt += c
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

n, x, *lst = map(int, sys.stdin.read().split())
res = 0
lst.append(0)
for i in range(n, 0, -1):
  tmpsum = lst[i] + lst[i - 1]
  if tmpsum > x:
    res += tmpsum - x
    lst[i - 1] -= tmpsum - x

print(res)

Submission status: Accepted

Solution code:
import sys

n, x, *lst1 = map(int, sys.stdin.read().split())
res1 = 0
lst2 = [0] + lst1
lst1.append(0)
for i in range(n):
  tmpsum = lst2[i] + lst2[i + 1]
  if tmpsum > x:
    res1 += tmpsum - x
    lst2[i + 1] -= tmpsum - x

print(res1)

Submission status: Accepted

Solution code:
import sys

n, x, *lst1 = map(int, sys.stdin.read().split())
res1 = res2 = 0
lst2 = [0] + lst1
lst1.append(0)
for i in range(n):
  tmpsum = lst2[i] + lst2[i + 1]
  if tmpsum > x:
    res1 += tmpsum - x
    lst2[i + 1] -= tmpsum - x

for i in range(n, 0, -1):
  tmpsum = lst1[i] + lst1[i - 1]
  if tmpsum > x:
    res2 += tmpsum - x
    lst1[i - 1] -= tmpsum - x  
print(min(res1, res2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x,*a=map(int,open(0).read().split())
ans=0
for i in range(n-1):
  sur=max(0,a[i]+a[i+1]-x)
  if sur > a[i+1]:
    a[i]-=sur-a[i+1]
    a[i+1]=0
  else:
    a[i+1]-=sur
  ans+=sur
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, x = map(int,input().split())
a = [int(i) for i in input().split()]
ans = max(0,a[0]-x)
now = max(0,a[0]-x)
for i in range(n-1):
  m = a[i]+a[i+1]-now
  if m <= x:
    now = 0
  else:
    now = m - x
    ans += now
    
print(ans)

Submission status: Accepted

Solution code:
A,B = map(int,input().split())
C = list(map(int,input().split()))
ans = 0
for i in range(A-1):
    if B < C[i]+C[i+1]:
        minus = C[i]+C[i+1]-B
        if C[i+1]<minus:
            C[i+1]=0
        else:
            C[i+1]-=minus
        ans += minus
print(ans)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

target = [x for _ in range(n)]

cnt = 0

for i in range(n - 1):
	if a[i] + a[i + 1] > target[i]:
		tmp = min(a[i + 1], a[i] + a[i + 1] - target[i])
		cnt += tmp
		a[i + 1] -= tmp

if a[0] + a[1] > target[0]:
	cnt += a[0] - target[0]
	a[0] -= a[0] - target[0]

print(cnt)

Submission status: Accepted

Solution code:
N, x = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A
total = sum(A)

for i in range(1, N+1):
    if A[i-1] + A[i] > x:
        tmp = (A[i-1]+A[i]) - x
        A[i] -= tmp
        
print(total - sum(A))

Submission status: Accepted

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

a = [0]+a

ans = 0

for i in range(n):
    if a[i]>x:
        ans += a[i]-x
        a[i]=x
    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()))

cnt = 0
for i in range(N-1):
    if(a[i] + a[i+1] > x):
        if(a[i] > x):
            cnt += (a[i]-x)+a[i+1]
            a[i+1] = 0
        else:
            cnt += a[i]+a[i+1]-x
            a[i+1] -= a[i]+a[i+1]-x
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 - 1):
    S = A[i + 1] + A[i]
    if S > x:
        ans += S - x
        if A[i + 1] > S - x:
            A[i + 1] -= S - x
        else:
            A[i + 1] = 0

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools
from fractions import gcd
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N,X = LI()
A = LI()
ans = 0
for i in range(1, N):
    if A[i-1] + A[i] > X:
        sa = (A[i-1]+A[i]) - X
        if A[i] >= sa:
            A[i] -= sa
        else:
            A[i] = 0
        ans += sa
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 x  < a[i] + a[i+1]:
        ans += (a[i]+a[i+1])-x
        if a[i] <= x:
            a[i+1] = x - a[i]
        else:
            a[i+1] = 0

#print(a)
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(1,N):
	tmp = max(0, A[i]+A[i-1]-x)
	cnt += tmp
	if A[i] >= tmp:
		A[i] -= tmp
	else:
		tmp -= A[i]
		A[i] = 0
		A[i-1] -= tmp

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-1):
    if a[i]+a[i+1]>x:
        ans+=a[i]+a[i+1]-x
        if a[i]<=x:
            a[i+1]=x-a[i]
        else:
            a[i+1]=0
print(ans)

Submission status: Accepted

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

res = 0
for i in range(n-1):
    a1 = al[i]
    a2 = al[i+1]
    if a1+a2>x:
        d = a1+a2-x
        res += d
        if a2>=d:
            al[i+1] -= d
        else:
            al[i+1] = 0

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,x=mii()
arr=limii()
cnt=0

if arr[0]>x:
    cnt+=arr[0]-x
    arr[0]=x

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

Submission status: Accepted

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

t = list(map(int,input().split()))

res = 0

for i in range(n-1):
    if t[i] > x:
        res += t[i]+t[i+1]-x
        t[i] = x
        t[i+1] = 0
    elif t[i]+t[i+1] > x:
        res += t[i+1]+t[i]-x
        t[i+1] = x-t[i]
    #print(t)
print(res)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))

D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''



N, K = map(int, input().split())

A = list(map(int,input().split()))


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

        if A[i-1] <=K:
            #i番目を減らせばよい
            target = K-A[i-1]
            ans += A[i]-target
            A[i] = target

        else:
            # i番目は０にする
            ans += (A[i]+A[i-1]) - K
            A[i] = 0


print(ans)

Submission status: Accepted

Solution code:
# ARC064c
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n - 1):
        ooi = a[i] + a[i + 1] - x
        #print(i, ooi)
        if ooi > 0:
            before = a[i + 1]
            #print(i, 'before', a[i + 1])
            a[i + 1] = max(0, a[i + 1] - ooi)
            #print(i, 'after', a[i + 1])
            ans += before - a[i + 1]
            #print(i, 'ans', ans)

            ooi = a[i] + a[i + 1] - x
            if ooi > 0:
                before = a[i]
                a[i] = max(0, a[i] - ooi)
                ans += before - a[i]
    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
now = a[0]
if a[0] > x:
    ans += a[0]-x
    now = x
for i in range(1,N):
    if now +a[i] > x:
        ans,now = ans+(a[i]-x+now),x-now
    else:
        now = a[i]
print(ans)

Submission status: Accepted

Solution code:
# ??
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, x = MAP()

a = [0] + LIST() + [0]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

# 反転 (ライツアウト)
# 2回やったら元に戻る

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

ans = 0

if A[0] > X:
    x = X
    ans += A[0] - X
else:
    x = A[0]

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7

def main():
    N,X = cin.mapInt()
    A = cin.mapInt()
    ans = sum(A)
    for i in range(N - 1):
        if A[i + 1] + A[i] <= X:
            continue
        s = A[i + 1] + A[i] - X
        n = min(s,A[i + 1])
        A[i + 1]-=n
        s -= n
        A[i] -= s
    ans = ans - sum(A)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(1,N):
  b = A[i - 1] + A[i]
  if b - x > 0:
    c = b - x
    if c > A[i]:
      d = c - A[i]
      A[i] = 0
      A[i - 1] = A[i - 1] - d
    else:
      A[i] = A[i] - c

print(total - 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:
        if A[i] > x:
            ans += A[i] - x
            A[i] = x

    else:
        if A[i-1] + A[i] > x:
            ans += A[i-1] + A[i] - x
            A[i] = x - A[i-1]

print(ans)

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(1, N):
    if A[i-1] + A[i] <= X:
        continue
    if A[i-1] <= X:
        ans += A[i-1] + A[i] - X
        A[i] = X - A[i-1]
    else:
        ans += A[i] + A[i] - X
        A[i] = 0
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, x, *a = map(int, open(0).read().split())
    
    p_sum_a = sum(a)
    
    if x < a[0]:
        a[0] = x
    
    for i in range(1, N):
        if x < a[i-1] + a[i]:
            a[i] = x - a[i-1]
    
    sum_a = sum(a)
    print(p_sum_a - sum_a)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import copy
N, x = map(int, input().split())
a = [int(i) for i in input().split()]
a2 = copy.copy(a)
s = 0
s2 = 0
for i in range(1, N):
    tmp = max(a[i-1]+a[i]-x, 0)
    a[i] = max(0, a[i]-tmp)
    s += tmp
a = a2
for i in range(N-2, -1, -1):
    tmp = max(a[i+1]+a[i]-x, 0)
    a[i] = max(0, a[i]-tmp)
    s2 += tmp
print(min(s, s2))

Submission status: Accepted

Solution code:
def examC():
    N, x  = LI()
    A = LI()
    ans = 0
    cur = A[0]
    if A[0]>x:
        ans += A[0]-x
        cur = x
    for i in range(1,N):
        if cur+A[i]<=x:
            cur = A[i]
            continue
        ans += cur+A[i]-x
        cur = A[i]-(cur+A[i]-x)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(map(int, input().split()))


def main():
    N, X = read_values()
    A = read_list()

    pre = A[0]
    res = 0
    for i in range(1, N):
        a = A[i]
        count = max(0, (pre + a) - X)
        if count > 0:
            if A[i] < count:
                A[i] = 0
            A[i] = max(0, A[i] - count)
            res += count
        pre = A[i]
    
    print(res)


if __name__ == "__main__":
    main()

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 and x - a[i] >= 0:
        ans += a[i] + a[i + 1] - x
        a[i + 1] = x - a[i]
    elif a[i] + a[i + 1] > x and x - a[i] < 0:
        ans += a[i] + a[i + 1] - x
        a[i + 1] = 0
        a[i] = a[i] - x
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(N):
    if i == 0:
        pass
    else:
        if A[i-1]+A[i] > x:
            ans+=(A[i-1]+A[i]-x)
            A[i] = max(0,x-A[i-1])
            
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:
    sa=A[i-1]+A[i]-x
    ans+=sa
    if A[i]-sa>0:
      A[i]-=sa
    else:
      A[i-1]-=sa-A[i]
      A[i]=0
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)


def main():
    N, x = map(int, input().split())
    A = [int(c) for c in input().split()]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x=[int(i) for i in 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):
        rem =  a[i+1] + a[i] - x
        if(rem<=a[i+1]):
            a[i+1]-=rem
        else:
            rem-=a[i+1]
            ans+=a[i+1]
            a[i]-=rem
            a[i+1]=0
        ans+=rem
print(ans)