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: Wrong Answer

Solution code:
n, L = map(int, raw_input().split())
dp = [0] * (n+2)
l = [0]
for i in range(n):
    l += [input()]
l += [0]
dp = [L - l[i] for i in range(n+2)]
for i in range(1,n):
    if l[i] < l[i-1]: dp[i] = dp[i-1] + (L - l[i])
ans = 0
for i in range(n,0,-1):
    if l[i] < l[i+1]:
        dp[i] = max(dp[i], dp[i+1] + (L - l[i]))
        ans = max(ans, dp[i])
print ans

Submission status: Wrong Answer

Solution code:
n, L = map(int, raw_input().split())
dp = [0] * (n+2)
l = [0]
for i in range(n):
    l += [input()]
    dp[i+1] = L - l[i+1]
l += [0]
for i in range(1,n):
    if l[i] < l[i-1]: dp[i] = dp[i-1] + (L - l[i])
ans = 0
for i in range(n,0,-1):
    if l[i] < l[i+1]:
        dp[i] = max(dp[i], dp[i+1] + (L - l[i]))
        ans = max(ans, dp[i])
print ans

Submission status: Wrong Answer

Solution code:
n, L = map(int, raw_input().split())
dp = [0] * (n+2)
l = [0]
for i in range(n):
    l += [input()]
    dp[i+1] = L - l[i+1]
l += [0]
for i in range(1,n):
    if l[i] < l[i-1]: dp[i] = dp[i-1] + (L - l[i])
ans = 0
for i in range(n,0,-1):
    if l[i] < l[i+1]:
        dp[i] = max(dp[i], dp[i+1] + (L - l[i]))
    ans = max(ans, dp[i])
print ans

Submission status: Wrong Answer

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 = map(int,input().rstrip().split())
ices = []
while True:
    ice = int(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: Wrong Answer

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] >= L:
                    ices[i] = 0
                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] >= L:
                    ices[i] = 0
                if ices[i] > ices[1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == N-1:
                if ices[i] >= L:
                    ices[i] = 0
                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 = map(int,input().rstrip().split())
ices = []
while True:
    ice = int(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: Wrong Answer

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] >= L:
                    ices[i] = 0
                    break
                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] >= L:
                    ices[i] = 0
                    break
                if ices[i] > ices[1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == N-1:
                if ices[i] >= L:
                    ices[i] = 0
                    break
                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 = map(int,input().rstrip().split())
ices = []
while True:
    ice = int(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: Wrong Answer

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] >= L:
                    ices[i] = 0
                    break
                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] >= L:
                    ices[i] = 0
                    break
                if ices[i] > ices[1]:
                    ices[i] += 1
                    if ices[i] >= L:
                        ices[i] = 0
            elif i == N-1:
                if ices[i] >= L:
                    ices[i] = 0
                    break
                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 = 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]

greedy(N,L,ices)

Submission status: Wrong Answer

Solution code:
def greedy(N,L,ices):
    counts = 1
    while True:
        # print(ices)
        for i in range(len(ices)):
            if ices[i] != 0:
                if 0 < i < N-1:
                    if ices[i] >= L:
                        ices[i] = 0
                        break
                    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] >= L:
                        ices[i] = 0
                        break
                    if ices[i] > ices[1]:
                        ices[i] += 1
                        if ices[i] >= L:
                            ices[i] = 0
                elif i == N-1:
                    if ices[i] >= L:
                        ices[i] = 0
                        break
                    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 = 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]

greedy(N,L,ices)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

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


def solve(trr, hour=0):
    N = len(trr)
    if N == 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([t for t in trr if t < 6], hour+1)


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

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


def solve(trr, hour=0):
    print trr
    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)


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

Submission status: Wrong Answer

Solution code:
import sys

## ?????????
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: Wrong Answer

Solution code:
import sys

## ?????????
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 = [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]

		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 = [-1]*len(icicles)

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

	if diff_2times[i] == -1:
		time[i] = L - icicles[i]

