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):
    sub = max(0, A[i] + A[i+1] - X)
    ans += sub
    A[i+1] = max(0, A[i+1] - sub)

print(ans)

Submission status: Accepted

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

nc = 0

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

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

print(nc)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
total=sum(a)
if k<a[0]:
    a[0]=k
for i in range(n-1):
    if k<a[i]+a[i+1]:
        a[i+1]=k-a[i]
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(len(a)):
    if a[i]>x:
        ans+=a[i]-x
        a[i]=x
nlist=[]
for i in range(1,len(a)):
    nlist.append(a[i]+a[i-1])

for i in range(len(nlist)):
    if nlist[i]>x:
        d=nlist[i]-x
        ans+=nlist[i]-x
        nlist[i]=x
        if i+1<len(nlist):
            nlist[i+1]-=d
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 = ans+(a[0]-x)
    a[0]=x

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

Submission status: Accepted

Solution code:
ri=(raw_input()).split(" ")
n=int(ri[0])
x=int(ri[1])
a=(raw_input()).split(" ")
for i in range(n):
    a[i]=int(a[i])

#print(a)

eat=0

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

#print(a)
print(eat)

Submission status: Accepted

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

res = 0

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

print(res)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import numpy as np
def readLine_int_list():return list(map(int, stdin.readline().split()))



def main():
    n, x = readLine_int_list()

    _a = readLine_int_list()
    a = _a.copy()
    
    for i in range(n-1):
        if a[i] + a[i+1] > x:
            
            if a[i] > x:
                a[i] = x
            
            if x - a[i] >= 0:
                if a[i] == 0:
                    a[i+1] = x
                elif a[i] > 0:
                    a[i+1] = x-a[i]
    print(np.sum(np.array(_a) - np.array(a)))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, M = map(int, input().split())
cnt = 0
a = list(map(int, input().split())) + [0]
for i in range(N):
    if a[i] + a[i+1] > M:
        o = a[i] + a[i+1] - M
        cnt += o
        if o > a[i+1]:
            o -= a[i+1]
            a[i+1] = 0
            # a[i] -= o
        else:
            a[i+1] -= o
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):
  L=A[i]-x
  if L>0:
    A[i]=x
    ans+=L
for i in range(1,N):
  M=A[i]+A[i-1]-x
  if M>0:
    A[i]-=M
    ans+=M
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):
    if a[i-1] + a[i] > x:
        rem = a[i-1] + a[i] - x
        cnt += rem
        if rem >= a[i]:
            a[i - 1] -= rem - a[i]
            a[i] = 0
        else:
            a[i] -= rem
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
r = range

n, x = map(int, input().split())
# n行x列の配列を取得
a = np.array(list(map(int, input().split())))

ret = 0
for i in r(1, n):
    for j in r(2):
        if a[i] + a[i-1] > x:
            tmp = min(a[i-j], a[i] + a[i-1] - x)
            ret += tmp
            a[i-j] -= tmp

print(ret)

Submission status: Accepted

