Problem:


つらら

 問題

カナダに住む JOI 君の家の軒下には,立派なつららが出来ている.せっかくなので,JOI 君はつららについて調べてみることにした.

JOI 君の家の軒下には N 本(2 ≤ N ≤ 100000 = 105 )のつららが出来ている.これらのつららは一直線上に並んでおり,軒下の左端から i cm(1 ≤ i ≤ N )の位置に i 本目のつららが出来ている.i 本目のつららの長さは最初 ai cm(ai は 1 以上の整数)である.これらのつららは,次のような規則によって伸びていく:

 i 本目のつららは,i − 1 本目のつららと i + 1 本目のつららの両方よりも長い場合にのみ,1 時間につき 1 cm ずつ伸びる(ただし,両端のつららに関しては片方の隣のみ考える.すなわち,1 本目のつららは 2 本目のつららより長ければ伸び,N 本目のつららは N − 1 本目のつららより長ければ伸びる).

 どのつららも,L cm(2 ≤ L ≤ 50000)に達した瞬間に,根元から折れる(折れたつららは,以後長さ 0 cm のつららとみなす)
.

最初の段階で,隣り合う 2 本のつららの長さはすべて異なっている.このとき,十分な時間が経過すれば,N 本すべてのつららが折れて長さ 0 cm となる.JOI 君は,つららがこのような状態になるまでの時間を知りたくなった.

N 本のつららの最初の長さとつららの限界の長さ L が与えられると,すべてのつららが折れるまでにかかる時間を求めるプログラムを作成せよ.

入力

入力の 1 行目には,つららの本数を表す整数 N とつららの限界の長さを表す整数
L が,空白を区切りとしてこの順に書かれている.入力の i + 1 行目 (1 ≤ i ≤ N) に
は, i 本目のつららの最初の長さを表す整数 ai (1 ≤ ai < L) が書かれている.

採点用データのうち,配点の 30% 分については,N ≤
500 かつ L ≤ 
1000 を満
たす.

 出力

出力 は,すべてのつららが折れるまでにかかる時間を表す 1 つの整数のみを含む 1 行からなる.

 入出力例

入力例 1
  

4 6
4
2
3
5

出力例 1

8

例 1 の場合,1, 2, 3, 4 本目のつららは,それぞれ 2, 8, 4, 1 時間後に折れる.した
がって,すべてのつららが折れるまでにかかる時間は 8 時間であるので,8 を出力
する.

入力例 2
  

6 10
3
4
1
9
5
1

出力例 2

15

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4 6
4
2
3
5


Sample output:
8

Submission status: Accepted

Solution code:
import heapq

n,l=map(int,raw_input().split())
a=[[0,0]]+[[0,i] for i in xrange(n)]+[[0,n+1]]
for i in xrange(n):
    en=int(raw_input())
    a[i]=[-en,i]
pq=[]
for i in xrange(n+2):
    heapq.heappush(pq,a[i])
ti=[0]*(n+2)
while 1:
    p,i=heapq.heappop(pq)
    p=-p
    if p==0:break
    ti[i]+=l-p
    a[i][0]=0
    if a[i-1][0]!=0:
        ti[i-1]=max(ti[i-1],ti[i])
    if a[i+1][0]!=0:
        ti[i+1]=max(ti[i+1],ti[i])
print(max(ti))

Submission status: Accepted

Solution code:
n, l = map(int,input().split())
ai = [[int(input()),i] for i in range(n)]

ai.sort(key = lambda x: x[0])
time = [0]*(n+2)
for i in ai:
    idx = i[1]
    time[idx+1] = max(time[idx],time[idx+2]) + l - i[0]

print(max(time))

Submission status: Accepted

Solution code:
n, l = map(int,input().split())
#ai = [[int(input()),i] for i in range(n)]
ai = [[] for _ in range(l)]
for i in range(n):
    ai[int(input())].append(i)
time = [0]*(n+2)

for i in range(l-1,0,-1):
    for j in ai[i]:
        time[j+1] = max(time[j],time[j+2]) + l - i

print(max(time))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

line = raw_input().rstrip().split()
N, L = map(int, line)