for i in range(len(icicles)):
	if time[i] != -1: 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: 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: Wrong Answer

Solution code:
import sys

## ?????????
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 = [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
		
		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 = [-1]*len(icicles)

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

	if diff_2times[i] == -1:
		time[i] = L - icicles[i]

for i in range(len(icicles)):
	if time[i] != -1: 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: 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: Wrong Answer

Solution code:
def orderN(N,L,ices):
    upPeak = 0
    downPeak = 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]
                upPeak += L - ices[i]
            else:
                peaks.append(upPeak)
                peaks.append(upPeak)
                downPeak += L - ices[i]
        elif i == N-1:
            if ices[i] > ices[i-1]:
                upPeak += L - ices[i]
                peaks.append(upPeak)
            else:
                downPeak += L - ices[i]
                peaks.append(upPeak)

    best = max(peaks)
    print(best)

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



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: Wrong Answer

Solution code:
def orderN(N,L,ices):
    upPeak = 0
    downPeak = 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]
                upPeak += L - ices[i]
            else:
                peaks.append(upPeak)
                upPeak = L - ices[i]
                downPeak += L - ices[i]
        elif i == N-1:
            if ices[i] > ices[i-1]:
                upPeak += L - ices[i]
                peaks.append(upPeak)
            else:
                downPeak += L - ices[i]
                peaks.append(upPeak)

    best = max(peaks)
    print(peaks)
    print(best)

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

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



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: Wrong Answer

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: Wrong Answer

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_pos = icicles[idx+1] > icicles[idx] if idx != N-1 else False
		dif_left_pos = icicles[idx] - icicles[idx-1] if idx != 0 else True

		if not dif_right_pos and dif_left_pos: diff_2times[idx] = -1
		elif dif_right_pos and not dif_left_pos: 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: Wrong Answer

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(idx, N, icicles):
	diff_2times = 0

	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 = -1
	elif dif_right - dif_left > 0: diff_2times = 1
	else: diff_2times = 0

	return diff_2times

icicles, N, L = loadIcicle()

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

	isLocalMinL, isLocalMinR = False, False
	posL, posR = i, i

	while not isLocalMinL:
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			time[posL] = (L-icicles[posL]) + time[posL+1]
			if calcDiff(posL, N, icicles) == 1:
				isLocalMinL = True

	while not isLocalMinR:
		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 calcDiff(posR, N, icicles) == 1:
				isLocalMinR = True

print(max(time))

Submission status: Wrong Answer

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(idx, N, icicles):
	diff_2times = 0

	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 = -1
	elif dif_right - dif_left > 0: diff_2times = 1
	else: diff_2times = 0

	return diff_2times

icicles, N, L = loadIcicle()

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

	isLocalMinL, isLocalMinR = False, False
	posL, posR = i, i

	while not isLocalMinL:
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			time[posL] = (L-icicles[posL]) + time[posL+1]
			if calcDiff(posL, N, icicles) == 1:
				isLocalMinL = True

	while not isLocalMinR:
		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 calcDiff(posR, N, icicles) == 1:
				isLocalMinR = True

print(max(time))

Submission status: Wrong Answer

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(idx, N, icicles):
	diff_2times = 0
	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 = -1
	elif dif_right - dif_left > 0: diff_2times = 1
	else: diff_2times = 0

	return diff_2times

icicles, N, L = loadIcicle()

time = [-1]*N
peakX = [idx for idx in range(N) if calcDiff(idx, N, icicles)==-1]
print(peakX)
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL, posR = i, i

	while not isLocalMinL:
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			time[posL] = (L-icicles[posL]) + time[posL+1]
			if calcDiff(posL, N, icicles) == 1:
				isLocalMinL = True

	while not isLocalMinR:
		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 calcDiff(posR, N, icicles) == 1:
				isLocalMinR = True