Solution code:
n,k=map(int,raw_input().split())
N=map(int,raw_input().split())
ans=0
for i in range(1,n):
    if N[i]+N[i-1]>k:
        ans+=min(N[i]+N[i-1]-k,N[i])
        N[i]-=min(N[i]+N[i-1]-k,N[i])
    if N[i]+N[i-1]>k:
        ans+=min(N[i]+N[i-1]-k,N[i-1])
        N[i-1]-=min(N[i]+N[i-1]-k,N[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(len(a) - 1):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x

    if a[i] + a[i+1] > x:
        prev = a[i+1]
        a[i+1] -= a[i] + a[i+1] - x
        ans += prev - 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] + a[1] > x and a[1] < x:
  ans = a[1]
  a[1] = 0
  ans += a[0] - x
  a[0] = x

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

print(ans)

Submission status: Accepted

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

for i in range(len(a) - 1):
    s = a[i] + a[i + 1]
    if x < s:
        sub = s - x
        a[i + 1] = max(0, a[i + 1] - sub)
        cnt += sub
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(len(a) - 1):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x

    if a[i] + a[i+1] > x:
        prev = a[i+1]
        a[i+1] -= a[i] + a[i+1] - x
        ans += prev - a[i+1]

print(ans)

Submission status: Accepted

Solution code:
N, x = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 0
if a[0] > x:
    ans += a[0] - x
    a[0] = x
if a[-1] > x:
    ans += a[-1] - x
    a[-1] = x
for i in xrange(N - 1):
    if a[i] + a[i + 1] > x:
        ans += a[i + 1] - (x - a[i])
        a[i + 1] = x - a[i]
print ans

Submission status: Accepted

Solution code:
# coding: utf-8
num_box, num_ans_candy = map(int, input().split())
l_box = list(map(int, input().split()))

eat_counter = 0
for index in range(num_box - 1):
    double_candy = l_box[index] + l_box[index + 1]
    if double_candy > num_ans_candy:
        num_eat_candy = double_candy - num_ans_candy
        if l_box[index + 1] < num_eat_candy:
            num_eat_candy -= l_box[index + 1]
            eat_counter += l_box[index + 1]
            l_box[index + 1] = 0
            l_box[index] -= num_eat_candy
        else:
            l_box[index + 1] -= num_eat_candy
        eat_counter += num_eat_candy

print(eat_counter)

Submission status: Accepted

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

    result = 0


    for i in range(1,N):
        tot = a[i] + a[i-1]
        if tot>x:
            result += (tot - x)
            tmp = a[i]
            a[i] =  max(0, a[i]- tot +x)
            if a[i] == 0:
                a[i-1] = min(x,a[i-1])

    print(result)

Submission status: Accepted

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

print ans

Submission status: Accepted

Solution code:
NandX=list(map(int,input().split()))
N=NandX[0]
x=NandX[1]
A=list(map(int,input().split()))

ans = 0
for i in range(1,N):
    s = A[i]+A[i-1]
    if x<s:
        dif = s-x
        #オーバーしてる分がA[i]より小さい
        if dif<=A[i]:
            A[i]-=dif
            ans+=dif
        #オーバーしてる分がA[i]より大きい
        #(A[i]を減らすだけでは対処できない)
        else:
            A[i-1]=dif-A[i]
            A[i]=0
            ans+=dif

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-

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

cnt = 0
for i in range(N-1):
    tmp = (a[i] + a[i+1]) - x
    if tmp < 0:
        continue
    cnt += tmp
    if a[i+1] >= tmp:
        a[i+1] -= tmp
    else:
        a[i] -= tmp - a[i+1]
        a[i+1] = 0

# print(a)
print(cnt)

Submission status: Accepted

Solution code:
n, x = map(int,input().split())
a = list(map(int,input().split()))
a_min = [0] * n

if a[0] > x:
    a_min[0] = x
else:
    a_min[0] = a[0]

ans = a[0] - a_min[0]

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

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
i=0
num=0

if a[0] > x:
        ans=a[0]-x
        a[0]=a[0]-ans
        num=num+ans
while i<n-1:
        if a[i] + a[i+1] > x:
                ans=a[i] + a[i+1] - x
                a[i+1]=a[i+1]-ans
                num=num+ans
        else:
                i=i+1

print num

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):
    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)

Submission status: Accepted

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
counter = 0
for i in range(n-1):
    decrease = a[i] + a[i+1] - x
    if decrease > 0:
        counter += decrease
        if a[i+1] >= decrease:
            a[i+1] -= decrease
        else:
            a[i] -= decrease - a[i+1];
            a[i+1] = 0
print counter

Submission status: Accepted

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

count = 0

i = 0
pre = 0
while i < N:
    if pre + a[i] > x:
        pre = x - pre
        count += a[i] - pre
    else:
        pre = a[i]
    i += 1

print(count)

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

Submission status: Accepted

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

c = 0

for i in xrange(1, len(a)):
    while a[i] + a[i-1] > x:
        if a[i] > 0:
            c += min(a[i], a[i] + a[i-1] - x)
            a[i] -= min(a[i], a[i] + a[i-1] - x)
        else:
            c +=  a[i] + a[i-1] - x
            a[i-1] -=  a[i] + a[i-1] - x
print c

Submission status: Accepted

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

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

Submission status: Accepted

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

prev = a_s.pop()
result = max(prev - x, 0)
prev -= result
while a_s:
    cur = a_s.pop()
    if prev + cur > x:
        cur_res = prev + cur - x
        cur -= cur_res
        result += cur_res
    prev = cur

print(result)

Submission status: Accepted

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

