Problem:


Score : 600 points

Problem Statement

Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:

He never visits a point with coordinate less than 0, or a point with coordinate greater than L.

He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.

He only changes direction at a point with integer coordinate.

Each time when Snuke passes a point with coordinate i-0.5, where i is an integer, he put a stone in his i-th ear.

After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i, Snuke's i-th ear contains A_i stones:

Put a stone in one of Snuke's ears.

Remove a stone from one of Snuke's ears.

Find the minimum number of operations required when Ringo can freely decide how Snuke walks.

Constraints

1 \leq L \leq 2\times 10^5

0 \leq A_i \leq 10^9(1\leq i\leq L)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

L
A_1
:
A_L

Output

Print the minimum number of operations required when Ringo can freely decide how Snuke walks.

Sample Input 1

4
1
0
2
3

Sample Output 1

1

Assume that Snuke walks as follows:

He starts walking at coordinate 3 and finishes walking at coordinate 4, visiting coordinates 3,4,3,2,3,4 in this order.

Then, Snuke's four ears will contain 0,0,2,3 stones, respectively.
Ringo can satisfy the requirement by putting one stone in the first ear.

Sample Input 2

8
2
0
0
2
1
3
4
1

Sample Output 2

3

Sample Input 3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

Sample Output 3

1



Sample input:
4
1
0
2
3


Sample output:
1

Submission status: Runtime Error

Solution code:
import sys
L = int(input().strip())
A = [int(n.strip()) for n in sys.stdin]

def explore(now_position, now_stone):  # 操作が必ず減るように移動する
  now_diff = diff_stone(now_stone)
  explore_list = [now_diff]
  # 右へ
  if not now_position == L:
    now_stone[now_position] += 1
    if now_diff > diff_stone(now_stone):
      explore_list.append(explore(now_position+1, now_stone))
    now_stone[now_position] -= 1 # 戻す
  # 左へ
  if not now_position == 0:
    now_stone[now_position-1] += 1
    if now_diff > diff_stone(now_stone):
      explore_list.append(explore(now_position-1, now_stone))
    now_stone[now_position-1] -= 1 # 戻す
  # 一番小さいdiffを返す
  return min(explore_list)

def diff_stone(now_stone):
  d = 0
  for i in range(len(A)):
    d += abs(now_stone[i]-A[i])
  return d

print(min([explore(i, [0 for _ in range(L)]) for i in range(L+1)]))

Submission status: Runtime Error

Solution code:
n=int(input())
A=[int(input()) for i in range(n)]
s=0

Z=[]
R=[]
z=0
r=0
for a in A:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)

for i in range(n-1,-1,-1):
  if Z[i]>=R[i]:
    s+=sum(A[:i+1])
    A=A[i+1:]
    
    break

if A==[]:
  print(s)
  exit()
  
Z=[]
R=[]
z=0
r=0
for a in A[::-1]:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)
Z=Z[::-1]
R=R[::-1]

for i in range(len(a)):
  if Z[i]>=R[i]:
    s+=sum(A[i:])
    A=A[:i]
    break

if A==[]:
  print(s)
  exit()

for i in range(len(A)):
  if A[i]==0:
    s+=1
    A[i]=1
s0=s

O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s+=O[i]
    A=A[i+1:]

    break


O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s0+=O[i]
    A=A[i+1:]

    break
O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s0+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
print(min(s,s0))

Submission status: Runtime Error

Solution code:
l = int(input())

chunks = []
distances = []

check = int(input()) % 2
if  check == 1:
	now_in_chunk = True
else:
	now_in_chunk = False
size = 1

for i in range(l-1):
	check = int(input()) % 2
	if check == 0:
		if now_in_chunk:
			chunks.append(size)
			now_in_chunk = False
			size = 1
		else:
			size += 1
	else:
		if now_in_chunk:
			size += 1
		else:
			distances.append(size)
			now_in_chunk = True
			size = 1