print(max(time))

Submission status: Wrong Answer

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(idx, N, icicles):
	diff_2times = 0
	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 = -1
	elif dif_right - dif_left > 0: diff_2times = 1
	else: diff_2times = 0

	return diff_2times

icicles, N, L = loadIcicle()

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

	isLocalMinL, isLocalMinR = False, False
	posL, posR = i, i

	while not isLocalMinL:
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			time[posL] = (L-icicles[posL]) + time[posL+1]
			if calcDiff(posL, N, icicles) == 1:
				isLocalMinL = True

	while not isLocalMinR:
		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 calcDiff(posR, N, icicles) == 1:
				isLocalMinR = True

print(max(time))

Submission status: Wrong Answer

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	for _ in range(N):
		icicles.append(int(input().strip()))
	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 True:
		posL -= 1
		if posL < 0: break
		if not isLocalMinL:
			left = 0 if posL-1 < 0 else time[posL-1]
			time[posL] = (L-icicles[posL]) + max(left, time[posL+1])
			if diff_2times[posL] == 1: break
	while True:
		posR += 1
		if posR > N-1: break
		if not isLocalMinR:
			right = 0 if posR+1 > N-1 else time[posR+1]
			time[posR] = (L-icicles[posR]) + max(time[posR-1], right)
			if diff_2times[posR] == 1: break

print(max(time))

Submission status: Wrong Answer

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	for _ in range(N):
		icicles.append(int(input().strip()))
	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:

		posL -= 1
		if posL < 0: break
		if not isLocalMinL:
			left = 0 if posL-1 < 0 else time[posL-1]
			time[posL] = (L-icicles[posL]) + max(left, time[posL+1])

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

	while not isLocalMinR:

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

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

print(max(time))

Submission status: Wrong Answer

Solution code:
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	for _ in range(N):
		icicles.append(int(input().strip()))
	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
		posR += 1

		if posL < 0: isLocalMinL = True
		if posR > N-1: isLocalMinR = True

		if not isLocalMinL:
			left = 0 if posL-1 < 0 else time[posL-1]
			time[posL] = (L-icicles[posL]) + max(left, time[posL+1])

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

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

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

print(max(time))

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

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


def solve(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)


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

Submission status: Accepted

Solution code:
n, L = map(int, raw_input().split())
dp = [0] * (n+2)
l = [0]
for i in range(n):
    l += [input()]
    dp[i+1] = L - l[i+1]
l += [0]
for i in range(1,n+1):
    if l[i] < l[i-1]: dp[i] = dp[i-1] + (L - l[i])
ans = 0
for i in range(n,0,-1):
    if l[i] < l[i+1]:
        dp[i] = max(dp[i], dp[i+1] + (L - l[i]))
    ans = max(ans, dp[i])
print ans

Submission status: Accepted

Solution code:
n, L = map(int, raw_input().split())
dp = [0] * (n+2)
l = [0]
for i in range(n):
    l += [input()]
    dp[i+1] = L - l[i+1]
l += [0]
for i in range(1,n+1):
    if l[i] < l[i-1]: dp[i] += dp[i-1]
ans = 0
for i in range(n,0,-1):
    if l[i] < l[i+1]:
        dp[i] = max(dp[i], dp[i+1] + (L - l[i]))
    ans = max(ans, dp[i])
print ans

Submission status: Accepted

Solution code:
[N,L]=[int(x) for x in raw_input().split()]
icelist=[]
for i in range(N):
    icelist+=[int(raw_input())]
peakindex=[0]
for i in range(1,N-1):
    if (icelist[i]-icelist[i-1])*(icelist[i+1]-icelist[i])<0:
            peakindex.append(i)
peakindex.append(N-1)
ans=0
for i in range(len(peakindex)-1):
    newans=sum([L-icelist[x] for x in range(peakindex[i],peakindex[i+1]+1)])
    ans=max(ans,newans)
print ans