res = 0
for i in range(len(a)-1):
    b = a[i]+a[i+1]
    if x < b:
        res += b-x
        a[i+1] -= min(b-x, a[i+1])

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

def solve(N,x,a):
	a.insert(0,0)
	count=0
	for i in range(len(a)-1):
		if a[i]+a[i+1]>x:
			eat=a[i+1]+a[i]-x
			count+=eat
			a[i+1]-=eat
	return(count)


print(solve(N, x, a))

Submission status: Accepted

Solution code:
N, x = [int(t) for t in input().split()]
a = [int(t) for t in input().split()]

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

for i in range(1, len(a)):
    much = a[i] + a[i-1] - x
    if 0 < much <= a[i]:
        ans += much
        a[i] -= much
    elif a[i] < much:
        t = a[i]
        a[i] = 0
        ans += t
        much -= t
        a[i-1] -= much
        ans += much
print(ans)

Submission status: Accepted

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

# greedy from left
res = 0
for i in range(1, N):
    if A[i] + A[i-1] > x:
        if x > A[i-1]:
            res += A[i] - x + A[i-1]
            A[i] = x - A[i-1]
        else:
            res += A[i]
            A[i] = 0
            res += A[i-1] - x
            A[i-1] = x
    else:
        pass

print res

Submission status: Accepted

Solution code:
n,x = map(int, input().split())
a = list(map(int, input().split()))
b = a[::-1]

def solve(a):
    total = 0
    if a[0] > x:
        total += a[0]-x
        a[0] = x

    for i in range(1, n):
        if a[i-1] + a[i] > x:
            d = (a[i-1] + a[i]) - x
            total += d
            a[i] = max(0, a[i] - d)
    return total

print(min(solve(a), solve(b)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

N, x = ln()
X = ln()

A = X[:]
result = 0
for i in xrange(1, N):
    if A[i] + A[i - 1] > x:
        diff = A[i] + A[i - 1] - x
        
        A[i] -= diff
        A[i] = max(A[i], 0)
        result += diff

print result

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=0
if a[0]+a[1]>x:
    ans+=a[0]+a[1]-x
    a[1]=max(a[1]-ans,0)
for i in xrange(1,n-1):
    if a[i]+a[i+1]>x:
        ans+=a[i]+a[i+1]-x
        tmp=a[i]+a[i+1]-x
        a[i+1]=max(a[i+1]-tmp,0)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N,x = map(int,input().split())
As = list(map(int,input().split()))
Bs = As[:]
for i in range(1,N):
    s = As[i] + As[i-1]
    if s > x:
        As[i] = max(0, As[i] - (s - x))
    s = As[i] + As[i-1]
    if s > x:
        As[i-1] = As[i-1] - (s - x)
ans = sum(b - a for a, b in zip(As, Bs))
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, raw_input().split())
A = map(int, raw_input().split())
ans = 0
if x < A[0]:
    ans += A[0] - x
    A[0] = x
if x < A[-1]:
    ans += A[-1] - x
    A[-1] = x
for i in xrange(1, n):
    if x - A[i-1] < A[i]:
        ans += A[i] - (x - A[i-1])
        A[i] = x - A[i-1]
print ans

Submission status: Accepted

Solution code:
from sys import stdin
n,m = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
ans = 0
if a[0] > m:
    ans += a[0] - m 
    a[0] = m 
for i in xrange(1,n):
    cur = a[i-1] + a[i]
    if cur >m:
        ans += cur - m 
        a[i] = m - a[i-1]
print ans

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, x) = reads()
a = [0] + reads()

result = 0

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

print(result)

Submission status: Accepted

Solution code:

def main():
    n, x = map(int, input().split())
    al = list(map(int, input().split()))
    ans = 0
    for i in range(n - 1):
        l, r = i, i + 1
        exc = al[l] + al[r] - x
        if exc <= 0:
            continue
        rd = min(al[r], exc)
        al[r] -= rd
        ans += rd
        exc -= rd
        if exc > 0:
            al[l] -= exc
            ans += exc
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in xrange(N-1):
    if A[i] + A[i+1] > x:
        ans += A[i] + A[i+1] - x
        A[i+1] -= A[i] + A[i+1] - x
    #print A, ans

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

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