def solve2(trr, hour=0):
    N = len(trr)
    if sum(trr) == 0:
        return hour
    elif N == 1:
        trr[0] += 1
    elif N == 2:
        if trr[0] > trr[1]:
            trr[0] += 1
        else:
            trr[1] += 1
    elif N > 2:
        if trr[0] > trr[1]:
            trr[0] += 1
        if trr[N-1] > trr[N-2]:
            trr[N-1] += 1
        for i in xrange(1, N-1):
            if N > 2 and trr[i-1] < trr[i] > trr[i+1]:
                trr[i] += 1
    return solve(map(lambda t: 0 if t == L else t, trr), hour+1)


def solve(trr, N):
#    print trr
    if N == 1:
        return L - trr[0]
    elif N == 2:
        return (L - trr[0]) + (L - trr[1])
    best_hour = -1
    peaks = []
    if trr[0] > trr[1]:
        peaks.append(0)
    if trr[N-1] > trr[N-2]:
        peaks.append(N-1)
    peaks += [i for i in xrange(1, N-1) if trr[i-1] < trr[i] > trr[i+1]]
#    print peaks
    for i, p in enumerate(peaks):
        hour1 = hour2 = L - trr[p]
        p_tm1 = p
        while p_tm1+1 < N and trr[p_tm1] > trr[p_tm1+1]:
            hour1 += L - trr[p_tm1+1]
            p_tm1 += 1
        p_tm2 = p
#        print '%d %d' % (p, trr[p_tm2-1])
        while p_tm2-1 > -1 and trr[p_tm2] > trr[p_tm2-1]:
            hour2 += L - trr[p_tm2-1]
#            print hour2
            p_tm2 -= 1
#            print hour2
        if best_hour < hour1:
            best_hour = hour1
        if best_hour < hour2:
            best_hour = hour2
    return best_hour

print solve([int(raw_input().rstrip()) for _ in xrange(N)], N)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

line = raw_input().rstrip().split()
N, L = map(int, line)


def solve(trr, N):
    if N == 1:
        return L - trr[0]
    elif N == 2:
        return (L - trr[0]) + (L - trr[1])
    best_hour = -1
    peaks = []
    if trr[0] > trr[1]:
        peaks.append(0)
    if trr[N-1] > trr[N-2]:
        peaks.append(N-1)
    peaks += [i for i in xrange(1, N-1) if trr[i-1] < trr[i] > trr[i+1]]
    for i, p in enumerate(peaks):
        hour1 = hour2 = L - trr[p]
        p_tm1 = p
        while p_tm1+1 < N and trr[p_tm1] > trr[p_tm1+1]:
            hour1 += L - trr[p_tm1+1]
            p_tm1 += 1
        p_tm2 = p
        while p_tm2-1 > -1 and trr[p_tm2] > trr[p_tm2-1]:
            hour2 += L - trr[p_tm2-1]
            p_tm2 -= 1
        if best_hour < hour1:
            best_hour = hour1
        if best_hour < hour2:
            best_hour = hour2
    return best_hour

print solve([int(raw_input().rstrip()) for _ in xrange(N)], N)

Submission status: Accepted

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in range(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            elif ices[i] > ices[i+1]:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        elif i == N-1:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,input().strip().split())
ices = []
while True:
    ice = int(input().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)

Submission status: Accepted

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in range(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,input().strip().split())
ices = []
while True:
    ice = int(input().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)

Submission status: Accepted

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,raw_input().strip().split())
ices = []
while True:
    ice = int(raw_input().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)

Submission status: Accepted

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,raw_input().strip().split())
ices = [int(raw_input().strip()) for _ in xrange(N)]

orderN(N,L,ices)

Submission status: Accepted

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in range(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            elif ices[i] > ices[i+1]:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        elif i == N-1:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,input().strip().split())
ices = [int(input().strip()) for _ in range(N)]


orderN(N,L,ices)

Submission status: Accepted

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    append = peaks.append
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            append(upPeak)
            append(downPeak)
    print(max(peaks))

N,L = map(int,raw_input().strip().split())
ices = [int(raw_input().strip()) for _ in xrange(N)]

orderN(N,L,ices)

Submission status: Accepted