if now_in_chunk:
	chunks.append(size)

# 最初0だったとき
if len(chunks) == len(distances):
	distances = distances[1:]

new_chunks = []
new_distances = []

# 集団の結合
connecting = False
amount = chunks[0]
for key in range(1, len(chunks)):
	if chunks[key] > distances[key-1]:
		connecting = True
		amount += chunks[key]
	else:
		connecting = False
		new_chunks.append(amount)
		new_distances.append(distances[key-1])
		amount = chunks[key]

new_chunks.append(amount)

if len(new_chunks) == 1:
	print(0)
else:
	new_chunks.sort()
	new_chunks.reverse()
	new_chunks = new_chunks[1:]

	print(sum(new_chunks))

Submission status: Runtime Error

Solution code:
n=int(input())
A=[int(input()) for i in range(n)]
s=0

Z=[]
R=[]
z=0
r=0
for a in A:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)

for i in range(n-1,-1,-1):
  if Z[i]>=R[i]:
    s+=sum(A[:i+1])
    A=A[i+1:]
    
    break

if A==[]:
  print(s)
  exit()
  
Z=[]
R=[]
z=0
r=0
for a in A[::-1]:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)
Z=Z[::-1]
R=R[::-1]

for i in range(n):
  if Z[i]>=R[i]:
    s+=sum(A[i:])
    A=A[:i]
    break

if A==[]:
  print(s)
  exit()

for i in range(len(A)):
  if A[i]==0:
    s+=1
    A[i]=1
s0=s

O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s+=O[i]
    A=A[i+1:]

    break


O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s0+=O[i]
    A=A[i+1:]

    break
O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s0+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
print(min(s,s0))

Submission status: Runtime Error

Solution code:
import numpy as np

L = int(input())

A_list = []
not_zero_indexs = []
for i in range(L):
    input_ = int(input())
    A_list.append(input_)
    if input_ != 0:
        not_zero_indexs.append(i)

def main(A_list, not_zero_indexs):
    yobun = 0
    count = np.zeros(L, dtype=int)

    cur_nzero_indexs = not_zero_indexs

    while True:
        start_i, next_i = cur_nzero_indexs[0:2]
        n_aida_zero =  next_i - start_i - 1
        cur_nzero_indexs = cur_nzero_indexs[1:]
        if n_aida_zero < A_list[start_i]:
            break

    cur_i = start_i
    count[cur_i] = A_list[cur_i]

    cur_yobun = sum(A_list[:cur_i])
    yobun += cur_yobun

    for cur_next_i in cur_nzero_indexs:
        a_array = A_list[cur_i+1:]
        #print(a_array)

        count[cur_i+1:cur_next_i] += 1
        cur_yobun = cur_next_i - 1 - (cur_i + 1) + 1

        cur_i = cur_next_i
        count[cur_i] += A_list[cur_i]
        if A_list[cur_i] % 2 == 0 and cur_i != cur_nzero_indexs[-1]:
            count[cur_i] += 1
            cur_yobun += 1

        yobun += cur_yobun

    diff = np.sum(np.abs(A_list - count))
    #assert yobun == diff

    out = yobun
    #print(yobun, diff, count, A_list)
    return out

out1 = main(A_list, not_zero_indexs)
not_zero_indexs_rev = [L-1 - elm for elm in reversed(not_zero_indexs)]
out2 = main(A_list[::-1], not_zero_indexs_rev)
#print(out1, out2)
print(min(out1, out2))

Submission status: Runtime Error

Solution code:
def hoge(A, x):
    path = []
    tmp = []
    for a in A:
        if a != x:
            tmp.append(a)
        else:
            if tmp:
                path.append(tmp)
            tmp = []
    if tmp:
        path.append(tmp)
    return path