def main():
    n,x = list(map(int, input().split()))
    a = list(map(int, input().split()))
    r = 0
    for i in range(n-1):
        wa = a[i] + a[i+1]
        if wa <= x:
            continue
        sa = wa - x
        r += sa
        if sa <= a[i+1]:
            a[i+1] -= sa
        else:
            a[i+1] = 0
    return r


print(main())

Submission status: Runtime Error

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

a = list(map(int, input().split())
before = sum(a)

for i in range(n-1):
	while a[i] + a[i+1] > x:
		a[i+1] -= 1
		
after = sum(a)

print(after - before)

Submission status: Runtime Error

Solution code:
import sys

n, x, *lst = map(int, sys.stdin.read().split())
re1 = 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: Runtime Error

Solution code:
/*
         ██╗ ██████╗ ██╗███╗   ██╗    ██╗   ██╗███████╗
         ██║██╔═══██╗██║████╗  ██║    ██║   ██║██╔════╝
         ██║██║   ██║██║██╔██╗ ██║    ██║   ██║███████╗
    ██   ██║██║   ██║██║██║╚██╗██║    ██║   ██║╚════██║
    ╚█████╔╝╚██████╔╝██║██║ ╚████║    ╚██████╔╝███████║
     ╚════╝  ╚═════╝ ╚═╝╚═╝  ╚═══╝     ╚═════╝ ╚══════╝
*/
//password:+BdCHpO8dQvpo5fnV3/u
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int main() {
    ll n,x;
    cin>>n>>x;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int ans=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]+a[i+1]>x)
        {
            int res=a[i]+a[i+1]-x;
            ans+=res;
            if(2<=i+1<=n-1)
            {
                if(a[i+1]>=res) a[i+1]-=res;
                else
                {
                    a[i+1]=0;
                    a[i]-=res-a[i+1];
                } 
            } 
        }
    }
    cout<<ans;
    return 0;
}

Submission status: Runtime Error

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

s = [0] * (N-1)
for i in range(N-1):
    s[i] = a[i] + a[i+1]

ans = 0
for i in range(N-1):
    if i != N-2:
        while s[i] > x:
            b = s[i]-x 
            s[i] -= min(b, a[i])
            s[i+1] -= min(b,a[i]) 
            ans += min(b,a[i]) 
    else:
        while s[i] > x:
            a = s[i]-x 
            s[i] -= min(b,a[i])
            ans += min(b,a[i])

print(ans)

Submission status: Runtime Error

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

s = [0] * (N-1)
for i in range(N-1):
    s[i] = a[i] + a[i+1]

ans = 0
for i in range(N-1):
    if i != N-2:
        while s[i] > x:
            b = s[i]-x 
            s[i] -= min(b, a[i+1])
            s[i+1] -= min(b,a[i+1]) 
            ans += min(b,a[i+1]) 
    else:
        while s[i] > x:
            a = s[i]-x 
            s[i] -= min(b,a[i+1])
            ans += min(b,a[i+1])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import heapq
from math import sqrt
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def calc(b1, b2):
    x1, y1, r1 = b1
    x2, y2, r2 = b2
    d = sqrt((x1-x2)**2+(y1-y2)**2)
    return max(d-(r1+r2), 0)


sx, sy, gx, gy = map(int, input().split())
N = int(input())
barriers = [[sx, sy, 0]] + [list(map(int, input().split()))
                            for _ in range(N)]+[[gx, gy, 0]]

mat = [[0]*(N+2) for _ in range(N+2)]

for row in range(N+2):
    for col in range(row+1, N+2):
        d = calc(barriers[row], barriers[col])
        mat[row][col] = d
        mat[col][row] = d

# 視点からの距離
dist = [float('inf')]*(N+2)
dist[0] = 0

# 最短経路での一つ前のノード
prev = defaultdict(lambda: None)

Q = []
# Q->[dist from　start,node])
heapq.heappush(Q, (0, 0))

while Q:
    dist_to_node, node = heapq.heappop(Q)
    if dist[node] < dist_to_node:
        continue
    else:
        for v in range(N+2):
            weight = mat[node][v]
            alt = dist_to_node+weight
            if dist[v] > alt:
                dist[v] = alt
                prev[v] = node
                heapq.heappush(Q, (alt, v))
print(dist[-1])

Submission status: Runtime Error

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

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Submission status: Runtime Error