Solution code:
## ?????????
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	while True:
		icicles.append(int(input().strip()))
		if len(icicles) == N: break
	return icicles, N, L
icicles, N, L = loadIcicle()

def calcDiff(icicles, N):
	diff_2times = [0]*len(icicles)

	for idx in range(len(icicles)):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		dif_right = 1 if dif_right > 0 else -1
		dif_left = 1 if dif_left > 0 else -1

		if dif_right - dif_left < 0: diff_2times[idx] = -1
		elif dif_right - dif_left > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

diff_2times = calcDiff(icicles, N)

time = [-1]*len(icicles)

peakX = [i for i in range(len(diff_2times)) if diff_2times[i]==-1] # ?????????(?????????)???index?????????
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL = i
	posR = i
	while not (isLocalMinL and isLocalMinR):
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		# ?£????????????£?????????????¨????
		if not isLocalMinL:
			if time[posL] == -1:
				time[posL] = (L-icicles[posL]) + time[posL+1]
			else:
				time[posL] = (L-icicles[posL]) + max(time[posL-1], time[posL+1])

			# ????????????????????????
			if diff_2times[posL] == 1:
				isLocalMinL = True

		posR += 1
		if posR >= N:
			isLocalMinR = True
		if not isLocalMinR:
			if time[posR] == -1:
				time[posR] = (L-icicles[posR]) + time[posR-1]
			else:
				time[posR] = (L-icicles[posR]) + max(time[posR-1], time[posR+1])

			if diff_2times[posR] == 1:
				isLocalMinR = True
print(max(time))

Submission status: Accepted

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	while True:
		icicles.append(int(input().strip()))
		if len(icicles) == N: break
	return icicles, N, L
icicles, N, L = loadIcicle()

def calcDiff(icicles, N):
	diff_2times = [0]*N

	for idx in range(N):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		dif_right = 1 if dif_right > 0 else -1
		dif_left = 1 if dif_left > 0 else -1

		if dif_right - dif_left < 0: diff_2times[idx] = -1
		elif dif_right - dif_left > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

diff_2times = calcDiff(icicles, N)

time = [-1]*N
peakX = [i for i in range(N) if diff_2times[i]==-1]
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL = i
	posR = i
	while not (isLocalMinL and isLocalMinR):
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			if time[posL] == -1:
				time[posL] = (L-icicles[posL]) + time[posL+1]
			else:
				time[posL] = (L-icicles[posL]) + max(time[posL-1], time[posL+1])

			if diff_2times[posL] == 1:
				isLocalMinL = True

		posR += 1
		if posR >= N:
			isLocalMinR = True
		if not isLocalMinR:
			if time[posR] == -1:
				time[posR] = (L-icicles[posR]) + time[posR-1]
			else:
				time[posR] = (L-icicles[posR]) + max(time[posR-1], time[posR+1])

			if diff_2times[posR] == 1:
				isLocalMinR = True
print(max(time))

Submission status: Accepted

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	while True:
		icicles.append(int(input().strip()))
		if len(icicles) == N: break
	return icicles, N, L
icicles, N, L = loadIcicle()

def calcDiff(icicles, N):
	diff_2times = [0]*N

	for idx in range(N):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		dif_right = 1 if dif_right > 0 else -1
		dif_left = 1 if dif_left > 0 else -1

		if dif_right - dif_left < 0: diff_2times[idx] = -1
		elif dif_right - dif_left > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

diff_2times = calcDiff(icicles, N)

time = [-1]*len(icicles)
peakX = [i for i in range(N) if diff_2times[i]==-1]
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL = i
	posR = i
	while not (isLocalMinL and isLocalMinR):
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			if time[posL] == -1:
				time[posL] = (L-icicles[posL]) + time[posL+1]
			else:
				time[posL] = (L-icicles[posL]) + max(time[posL-1], time[posL+1])

			if diff_2times[posL] == 1:
				isLocalMinL = True

		posR += 1
		if posR >= N:
			isLocalMinR = True
		if not isLocalMinR:
			if time[posR] == -1:
				time[posR] = (L-icicles[posR]) + time[posR-1]
			else:
				time[posR] = (L-icicles[posR]) + max(time[posR-1], time[posR+1])

			if diff_2times[posR] == 1:
				isLocalMinR = True