def func(path):
    if len(path) == 2:
        return 0
    pp = [x%2 for x in path]
    dp1 = [0] * len(path)
    for i in range(len(path)):
        dp1[i] = (dp1[i - 1] + 1) * (pp[i] == 1)
    dp2 = [0] * len(path)
    for i in range(len(path)):
        dp2[i] = (dp2[i - 1] + 1) * (pp[i] == 0)
    while dp1 and dp1[-1] == 0:
        dp1.pop()
    while dp2 and dp2[-1] == 0:
        dp2.pop()
    dp1.reverse()
    dp2.reverse()
    while dp1 and dp1[-1] == 0:
        dp1.pop()
    while dp2 and dp2[-1] == 0:
        dp2.pop()
    return min(max(x for x in dp1 if x), max(x for x in dp2 if x))

L, *A = map(int, open(0).read().split())
path = sorted(hoge(A, 0), key=len, reverse=True)
print(func(path[0]) + sum(map(sum, path[1:])))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 20:33:23 2019

@author: Yamazaki Kenichi
"""

L = int(input())
A = [int(input()) for i in range(L)]

B = []

ans = 0
zero = False
nzero = False
temp = 0

for elem in A:
    if elem ==0:
        if zero:
            B[-1][1]+=1
        else:
            B.append([0,1,0,0])
            zero = True
            nzero = False
    else:
        if nzero:
            B[-1][0]+=elem
            if elem%2==0:
                B[-1][1]+=1
            else:
                B[-1][3]=0
        else:
            if elem%2==0:
                B.append([elem,1,1,1])
            else:
                B.append([elem,0,0,0])
            nzero = True
            zero = False

def a(X):
    flg = False
    C = []
    for i in range(len(X)-2):
        if X[i][0]+X[i+2][0] < X[i][1]+X[i+1][1]+X[i+2][1]:
            C.append([X[i][0]+X[i+2][0],X[i][1]+X[i+1][1]+X[i+2][1],X[i][2],X[i][3]])
            flg = True
        else:
            C.append(X[i])
            C.append(X[i+1])
            C.append(X[i+2])
    if flg:
        a(C)
    else:
        return C

C = a(B)
ans = 0
t1,t2,t3,m = 0,0,0,0
for i in range(len(C)):
    ans += C[i][0]
    if C[i][0] > m:
        m = C[i][0]
        t1 = C[i][1]
        t2 = C[i][2]
        t3 = C[i][3]
ans += t1-t2-t3-m
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[int(input()) for i in range(n)]
s=0

Z=[]
R=[]
z=0
r=0
for a in A:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)

for i in range(n-1,-1,-1):
  if Z[i]>=R[i]:
    s+=sum(A[:i+1])
    A=A[i+1:]
    
    break


Z=[]
R=[]
z=0
r=0
for a in A[::-1]:
  if a==0:
    z+=1
  r+=a
  Z.append(z)
  R.append(r)
Z=Z[::-1]
R=R[::-1]

for i in range(n):
  if Z[i]>=R[i]:
    s+=sum(A[i:])
    A=A[:i]
    break

for i in range(len(A)):
  if A[i]==0:
    s+=1
    A[i]=1
s0=s

O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s+=O[i]
    A=A[i+1:]

    break


O=[]
E=[]
o=0
e=0
for a in A[::-1]:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0
E=E[::-1]
O=O[::-1]
for i in range(len(A)):
  if E[i]>O[i]:
    s0+=O[i]
    A=A[i+1:]

    break
O=[]
E=[]
o=0
e=0
for a in A:
  if a%2==0:
    e+=1
  else:
    o+=1
  E.append(e)
  O.append(o)
l=0
f=0

for i in range(len(A)-1,-1,-1):
  if E[i]>O[i] and f==1:
    s0+=O[i]
    A=A[i+1:]

    break
  if A[i]==1:
    f=1
print(min(s,s0))

Submission status: Runtime Error

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
L = int(input())
A = [int(input()) for _ in  range(L)]


# mode = A[0] % 2
# B = []
# for a in A:
#     if a == 0:
#         mode = -1
#     elif a % 2 == mode:
#     elif a % 2 != mode:


fromEnd = []

i = 0
while i < L:
    if A[i] != 0:
        start = i
        while i < L and A[i] != 0:
            i += 1
        end = i-1 if i != start else start
        fromEnd.append((start, end, sum(A[start:end+1])))
    i += 1

ans = float("inf")

# start forward
mode = 2 % 2
sum_forward = sum(A)
for i in range(start, L):
    sum_forward = min(sum_forward, ans)
    if   A[i] % 2 ==  1 and mode == A[i] % 2:
        sum_forward -= A[i]
    elif A[i] % 2 ==  1 and mode != A[i] % 2:
        mode = A[i] % 2
        sum_forward -= A[i]

    elif A[i] == 0:
        sum_forward += 1
        mode = -1

    elif A[i] % 2 == 0 and mode == A[i] % 2 :
        sum_forward -= A[i]

    elif A[i] % 2 == 0 and mode != A[i] % 2 :
        sum_forward -= A[i] - 1
        mode = A[i] % 2 
    
    if i == L-1 and A[i] %2 == 0 and mode != A[i] %2:
        sum_forward -= 1

# print("sum forward: ", sum_forward)
ans = sum_forward
mode = 2 % 2
sum_backward = sum(A)


for i in range(end, -1, -1):
    ans = min(sum_backward, ans)
    
    # ans = min(sum_backward, ans)
    if   A[i] % 2 ==  1 and mode == A[i] % 2:
        sum_backward -= A[i]
    elif A[i] % 2 ==  1 and mode != A[i] % 2:
        mode = A[i] % 2
        sum_backward -= A[i]

    elif A[i] == 0:
        sum_backward += 1
        mode = -1

    elif A[i] % 2 == 0 and mode == A[i] % 2 :
        sum_backward -= A[i]
    elif A[i] % 2 == 0 and mode != A[i] % 2 :
        sum_backward -= A[i] - 1
        mode = A[i] % 2 
    if i == 0 and A[i] %2 == 0 and mode != A[i] %2:
        sum_backward -= 1

ans = min(sum_backward, sum_forward)
print(ans)

Submission status: Runtime Error

Solution code:
l=int(input())
a_list=[]
for i in range(l):
    a_list.append(int(input()))

for num, a in enumerate(a_list):
    if a!=0:
        start=num+1
        break
for num, a in enumerate(reversed(a_list)):
    if a!=0:
        end=l-num
        break

b=0
for i in range(len(a_list[start-1:end])-1):
    if a_list[i]%2 != a_list[i+1]%2:
        b+=1
print(a_list[start-1:end].count(0)+b-2)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 20:33:23 2019

@author: Yamazaki Kenichi
"""