Solution code:
N,x=map(int,input().split(' '))
A=list(map(int,input().split(' ')))
B=[a for a in A]
if N==2:
	print(A[0]+A[1]-x)
else:
	for i in range(N-3):
		B[i+1] -= min(B[i+1], max(0,(B[i]+B[i+1]-x)))
		B[i] -= max(B[i]-x, 0)
	B[-2] -= min(B[-2], max(0, (B[-3]+B[-2]-x), (B[-1]+B[-2]-x)))
	B[-3] -= max(0, (B[-3]-x))
	B[-1] -= max(0, (B[-1]-x))
	print(sum[A[i]-B[i] for i in range(N)])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,x=map(int,input().split(' '))
A=list(map(int,input().split(' ')))
B=[a for a in A]
if N==2:
	print(A[0]+A[1]-x)
else:
	for i in range(N-3):
		B[i+1] -= min(B[i+1], max(0,(B[i]+B[i+1]-x)))
		B[i] -= max(B[i]-x, 0)
B[-2] -= min(B[-2], max(0, (B[-3]+B[-2]-x), (B[-1]+B[-2]-x)))
B[-3] -= max(0, (B[-3]-x))
B[-1] -= max(0, (B[-1]-x))
print(sum(A)-sum(B))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def dijkstra(s):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [[Xs,Ys,0],[Xt,Yt,0]]
for i in range(2,n+2):
    p.append(list(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)

n += 2

res = dijkstra(0)
print(res[1])

Submission status: Runtime Error

Solution code:

n, x = map(int, input().split())
l = list(map(int, input().split()))
total = 0

for i in range(n - 1):
    sub = l[i] + l[i+1]
    if sub > x:
        total += sub - x
        l[i+1] -= sub - x
        if l[i+1] > x:
            l[i] -= l[i+1] - x
            total += l[i+1 - x]




print(total)

Submission status: Runtime Error

Solution code:
from heapq import heapify,heappop,heappush
xs,ys,xt,yt=map(int,input().split())
P=[]
inf=float("inf")
P.append((xs,ys,0))
N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  P.append((x,y,r))
P.append((xt,yt,0))
G=[set() for i in range(N+2)]
for i in range(N+2):
  for j in range(N+2):
    if i!=j:
      x1,y1,r1,x2,y2,r2=P[i][0],P[i][1],P[i][2],P[j][0],P[j][1],P[j][2]
      d=((x1-x2)**2+(y1-y2)**2)**(1/2)
      if d<=r1+r2:
        G[i].add((0,j))
      else:
        G[i].add((d-r1-r2,j))

def dijkstra(s,n,links):
  cost=[inf]*n
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    for c,p in links[hp]:
      if c+hc<cost[p]:
        cost[p]=c+hc
        heappush(heap,(cost[p],p))
  return cost        

c=dijkstra(0,N+2,G)
print(c[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(N - 1):
    if(candy[i] + candy[i + 1] > x):
        ex = candy[i] + candy[i + 1] - x
        eat += ex
        if(candy[i + 1] >= ex):
            candy[i + 1] -= ex
        else:
            candy[i] -= ex - cndy[i + 1]
            candy[i + 1] = 0
print(eat)

Submission status: Runtime Error

Solution code:
from heapq import heappop, heappush

INF = 10 ** 20

xs, ys, xt, yt = map(int, input().split())
N = int(input())
circle = [list(map(int, input().split())) for _ in range(N)]
circle = [[xs, ys, 0]] + circle + [[xt, yt, 0]]
edges_lst = [[] for _ in range(N + 2)]
for i, (x1, y1, r1) in enumerate(circle):
    for j, (x2, y2, r2) in enumerate(circle[i + 1:]):
        j += i + 1
        d = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** .5
        dist = max(0, d - r1 - r2)
        edges_lst[i].append((j, dist))
        edges_lst[j].append((i, dist))

def dijkstra():
    que = []
    heappush(que, (0, 0))
    dist_lst = [INF] * (N + 2)
    dist_lst[0] = 0
    while que:
        dist, node = heappop(que)
        for to, cost in edges_lst[node]:
            if dist_lst[to] > cost + dist:
                dist_lst[to] = cost + dist
                heappush(que, (cost + dist, to))
    return dist_lst[-1]

print('{:.10f}'.format(dijkstra()))

Submission status: Runtime Error

Solution code:
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
x = int(arr_data[0][1])

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