print(max(time))

Submission status: Accepted

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	while True:
		icicles.append(int(input().strip()))
		if len(icicles) == N: break
	return icicles, N, L
icicles, N, L = loadIcicle()

def calcDiff(icicles, N):
	diff_2times = [0]*N

	for idx in range(N):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		dif_right = 1 if dif_right > 0 else -1
		dif_left = 1 if dif_left > 0 else -1

		if dif_right - dif_left < 0: diff_2times[idx] = -1
		elif dif_right - dif_left > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

diff_2times = calcDiff(icicles, N)

time = [-1]*N
peakX = [i for i in range(N) if diff_2times[i]==-1]
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL, posR = i, i
	while not (isLocalMinL and isLocalMinR):
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			if time[posL] == -1:
				time[posL] = (L-icicles[posL]) + time[posL+1]
			else:
				time[posL] = (L-icicles[posL]) + max(time[posL-1], time[posL+1])

			if diff_2times[posL] == 1:
				isLocalMinL = True

		posR += 1
		if posR >= N:
			isLocalMinR = True
		if not isLocalMinR:
			if time[posR] == -1:
				time[posR] = (L-icicles[posR]) + time[posR-1]
			else:
				time[posR] = (L-icicles[posR]) + max(time[posR-1], time[posR+1])

			if diff_2times[posR] == 1:
				isLocalMinR = True
print(max(time))

Submission status: Accepted

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	while True:
		icicles.append(int(input().strip()))
		if len(icicles) == N: break
	return icicles, N, L

def calcDiff(icicles, N):
	diff_2times = [0]*N

	for idx in range(N):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		dif_right = 1 if dif_right > 0 else -1
		dif_left = 1 if dif_left > 0 else -1

		if dif_right - dif_left < 0: diff_2times[idx] = -1
		elif dif_right - dif_left > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

icicles, N, L = loadIcicle()
diff_2times = calcDiff(icicles, N)

time = [-1]*N
peakX = [i for i in range(N) if diff_2times[i]==-1]
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL, posR = i, i
	while not (isLocalMinL and isLocalMinR):
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			if time[posL] == -1:
				time[posL] = (L-icicles[posL]) + time[posL+1]
			else:
				time[posL] = (L-icicles[posL]) + max(time[posL-1], time[posL+1])

			if diff_2times[posL] == 1:
				isLocalMinL = True

		posR += 1
		if posR >= N:
			isLocalMinR = True
		if not isLocalMinR:
			if time[posR] == -1:
				time[posR] = (L-icicles[posR]) + time[posR-1]
			else:
				time[posR] = (L-icicles[posR]) + max(time[posR-1], time[posR+1])

			if diff_2times[posR] == 1:
				isLocalMinR = True

print(max(time))

Submission status: Accepted

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

length = [int(input()) for i in range(n)]
pare = [(length[i], i) for i in range(n)]
pare.sort(reverse=True)
ind = [p[1] for p in pare]
dp = [0] * (n + 1)
for i in ind:
  if i == 0:
    dp[i] = dp[i + 1] + (l - length[i])
  else:
    dp[i] = max(dp[i - 1], dp[i + 1]) + (l - length[i])
print(max(dp))

Submission status: Accepted

Solution code:
def solve():
  n,l = map(int,input().split())
  
  length = [int(input()) for i in range(n)]
  pare = [(length[i], i) for i in range(n)]
  pare.sort(reverse=True)
  ind = [p[1] for p in pare]
  dp = [0] * (n + 1)
  for i in ind:
    if i == 0:
      dp[i] = dp[i + 1] + (l - length[i])
    else:
      dp[i] = max(dp[i - 1], dp[i + 1]) + (l - length[i])
  print(max(dp))
solve()

Submission status: Accepted

Solution code:
def solve():
  n,l = map(int,input().split())
  
  length = [int(input()) for i in range(n)]
  pare = [(length[i], i) for i in range(n)]
  pare.sort(reverse=True)
  dp = [0] * (n + 1)
  for p in pare:
    i = p[1]
    if i == 0:
      dp[i] = dp[i + 1] + (l - length[i])
    else:
      dp[i] = max(dp[i - 1], dp[i + 1]) + (l - length[i])
  print(max(dp))