L = int(input())
A = [int(input()) for i in range(L)]

B = []

ans = 0
zero = False
nzero = False
temp = 0

for elem in A:
    if elem ==0:
        if zero:
            B[-1][1]+=1
        else:
            B.append([0,1,0,0])
            zero = True
            nzero = False
    else:
        if nzero:
            B[-1][0]+=elem
            if elem%2==0:
                B[-1][1]+=1
            else:
                B[-1][3]=0
        else:
            if elem%2==0:
                B.append([elem,1,1,1])
            else:
                B.append([elem,0,0,0])
            nzero = True
            zero = False

def a(X):
    flg = False
    C = []
    for i in range(len(X)-2):
        if X[i][0]+X[i+2][0] < X[i][1]+X[i+1][1]+X[i+2][1]:
            C.append([[X[i][0]+X[i+2][0]],X[i][1]+X[i+1][1]+X[i+2][1],X[i][2],X[i][3]])
            flg = True
        else:
            C.append(X[i])
            C.append(X[i+1])
            C.append(X[i+2])
    if flg:
        a(C)
    else:
        return C

C = a(B)
ans = 0
t1,t2,t3,m = 0,0,0,0
for i in range(len(C)):
    ans += C[i][0]
    if C[i][0] > m:
        m = C[i][0]
        t1 = C[i][1]
        t2 = C[i][2]
        t3 = C[i][3]