solve()

Submission status: Accepted

Solution code:
n, l = map(int,input().split())
ans = 0
pre = 0
up_acc = 0
down_acc = 0
for i in range(n):
  length = int(input())
  time = l - length
  if length > pre:
    up_acc += time
    if down_acc > ans:
      ans = down_acc
    down_acc = time
  else:
    down_acc += time
    if up_acc > ans:
      ans = up_acc
    up_acc = time
  pre = length
else:
  ans = max(ans, up_acc, down_acc)
print(ans)

Submission status: Accepted

Solution code:
def solve():
  n, l = map(int,input().split())
  ans = 0
  pre = 0
  up_acc = 0
  down_acc = 0
  for i in range(n):
    length = int(input())
    time = l - length
    if length > pre:
      up_acc += time
      if down_acc > ans:
        ans = down_acc
      down_acc = time
    else:
      down_acc += time
      if up_acc > ans:
        ans = up_acc
      up_acc = time
    pre = length
  else:
    ans = max(ans, up_acc, down_acc)
  print(ans)
solve()

Submission status: Accepted

Solution code:
def solve():
  n, l = map(int,input().split())
  ans = 0
  pre = 0
  prepre = 0
  acc = 0
  for i in range(n):
    length = int(input())
    time = l - length
    if length > pre and pre >= prepre:
      acc += time
    elif length < pre and pre <= prepre:
      acc += time
    else:
      if ans < acc:
        ans = acc
      acc = time + (l - pre)
    prepre = pre
    pre = length
  else:
    ans = max(ans, acc)
  print(ans)
solve()

Submission status: Accepted

Solution code:
def solve():
  n, l = map(int,input().split())
  ans = 0
  pre = 0
  trend = 1
  acc = 0
  for i in range(n):
    length = int(input())
    time = l - length
    if length > pre and trend >= 0:
      acc += time
    elif length < pre and trend <= 0:
      acc += time
    else:
      if ans < acc:
        ans = acc
      acc = time + (l - pre)
      trend = length - pre
    pre = length
  else:
    ans = max(ans, acc)
  print(ans)
solve()

Submission status: Runtime Error

Solution code:
[N,L]=[int(x) for x in raw_input().split()]
icelist=[0]
for i in range(N):
    icelist.append(int(raw_input()))
icelist.append(0)
incindex=[]
for i in range(1,N+1):
    if icelist[i]>icelist[i-1] and icelist[i]>icelist[i+1]:
        incindex.append(i)
ans=0
popped=0
while popped<N:
    addindex=[]
    delindex=[]
    t=L-max([icelist[i] for i in incindex])
    ans+=t
    for ii in incindex:
        icelist[ii]+=t
        if icelist[ii]==L:
            popped+=1
            delindex.append(ii)
            icelist[ii]=0
            if ii-1>0:
                if icelist[ii-1]>icelist[ii-2]:
                    addindex.append(ii-1)
            if ii+1<N+1:
                if icelist[ii+1]>icelist[ii+2]:
                    addindex.append(ii+1)
    for k in delindex:
        incindex.remove(k)
    for j in addindex:
        incindex.append(j)
print ans

Submission status: Runtime Error

Solution code:
n,l=map(int,raw_input().split())
a=[0]+[int(raw_input()) for _ in xrange(n)]+[0]
cnt=0
while a!=[0]*(n+2):
    t_id=[]
    max_t=-1
    for i in xrange(1,n+1):
        if a[i-1]<a[i] and a[i]>a[i+1]:
            t_id.append(i)
            if max_t<a[i]:
                max_t=a[i]
    cnt+=l-max_t
    for i in t_id:
        a[i]+=l-max_t
        a[i]=a[i]%l
print(cnt)

Submission status: Runtime Error

Solution code:
n,l=map(int,raw_input().split())
a=[0]+[int(raw_input()) for _ in xrange(n)]+[0]
r=[0]*(n+2)
for i in xrange(1,n+1):
    if a[i-1]<a[i] and a[i]>a[i+1]:
        r[i]=0
    elif a[i-1]<a[i] and a[i]<a[i+1]:
        r[i]=1
    elif a[i-1]>a[i] and a[i]>a[i+1]:
        r[i]=1
    else:
        r[i]=2