ans += t1-t2-t3-m
print(ans)

Submission status: Runtime Error

Solution code:
def hoge(A, x):
    path = []
    tmp = []
    for a in A:
        if a != x:
            tmp.append(a)
        else:
            if tmp:
                path.append(tmp)
            tmp = []
    if tmp:
        path.append(tmp)
    return path

def func(path):
    if len(path) == 2:
        return 0
    pp = [x%2 for x in path]
    dp1 = [0] * len(path)
    for i in range(len(path)):
        dp1[i] = (dp1[i - 1] + 1) * (pp[i] == 1)
    dp2 = [0] * len(path)
    for i in range(len(path)):
        dp2[i] = (dp2[i - 1] + 1) * (pp[i] == 0)
    while dp1 and dp1[-1] == 0:
        dp1.pop()
    while dp2 and dp2[-1] == 0:
        dp2.pop()
    dp1.reverse()
    dp2.reverse()
    while dp1 and dp1[-1] == 0:
        dp1.pop()
    while dp2 and dp2[-1] == 0:
        dp2.pop()
    return min(min(x for x in dp1 if x), min(x for x in dp2 if x))

L, *A = map(int, open(0).read().split())
path = sorted(hoge(A, 0), key=len, reverse=True)
print(func(path[0]) + sum(map(sum, path[1:])))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 20:33:23 2019