time=[0]*(n+2)
while r!=[-1]*(n+2):
    for i in xrange(1,n+1):
        if r[i]==0:
            r[i]=-1
            time[i]+=l-a[i]
            time[i-1]=max(time[i-1],time[i])
            time[i+1]=max(time[i+1],time[i])
            if r[i-1]!=-1:r[i-1]-=1
            if r[i+1]!=-1:r[i+1]-=1
print(max(time))

Submission status: Runtime Error

Solution code:
n,l=map(int,raw_input().split())
a=[0]+[int(raw_input()) for _ in xrange(n)]+[0]
ti=[0]*(n+2)
while a!=[0]*(n+2):
    for i in xrange(1,n+1):
        if a[i-1]<a[i] and a[i]>a[i+1]:
            ti[i]+=l-a[i]
            a[i]=0
            if a[i-1]!=0:
                ti[i-1]=max(ti[i-1],ti[i])
            if a[i+1]!=0:
                ti[i+1]=max(ti[i+1],ti[i])
print(max(ti))

Submission status: Runtime Error

Solution code:
def greedy(N,L,ices):
    counts = 0
    while True:
        for i in range(len(ices)):
            if 0 < i < N-1:
                if ices[i] > ices[i-1] and ices[i] > ices[i+1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == 0:
                if ices[i] > ices[1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == N-1:
                if ices[i] > ices[N-2]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
    if ices.count(0) == N:
        print(counts)
        return
    counts += 1


N,L = input().rstrip().split()
ices = []
while True:
    ice = input().rstrip()
    ices.append(ice)
    if len(ices) == N:
        break

greedy(N,L,ices)

Submission status: Runtime Error

Solution code:
def update(arr, diff):
    neoArr = []
    for i in range(len(arr)):
        tmp = 0
        if i==0:
            if arr[i]>arr[i+1]:
                tmp = diff
        elif i==len(arr)-1:
            if arr[i]>arr[i-1]:
                tmp = diff
        else:
            if arr[i]>arr[i-1] and arr[i]>arr[i+1]:
                tmp = diff
        neoArr.append(arr[i] + tmp)
        if neoArr[i] == L:
            neoArr[i] = 0
    return neoArr

def solve(arr):
    count = 0
    while True:
        maxInt = max(arr)
        if maxInt == 0:
            break
        diff = L-maxInt
        arr = update(arr,diff)
        count += diff
    return count

N,L = map(int,input().split(' '))
arr = []
for i in range(N):
    arr.append(int(input()))
print(solve(arr))

Submission status: Runtime Error

Solution code:
def greedy(N,L,ices):
    counts = 1
    while True:
        # print(ices)
        for i in range(len(ices)):
            if 0 < i < N-1:
                if ices[i] > ices[i-1] and ices[i] > ices[i+1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == 0:
                if ices[i] > ices[1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == N-1:
                if ices[i] > ices[N-2]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0

        if ices.count(0) == N:
            print(counts)
            return
        counts += 1


N,L = input().rstrip().split()
ices = []
while True:
    ice = input().rstrip()
    ices.append(ice)
    if len(ices) == N:
        break

# N = 4
# L = 6
# ices = [4,2,3,5]

greedy(N,L,ices)

Submission status: Runtime Error

Solution code:
import copy

def greedy(N,L,ices):
    counts = 1
    while True:
        # print(ices)
        copied = copy.deepcopy(ices)
        for i in range(len(ices)):
            if copied[i] != 0:
                if 0 < i < N-1:
                    if copied[i] >= L:
                        ices[i] = 0
                        break
                    if copied[i] > copied[i-1] and copied[i] > copied[i+1]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
                elif i == 0:
                    if copied[i] >= L:
                        ices[i] = 0
                        break
                    if copied[i] > copied[1]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
                elif i == N-1:
                    if ices[i] >= L:
                        ices[i] = 0
                        break
                    if copied[i] > copied[N-2]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
        copied = ices


        if ices.count(0) == N:
            print(counts)
            return
        counts += 1


# N,L = map(int,input().strip().split())
# ices = []
# while True:
#     ice = int(input().strip())
#     ices.append(ice)
#     if len(ices) == N:
#         break

# N = 4
# L = 6
# ices = [4,2,3,5]

# N = 6
# L = 10
# ices = [3,4,1,9,5,1]

with open("aoj.txt") as infile:
    N,L = map(int,infile.readline().strip().split())
    ices = []
    while True:
        ice = int(infile.readline())
        ices.append(ice)
        if len(ices) == N:
            break

greedy(N,L,ices)

Submission status: Runtime Error

Solution code:
import copy

def greedy(N,L,ices):
    counts = 1
    while True:
        # print(ices)
        copied = copy.deepcopy(ices)
        for i in range(len(ices)):
            if copied[i] != 0:
                if 0 < i < N-1:
                    if copied[i] >= L:
                        ices[i] = 0
                        break
                    if copied[i] > copied[i-1] and copied[i] > copied[i+1]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
                elif i == 0:
                    if copied[i] >= L:
                        ices[i] = 0
                        break
                    if copied[i] > copied[1]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
                elif i == N-1:
                    if ices[i] >= L:
                        ices[i] = 0
                        break
                    if copied[i] > copied[N-2]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
        copied = ices


        if ices.count(0) == N:
            print(counts)
            return
        counts += 1


N,L = map(int,input().strip().split())
ices = []
while True:
    ice = int(input().strip())
    ices.append(ice)
    if len(ices) == N:
        break

# N = 4
# L = 6
# ices = [4,2,3,5]

# N = 6
# L = 10
# ices = [3,4,1,9,5,1]

# with open("aoj.txt") as infile:
#     N,L = map(int,infile.readline().strip().split())
#     ices = []
#     while True:
#         ice = int(infile.readline())
#         ices.append(ice)
#         if len(ices) == N:
#             break

greedy(N,L,ices)

Submission status: Runtime Error

Solution code:
N, L = 0, 0
def loadIcicle():
	N, L = 0, 0
	i = 0
	icicles = []

	line = sys.stdin.readline().strip()
	while True:
		if i == 0:
			N, L = int(line.split(" ")[0]), int(line.split(" ")[1])
			i += 1
			continue
		line = sys.stdin.readline().strip()
		if line == "": break
		icicles.append(int(line))
		i += 1
		if i == N+1: break
	return icicles, N, L
icicles, N, L = loadIcicle()

def calcDiff(icicles, N):
	diff_2times = []
	for _ in range(len(icicles)):
		diff_2times.append(0)

	for idx in range(len(icicles)):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		peak = dif_left * dif_right < 0
		if peak and dif_left > 0: diff_2times[idx] = -1
		elif peak and dif_right > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

diff_2times = calcDiff(icicles, N)

time = []
for _ in range(len(icicles)):
	time.append(-1)

for i in range(len(icicles)):
	if diff_2times[i] == -1:
		time[i] = L - icicles[i]

for i in range(len(icicles)):
	if time[i] == -1: pass
	else: continue

	if diff_2times[i] == 0: pass
	else: continue

	if time[i-1] != -1: time[i] = (L-icicles[i]) + time[i-1]
	elif time[i+1] != -1: time[i] = (L-icicles[i]) + time[i+1]

for i in range(len(icicles)):
	if time[i] == -1: pass
	else: continue

	if diff_2times[i] == 1: pass
	else: continue

	time[i] = (L-icicles[i]) + max(time[i-1], time[i+1])

print(max(time))

Submission status: Runtime Error

Solution code:
def orderN(N,L,ices):
    upPeak = L - ices[0]
    downPeak = L - ices[0]
    peaks = []
    for i in xrange(len(ices)):
        if i < N-1:
            if ices[i] < ices[i+1]:
                peaks.append(downPeak)
                downPeak = L - ices[i+1]
                upPeak += L - ices[i+1]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i+1]
                downPeak += L - ices[i+1]
        else:
            peaks.append(upPeak)
            peaks.append(downPeak)
    print(max(peaks))

N,L = map(int,rawinput().strip().split())
ices = []
while True:
    ice = int(rawinput().strip())
    ices.append(ice)
    if len(ices) == N:
        break

orderN(N,L,ices)