@author: Yamazaki Kenichi
"""

L = int(input())
A = [int(input()) for i in range(L)]

B = []

ans = 0
zero = False
nzero = False
temp = 0

for elem in A:
    if elem ==0:
        if zero:
            B[-1][1]+=1
        else:
            B.append([0,1,0,0])
            zero = True
            nzero = False
    else:
        if nzero:
            B[-1][0]+=elem
            if elem%2==0:
                B[-1][1]+=1
            else:
                B[-1][3]=0
        else:
            if elem%2==0:
                B.append([elem,1,1,1])
            else:
                B.append([elem,0,0,0])
            nzero = True
            zero = False

def a(X):
    C = []
    for i in range(len(X)-2):
        if X[i][0]+X[i+2][0] < X[i][1]+X[i+1][1]+X[i+2][1]:
            C.append([[X[i][0]+X[i+2][0]],X[i][1]+X[i+1][1]+X[i+2][1],X[i][2],X[i][3]])
        else:
            C.append(X[i])
            C.append(X[i+1])
            C.append(X[i+2])
    return C
C = a(B)
ans = 0
t1,t2,t3,m = 0,0,0,0
for i in range(len(C)):
    ans += C[i][0]
    if C[i][0] > m:
        m = C[i][0]
        t1 = C[i][1]
        t2 = C[i][2]
        t3 = C[i][3]
ans += t1-t2-t3-m
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
arr = []
evod0 = []
even = [0]
odds = [0]
g0 = []
for i in range(N):
    tmp = int(input())
    arr.append(tmp)
    if tmp%2:
        evod0.append(1)
        even.append(even[-1]+1)
        odds.append(odds[-1])
    elif tmp>0:
        evod0.append(2)
        even.append(even[-1])
        odds.append(odds[-1]+1)
    else:
        evod0.append(0)
        g0.append(i)
        even.append(even[-1]+1)
        odds.append(odds[-1]+2)
ans = sum(arr)
#0を消す
for i in range(N-1):
    tmp = min(even[i+1]+odds[N] - odds[i+1],odds[i+1] + even[N] - even[i+1])
    ans = min(ans,tmp)
tmp = min(even[N],odds[N])
ans = min(ans,tmp)
#0を消さない
ans0 = 0
#左を全部0にする
ans0 += sum(arr[:g0[0]])
a0min = sum(arr[g0[-1]+1:])
for i in range(g0[-1]+1,N-1):
    tmp = min(even[i+1] - even[g0[-1]+1] + odds[N] - odds[i+1],odds[i+1] - odds[g0[-1]+1] + even[N] - even[i+1])
    a0min = min(a0min,tmp)
tmp = min(even[N]-even[g0[-1]+1],odds[N]-odds[g0[-1]+1])
a0min = min(a0min,tmp)
ans0 += a0min
#右を全部0に
right = sum(arr[g0[-1]:])
rmin = sum(arr[:g0[0]])
for i in range(0,g0[0]):
    tmp = min(even[i+1]+odds[g0[0]] - odds[i+1],odds[i+1] + even[g0[0]] - even[i+1])
    rmin = min(rmin,tmp)
tmp = min(even[g0[0]],odds[g0[0]])
rmin = min(tmp,rmin)
right += rmin
print(min(ans,ans0,right))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

#define PQ(T) priority_queue<T>
#define RPQ(T) priority_queue<T,vector<T>,greater<T>>

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
template <typename T>
inline T mod(T a, T b) { return ((a % b) + b) % b; }


const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }



/*
  empty 奇 偶 奇偶 偶奇 奇偶奇 偶奇偶 fin
*/

ll solve(int L, vi& a) {
    vector<vll> dp(L+1, vll(8, LLONG_MAX));
    dp[0][0] = 0;

    rep(i,L){
        int k = (a[i] % 2) ? 0 : 1;
        int g = (a[i] % 2) ? 1 : 0; if (a[i]==0) g=2;

        if (dp[i][0] != LLONG_MAX) {
            amin(dp[i+1][0], dp[i][0] + a[i]);
            amin(dp[i+1][1], dp[i][0] + k);
            amin(dp[i+1][2], dp[i][0] + g);
            amin(dp[i+1][7], dp[i][0] + a[i]);
        }
        if (dp[i][1] != LLONG_MAX) {
            amin(dp[i+1][1], dp[i][1] + k);
            amin(dp[i+1][3], dp[i][1] + g);
            amin(dp[i+1][7], dp[i][1] + a[i]);
        }
        if (dp[i][2] != LLONG_MAX) {
            amin(dp[i+1][2], dp[i][2] + g);
            amin(dp[i+1][4], dp[i][2] + k);
            amin(dp[i+1][7], dp[i][2] + a[i]);
        }
        if (dp[i][3] != LLONG_MAX) {
            amin(dp[i+1][3], dp[i][3] + g);
            amin(dp[i+1][5], dp[i][3] + k);
            amin(dp[i+1][7], dp[i][3] + a[i]);
        }
        if (dp[i][4] != LLONG_MAX) {
            amin(dp[i+1][4], dp[i][4] + k);
            amin(dp[i+1][6], dp[i][4] + g);
            amin(dp[i+1][7], dp[i][4] + a[i]);
        }
        if (dp[i][5] != LLONG_MAX) {
            amin(dp[i+1][5], dp[i][5] + k);
            amin(dp[i+1][7], dp[i][5] + a[i]);
        }
        if (dp[i][6] != LLONG_MAX) {
            amin(dp[i+1][6], dp[i][6] + g);
            amin(dp[i+1][7], dp[i][6] + a[i]);
        }
        if (dp[i][7] != LLONG_MAX) {
            amin(dp[i+1][7], dp[i][7] + a[i]);
        }
    }

    return *min_element(ALL(dp[L]));
}

int main() {
    int L; scanf("%d",&L);
    vi a(L);
    rep(i,L) scanf("%d",&a[i]);
    cout << solve(L,a) << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
def hoge(A, x, flag = False):
    path = []
    tmp = []
    for a in A:
        if a != x:
            tmp.append(a)
        else:
            if tmp:
                path.append(tmp)
            tmp = []
    if tmp:
        path.append(tmp)
    if flag:
        return path[1:-1]
    return path

def func(path):
    if len(path) == 2:
        return 0
    pp = [x%2 for x in path]
    path1 = min(map(len, hoge([0] + pp + [0], 1, True)))
    path2 = min(map(len, hoge([1] + pp + [1], 0, True)))
    return min(path1, path2)

L, *A = map(int, open(0).read().split())
path = hoge(A, 0)
cnt = list(map(len, path))
max_cnt = max(cnt)
ans = 0
if max_cnt:
    for p in path:
        if len(p) == max_cnt:
            ans += func(p)
        else:
            ans += sum(p)
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

"""

o 999
o 2 3
x 2 0 2
o 2 1 2
x 2 1 2 1
o 2 1 3 1
o 2 1 3 2
o 3 1 3
x 3 2 3
o 3 2 2

- 0は両端のみ
- 偶奇の切り替わりが2回以下

zzoo
zzee
zzooee
zzeeoo
zzooeeoo xxx
zzeeooee
zz
???zz
"""

ooeeooee
L = input()
A = [input() for _ in range(L)]

T = [L,L,L,L,L,L,0,L]
for a in A:
  P = T
  o = 1-a%2
  e = 1-o
  if a==0:
    e = 2
  T = [
    min(P[0]+o, P[6]+o),
    min(P[1]+e, P[6]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+o, P[2]+o),
    min(P[5]+e, P[3]+e),
    P[6]+a,
    min(P)+a,
  ]
  #print a, T
print min(T[4:]+T[5:])

Submission status: Runtime Error

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

L = int(input())
l = [0]*L
l2 = [0]*L

i = 0

for i in range(L):
    a = int(input())
    l[i] = a


zeros = l.count(0)
rem0 = 0
while True:
    if l[i] == 0:
        rem0 += 1
    else:
        break
    i += 1
i = 0
while True:
    if l[-i] == 0:
        rem0 += 1
    else:
        break
    i += 1
# print("zeros")
# print(zeros)
# print(rem0)

l = list(map(lambda x: x % 2, l))

l = list(accumulate(l))
for i in range(L):
    l2[i] = abs(i+1-2*l[i])

ind = l2.index(max(l2))

ans = ind+1 - l[ind]+l[-1]-l[ind]
ans2 = l[ind] + L-ind-1 - l[-1]+l[ind]
print(min(ans, ans2)+zeros-rem0)

Submission status: Runtime Error

Solution code:
l = int(input())
a = []
mountain = []
count = 1
for i in range(l):
  x = int(input())
  if x==0 and len(a)>0:
    mountain.append(a)
    a = []
  elif x!=0:
    a.append(x)
if len(a)>0:
  mountain.append(a)
sum_mountain = []
for i in range(len(mountain)):
  sum_mountain.append(sum(mountain[i]))
max_sum = max(sum_mountain)
for i in range(len(sum_mountain)):
  if max_sum != sum_mountain[i]:
    count += sum_mountain[i]
print(count)

Submission status: Runtime Error

Solution code:
def func(path):
    pp = [0 if x%2 else 1 for x in path]
    s = [0] * len(pp)
    for i, p in enumerate(pp):
        s[i] = (s[i] + 1) * (p == 0)
    if 0 not in s[1:]:
        return min(x for x in s if x)
    else:
        return 0

L, *A = map(int, open(0).read().split())
path = []
tmp = []
for a in A:
    if a:
        tmp.append(a)
    else:
        path.append(tmp)
        tmp = []
path.append(tmp)
cnt = list(map(len, path))
max_cnt = max(cnt)
ans = 0
for p in path:
    if len(p) == max_cnt:
        ans += func(p)
    else:
        ans += sum(p)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
if os.environ.get("USER") == "shun":
    def debug(*args): print(*args, file=sys.stderr)
else:
    print("NO DEBUG", file=sys.stderr)
    def debug(*args): pass
def exit(): sys.exit(0)


l = int(input())
a = []
for _ in range(l):
    a.append(int(input()))

init_score = 0
for i in range(l):
    if a[i] == 0:
        init_score += 2
    elif a[i] % 2 == 0:
        pass
    else:
        init_score += 1

left = [0]
for i in range(l):
    left.append(left[i])
    if a[i] == 0:
        left[i+1] -= 2
    elif a[i] % 2 == 0:
        left[i+1] += a[i]
    else:
        left[i+1] += a[i] - 1
left_i = 0
left_min = left[0]
for i in range(l+1):
    if left[i] < left_min:
        left_i = i
        left_min = left[i]
debug(left_i, left)

right = [0] * (l+1)
for i in range(l, 0, -1):
    right[i-1] = right[i]
    if a[i-1] == 0:
        right[i-1] -= 2
    elif a[i-1] % 2 == 0:
        right[i-1] += a[i-1]
    else:
        right[i-1] += a[i-1] - 1
right_i = l
right_min = right[l]
for i in range(l, -1, -1):
    if right[i] < right_min:
        right_i = i
        right_min = right[i]
debug(right_i, right)

assert(left_i <= right_i)

# odd
temp_score = init_score + left_min + right_min
b = a[left_i:right_i]
k = len(b)

for i in range(k):
    if b[i] == 0:
        temp_score -= 1
    elif b[i] % 2 == 0:
        temp_score += 1
    else:
        temp_score -= 1


left = [0]
for i in range(k):
    left.append(left[i])
    if b[i] == 0:
        left[i+1] += 1
    elif b[i] % 2 == 0:
        left[i+1] -= 1
    else:
        left[i+1] += 1
left_i = 0
left_min = left[0]
for i in range(k+1):
    if left[i] < left_min:
        left_i = i
        left_min = left[i]
debug(left_i, left)

right = [0] * (k+1)
for i in range(k, 0, -1):
    right[i-1] = right[i]
    if b[i-1] == 0:
        right[i-1] += 1
    elif b[i-1] % 2 == 0:
        right[i-1] -= 1
    else:
        right[i-1] += 1
right_i = k
right_min = right[k]
for i in range(k, -1, -1):
    if right[i] < right_min:
        right_i = i
        right_min = right[i]
debug(right_i, right)

assert(left_i <= right_i)

score = temp_score + left_min + right_min
print(score)

Submission status: Runtime Error

Solution code:
l,*a,=map(int,open(0).read().split())
b=[int(i%2==j%2)for i,j in zip(a,a[1:])]
a=0
c=b[0]
for i in range(1,len(b)):
    if b[i]:
        c+=1
    else:
        a=max(a,c)
        c=0
print(max(a,c))

Submission status: Runtime Error

Solution code:
from math import ceil
L = int(input())
A = [int(input()) for _ in range(L)]
even = 0
start, end = 0, L-1
if A[0] == 0:
	for i in range(1, L):
		if A[i] != 0:
			start = i
			break
if A[-1] == 0:
	for i in reversed(range(L-1)):
		if A[i] != 0:
			end = i
			break
for a in A[start:end+1]:
	if a % 2 == 0:
		even += 1
if A[start] % 2 == 0 and A[start+1] % 2 == 1:
	even -= 1
if A[end-1] % 2 == 1 and A[end] % 2 == 0:
	even -= 1
		
print(ceil(even/2))

Submission status: Runtime Error

Solution code:
L=int(input())


ma_g=0
ma_k=0
temp=0
for i in range(L):
    a=int(input())
    if a%2==0:
        temp+=1
    else:
        if(ma_g<temp):
            ma_g=temp
        temp=0
        
for i in range(L):
    a=int(input())
    if a%2==1:
        temp+=1
    else:
        if(ma_k<temp):
            ma_k=temp
        temp=0
if(ma_g>ma_k):
    print(ma_g)
else:
    print(ma_k)