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

Solution code:
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)] + [0]
dp = [[float("inf") for _ in range(5)] for _ in range(n+1)]
def ev(x):
	if x == 0:
		return 2
	else:
		return x&1
def od(x):
	return (x+1)&1

dp[0] = [a[0], ev(a[0]), od(a[0]), ev(a[0]), a[0]]
for i in range(1, n+1):
	dp[i][0] = dp[i-1][0] + a[i]
	dp[i][1] = min(dp[i-1][:2]) + ev(a[i])
	dp[i][2] = min(dp[i-1][:3]) + od(a[i])
	dp[i][3] = min(dp[i-1][:4]) + ev(a[i])
	dp[i][4] = min(dp[i-1]) + a[i]
print(min(dp[n]))

Submission status: Accepted

Solution code:
# D
L = int(input())
A_list = [0]*L
for i in range(L):
    A_list[i] = int(input())
    
DP = [0]*5
for i in range(L):
    r0 = A_list[i]
    r1 = (A_list[i] + 1) % 2
    if A_list[i] == 0:
        r2 = 2
    else:
        r2 = A_list[i] % 2
        
    DP[4] = min(DP[0], DP[1], DP[2], DP[3], DP[4]) + r0
    DP[3] = min(DP[0], DP[1], DP[2], DP[3]) + r2
    DP[2] = min(DP[0], DP[1], DP[2]) + r1
    DP[1] = min(DP[0], DP[1]) + r2
    DP[0] = DP[0] + r0
    
print(min(DP))

Submission status: Accepted

Solution code:
L = int(input())
a=[int(input()) for i in range(L)]
if L == 1:
    print(0)
    exit()

#累積和
rightsum = [0]*(L+1)
leftsum = [0]*(L+1)
for i in range(1,L+1):
    rightsum[i] = rightsum[i-1]+a[i-1]
    leftsum[i] = leftsum[i-1]+a[L-i]

#Re:戻ってくる Go:戻ってこなくてもよい
Reright = [0]
Goright = [0]
for i in range(L):
    if a[i] == 0:
        Goright.append(min(rightsum[i+1],1+min(Goright[-1],Reright[-1])))
        Reright.append(min(rightsum[i+1],2+Reright[-1]))
    else:
        Goright.append(min(rightsum[i+1],(a[i]+1)%2+min(Goright[-1],Reright[-1])))
        Reright.append(min(rightsum[i+1],a[i]%2+Reright[-1]))
        
Releft = [0]
Goleft = [0]
for i in range(L):
    if a[L-1-i]==0:
        Releft.append(min(leftsum[i+1],2+Releft[-1]))
        Goleft.append(min(leftsum[i+1],1+min(Goleft[-1],Releft[-1])))
    else:
        Goleft.append(min(leftsum[i+1],(a[L-1-i]+1)%2+min(Goleft[-1],Releft[-1])))
        Releft.append(min(leftsum[i+1],a[L-1-i]%2+Releft[-1]))
        
#候補cand
cand = []
for i in range(L+1):
    p1 = Reright[i]
    p2 = min(Reright[i],Goright[i])
    q1 = Releft[L-i]
    q2 = min(Releft[L-i],Goleft[L-i])
    cand.append(min(p1+q2,p2+q1))
    
print(min(cand))

Submission status: Accepted

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

Asum = [0]
for i, a in enumerate(A):
    Asum.append(Asum[i] + a)

Emin = [0 for i in range(L + 1)]
Zmin = [0 for i in range(L + 1)]

for i in range(L)[:: -1]:
    a = A[i]
    if a == 0:
        Emin[i] = 2 + Emin[i + 1]
        Zmin[i] = 1 + min(Emin[i + 1], Zmin[i + 1])
    elif a % 2 == 0:
        Emin[i] = Emin[i + 1]
        Zmin[i] = 1 + min(Emin[i + 1], Zmin[i + 1])
    else:
        Emin[i] = 1 + Emin[i + 1]
        Zmin[i] = min(Emin[i + 1], Zmin[i + 1])
    Emin[i] = min(Emin[i], Asum[L] - Asum[i])
    Zmin[i] = min(Zmin[i], Asum[L] - Asum[i])


A.reverse()

Asum = [0]
for i, a in enumerate(A):
    Asum.append(Asum[i] + a)

Emin2 = [0 for i in range(L + 1)]
Zmin2 = [0 for i in range(L + 1)]

for i in range(L)[:: -1]:
    a = A[i]
    if a == 0:
        Emin2[i] = 2 + Emin2[i + 1]
        Zmin2[i] = 1 + min(Emin2[i + 1], Zmin2[i + 1])
    elif a % 2 == 0:
        Emin2[i] = Emin2[i + 1]
        Zmin2[i] = 1 + min(Emin2[i + 1], Zmin2[i + 1])
    else:
        Emin2[i] = 1 + Emin2[i + 1]
        Zmin2[i] = min(Emin2[i + 1], Zmin2[i + 1])
    Emin2[i] = min(Emin2[i], Asum[L] - Asum[i])
    Zmin2[i] = min(Zmin2[i], Asum[L] - Asum[i])

ans = 3000000
for i in range(L):
    ans = min(ans, min(Emin[i], Zmin[i]) + min(Emin2[L - i], Zmin2[L - i]))

print(ans)

Submission status: Accepted

Solution code:

def main():
    buf = input()
    L = int(buf)
    A = []
    for i in range(L):
        buf = input()
        A.append(int(buf))
    print(min(calc_move_count(A), calc_move_count(list(reversed(A)))))

def calc_move_count(A):
    stone_diff = []
    for i in A:
        if i == 0:
            stone_diff.append(1)
        elif i % 2 == 0:
            stone_diff.append(-1)
        else:
            stone_diff.append(0)
    no_left_sum = []
    for i in reversed(stone_diff):
        if not no_left_sum:
            no_left_sum.append(abs(i))
        else:
            no_left_sum.append(no_left_sum[-1] + abs(i))
    no_left_sum = list(reversed(no_left_sum))
    no_left_sum.append(0)
    move_left = [0]
    for i in A:
        if not move_left:
            move_left.append(i)
        else:
            move_left.append(move_left[-1] + i)
    move_right = []
    for i in reversed(A):
        if not move_right:
            move_right.append(i)
        else:
            move_right.append(move_right[-1] + i)
    move_right = list(reversed(move_right))
    move_right.append(0)
    dp = [[0, no_left_sum[0], 0, move_right[0]]]
    for i in range(len(A)):
        l = []
        l.append(min(move_left[i+1], dp[-1][0]+abs(stone_diff[i]+1)))
        l.append(min(move_left[i+1], l[0], dp[-1][1]+abs(stone_diff[i])-no_left_sum[i]) + no_left_sum[i+1])
        l.append(min(move_left[i+1], l[1]-no_left_sum[i+1], dp[-1][2]+abs(stone_diff[i]+1)))
        l.append(min(dp[-1][3], l[2] + move_right[i+1]))
        dp.append(l)
    return dp[-1][3]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
L = int(input())
a=[int(input()) for i in range(L)]
if L == 1:
    print(0)
    exit()
    
rightsum = [0]*(L+1)
leftsum = [0]*(L+1)
for i in range(1,L+1):
    rightsum[i] = rightsum[i-1]+a[i-1]
    leftsum[L-i] = leftsum[L+1-i]+a[L-i]
leftsum=leftsum[::-1]

Reright = [0]
Goright = [0]
for i in range(L):
    res = Reright[-1] 
    if a[i] == 0:
        Reright.append(min(rightsum[i+1],2+Reright[-1]))
        Goright.append(min(rightsum[i+1],1+min(Goright[-1],res)))
    else:
        Reright.append(min(rightsum[i+1],a[i]%2+Reright[-1]))
        Goright.append(min(rightsum[i+1],(a[i]+1)%2+min(Goright[-1],res)))
Releft = [0]
Goleft = [0]

for i in range(L):
    res = Releft[-1]
    if a[L-1-i]==0:
        Releft.append(min(leftsum[i+1],2+Releft[-1]))
        Goleft.append(min(leftsum[i+1],1+min(Goleft[-1],res)))
    else:
        Releft.append(min(leftsum[i+1],a[L-1-i]%2+Releft[-1]))
        Goleft.append(min(leftsum[i+1],(a[L-1-i]+1)%2+min(Goleft[-1],res)))



cand = []
for i in range(L+1):
    p1 = Reright[i]
    p2 = min(Reright[i],Goright[i])
    q1 = Releft[L-i]
    q2 = min(Releft[L-i],Goleft[L-i])
    cand.append(min(p1+q2,p2+q1))
    
print(min(cand))

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for _ in range(L)]

INF = 1E50
ans1 = sum(A)  # None
ans2 = ans1 - 1 if ans1 > 0 else 0

a_alpha_t = list(map(lambda x: 2 if x == 0 else x % 2, A))
a_b_t = list(map(lambda x: (x + 1) % 2, A))

total_val = 0
a_b_val = 0
a_alpha_val = 0
total = [0 for _ in range(L)]
a_b = list(total)
a_alpha = list(total)
for i in range(L):
    total_val += A[i]
    a_b_val += a_b_t[i]
    a_alpha_val += a_alpha_t[i]
    total[i] = total_val
    a_b[i] = a_b_val
    a_alpha[i] = a_alpha_val








ans = [0 for _ in range(5)]
for i, a in enumerate(A):
    tmp_ans=  [INF for _ in range(5)]
    tmp_ans[0] = total[i]
    tmp_ans[1] = min(ans[1]+a_alpha_t[i],total[i])
    tmp_ans[2]= min(tmp_ans[1],ans[2]+a_b_t[i])
    tmp_ans[3]= min(tmp_ans[2],ans[3]+a_alpha_t[i])
    tmp_ans[4] = min(tmp_ans[3],ans[4]+A[i])
    ans = tmp_ans

print(min(ans+[ans1,ans2]))

Submission status: Accepted

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回以下

0 zzoo
1 zzee
2 zzooee
3 zzeeoo
4 zzeeooee
5 zz
6 ???zz
"""

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

T = [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[5]+o),
    min(P[1]+e, P[5]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+e, P[3]+e),
    P[5]+a,
    min(P)+a,
  ]
  #print a, T
print min(T)

Submission status: Accepted

Solution code:
l = int(input())
aList = [int(input()) for _ in range(l)]

INF = 10 ** 6

dp = [[INF] * (l + 1) for _ in range(5)]
for i in range(5):
    dp[i][0] = 0
for i in range(l):
    for state in range(5):
        if state == 4:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + aList[i]
        elif state == 3:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + (aList[i] % 2 if aList[i] != 0 else 2)
        elif state == 2:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + (aList[i] - 1) % 2

        elif state == 1:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + (aList[i] % 2 if aList[i] != 0 else 2)
        else:
            dp[state][i + 1] = min(dp[j][i] for j in range(state + 1)) + aList[i]
            
ans = INF
for i in range(5):
    ans = min(ans, dp[i][l])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#k,a,b = [int(i) for i in input().split()]

l = int(input())
a = [int(input()) for i in [0]*l]
asum=[0]*(l+1)
for i in range(1,l+1):
    asum[i] = asum[i-1]+a[i-1]    

reven=[0]*(l+1)
leven=[0]*(l+1)
rodd=[0]*(l+1)
lodd=[0]*(l+1)

for i in range(1,l+1):
    if a[i-1] != 0:
        leven[i]=leven[i-1] + a[i-1]%2
    else:
        leven[i]=min(2+leven[i-1],asum[i])

for i in range(l-1,-1,-1):
    if a[i] != 0:
        reven[i]=reven[i+1] + a[i]%2
    else:
        reven[i]=min(2+reven[i+1],asum[l]-asum[i])

for i in range(1,l+1):
    lodd[i]=min(leven[i], lodd[i-1]+(a[i-1]+1)%2, asum[i])

for i in range(l-1,-1,-1):
    rodd[i]=min(reven[i], rodd[i+1]+(a[i]+1)%2, asum[l]-asum[i])

#print(asum)
#print(reven)
#print(leven)
#print(rodd)
#print(lodd)

ans = 5*(l+2)
for i in range(l+1):
    ans = min(ans, leven[i]+rodd[i], lodd[i]+reven[i])

print(ans)

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for i in range(L)]
dp = [[0]*5 for _ in range(L+1)]
for i in range(1, L+1):
    a = A[i-1]
    g = a%2
    dp[i][0] = dp[i-1][0] + a
    dp[i][1] = min(dp[i-1][:2]) + (g if a!=0 else 2)
    dp[i][2] = min(dp[i-1][:3]) + (1-g if a!=0 else 1)
    dp[i][3] = min(dp[i-1][:4]) + (g if a!=0 else 2)
    dp[i][4] = min(dp[i-1]) + a
print(min(dp[-1]))

Submission status: Accepted

Solution code:
L, = map(int, raw_input().split())
A = [0]*L
dp = []
for i in xrange(L):
  A[i], = map(int, raw_input().split())
  dp.append([float("inf")]*5)
i=0
e = 2-A[i] if A[i]<2 else A[i]%2
o = 1 if A[i]==0 else (A[i]+1)%2
dp[0][0] = A[0]
dp[0][1] = e
dp[0][2] = o
dp[0][3] = e
dp[0][4] = A[0]
for i in xrange(1, L):
  e = 2-A[i] if A[i]<2 else A[i]%2
  o = 1 if A[i]==0 else (A[i]+1)%2
  dp[i][0] = min(dp[i-1][:1]) + A[i]
  dp[i][1] = min(dp[i-1][:2]) + e
  dp[i][2] = min(dp[i-1][:3]) + o
  dp[i][3] = min(dp[i-1][:4]) + e
  dp[i][4] = min(dp[i-1][:5]) + A[i]
print min(dp[-1])

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [int(stdin.readline()) for _ in xrange(n)]
    while a and not a[-1]:
        a.pop()
    a.reverse()
    while a and not a[-1]:
        a.pop()
    n = len(a)
    p = [0] * n
    q = [0] * n
    for i in xrange(n):
        if not a[i]:
            p[i] = 1
            q[i] = 2
        else:
            p[i] = 1 - a[i] % 2
            q[i] = a[i] % 2
    l = [(0, 0, 0)] * (n + 1)
    r = [(0, 0, 0)] * (n + 1)
    for i in xrange(n):
        l[i+1] = (l[i][0] + a[i], min(l[i][0], l[i][1]) + q[i], min(l[i]) + p[i])
    for i in xrange(n - 1, -1, -1):
        r[i] = (r[i+1][0] + a[i], min(r[i+1][0], r[i+1][1]) + q[i], min(r[i+1]) + p[i])
    ans = min(min(l[i]) + min(r[i]) for i in xrange(n + 1))
    print ans
main()

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for i in range(L)]
X = [[0] * 5 for _ in range(L+1)]

X[0] = [0] * 5
for i in range(L):
    X[i+1][0] = X[i][0] + A[i]
    X[i+1][1] = min(X[i][0], X[i][1]) + (A[i] % 2 if A[i] > 0 else 2)
    X[i+1][2] = min(X[i][0], X[i][1], X[i][2]) + ((A[i]+1) % 2)
    X[i+1][3] = min(X[i][0], X[i][1], X[i][2], X[i][3]) + (A[i] % 2 if A[i] > 0 else 2)
    X[i+1][4] = min(X[i][0], X[i][1], X[i][2], X[i][3], X[i][4]) + A[i]

print(min(X[-1]))

Submission status: Runtime Error

Solution code:
K, A, B = map(int, input().split())
if B - A <= 2 :
  print(K + 1)
elif K < A + 1:
  print(K + 1)
elif K == A + 1:
  print(B)
else :
  count = K - (A + 1)
  if count % 2 == 1:
    ans = count // 2 * (B - A) + B
  else:
    ans = count//2 * (B - A) + B + 1
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
b = [0]*n
for i in range(n):
  if a[i]%2:
    b[i] = 1
  elif a[i]:
    b[i] = 2
n += 1
DP = [[10**18 for i in range(5)] for j in range(n+1)]
for i in range(5):
    DP[0][i] = 0
for i in range(1,n+1):
  for j in range(5):
    for k in range(j,5):
      if k == 0 or k == 4:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+a[i-1])
      elif k == 1 or k == 3:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+abs(b[i-1]-1))
      else:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+abs(b[i-1]-2))
print(min(DP[n]))

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
long long f[N][5];
int n, a[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n ; i ++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n ; i ++)
    {
        for (int j = 0; j < 5; j ++)
            f[i + 1][j] = 1e18;
        for (int j = 0; j < 5; j ++)
            for (int k = j; k < 5; k ++)
                if (k == 0 || k == 4)
                    f[i + 1][k] = min(f[i + 1][k], f[i][j] + a[i + 1]);
                else
                    if (k == 1 || k == 3)
                    {
                        if (a[i + 1] == 0)
                            f[i + 1][k] = min(f[i + 1][k], f[i][j] + 2);
                        else
                            f[i + 1][k] = min(f[i + 1][k], f[i][j] + (a[i + 1] & 1));
                    } else
                        f[i + 1][k] = min(f[i + 1][k], f[i][j] + ((a[i + 1] & 1) == 0));
    }
    long long ans = 1e18;
    for (int i = 0; i < 5; i++)
        ans = min(ans, f[n][i]);
    printf("%lld\n", ans);
    return 0;
}

Submission status: Runtime Error

Solution code:
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L)]

mod=A[0]%2
if A[0]==0 :
    mod=2
DP[1]=[A[0],min(A[0],mod%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2),min(A[0],mod%2,(mod+1)%2)]

for i in range(2,L):
    mod=A[i]%2
    if A[i]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i]

#print(DP)
print(min(DP[L-1]))

Submission status: Runtime Error

Solution code:
L=int(input())
A=[int(input()) for i in range(L)]
su=sum(A)
#print(A)

DP=[[0 for i in range(5)] for j in range(L)]

DP[1]=[A[0],min(A[0],A[0]%2),min(A[0],A[0]%2,(A[0]+1)%2),min(A[0],A[0]%2,(A[0]+1)%2),min(A[0],A[0]%2,(A[0]+1)%2)]

for i in range(2,L):
    mod=A[i]%2
    if A[i]==0 :
        mod=2
    DP[i][0]+=DP[i-1][0]+A[i]
    DP[i][1]+=min(DP[i-1][0],DP[i-1][1])+mod
    DP[i][2]+=min(DP[i-1][j] for j in range(3))+(mod+1)%2
    DP[i][3]+=min(DP[i-1][j] for j in range(4))+mod
    DP[i][4]+=min(DP[i-1][j] for j in range(5))+A[i]

#print(DP)
print(min(DP[L-1]))

Submission status: Runtime Error

Solution code:
a = int(input())

b = []

for i in range(a):
	b.append(int(input()))

c = [[0] * 5 for i in range(a+1)]

for i in range(a):
	c[i+1][0] = c[i][0] + b[i]
	c[i+1][1] = min(c[i][0],c[i][1]) + (b[i] % 2 if b[i] > 0 else 2)
	c[i+1][2] = min(c[i][0][,c[i][1],c[i][2]]) + ((b[i]+1) % 2)
	c[i+1][3] = min(c[i][0][,c[i][1],c[i][2]],c[i][3]) + (b[i] % 2 if b[i] > 0 else 2)
	c[i+1][4] = min(c[i][0][,c[i][1],c[i][2]],c[i][3],c[i][4]) + b[i]

print(min(c[-1]))

Submission status: Runtime Error

Solution code:
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "sol"

const int64_t MAX_N = 200002;
const int64_t INF = 1e9;

int n;
int64_t a[MAX_N], cost0[MAX_N], cost1[MAX_N];
int64_t f0[MAX_N], f1[MAX_N], f2[MAX_N], f3[MAX_N], f4[MAX_N];

void readInput() {
	cin >> n;
	for (int i=1; i<=n; ++i)
		cin >> a[i];
}

void solve() {
	int64_t min_f0, min_f1, min_f2, min_f3;

	min_f0 = min_f1 = min_f2 = min_f3 = 0;

	for (int i=1; i<=n; ++i) {
		cost0[i] = cost0[i-1] + (a[i]==0 ? 2 : a[i]%2);
		cost1[i] = cost1[i-1] + (a[i]+1)%2;

		f0[i] = f0[i-1] + a[i];
		min_f0 = min(min_f0, -cost0[i]+f0[i]);

		f1[i] = cost0[i] + min_f0;
		min_f1 = min(min_f1, -cost1[i]+f1[i]);

		f2[i] = cost1[i] + min_f1;
		min_f2 = min(min_f2, -cost0[i]+f2[i]);

		f3[i] = cost0[i] + min_f2;
		min_f3 = min(min_f3, -f0[i]+f3[i]);

		f4[i] = f0[i] + min_f3;
	}
	// debug(min_f0);

	cout << f4[n];
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	readInput();
	solve();
}

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
B=[0]*N
for i in range(N):
    if A[i]>0:
        if A[i]%2==0:
            B[i]=2
        else:
            B[i]=1
L=[0,2,1,2,0]
dp=[[10**9]*5 for i in range(N+1)]
for k in range(5):
    dp[0][k]=0
for i in range(1,N+1):
    for k in range(5):
        for k1 in range(k+1):
            if 1<=k<=3:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+abs(L[k]-B[i-1]))
            else:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+A[i-1])
ans=10**9
#print(B)
#print(dp)
for a in range(5):
    ans=min(ans,dp[N][a])
print(ans)v

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-11

#DP
L = int(input())
DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    cos = cost(a)
    DP[4] = n[4] + cos[4]
    DP[3] = n[3] + cos[3]
    DP[2] = n[2] + cos[2]
    DP[1] = n[1] + cos[1]
    DP[0] = n[0] + cos[0]

print(min(DP))

Submission status: Runtime Error

Solution code:
# https://yahoo-procon2019-qual.contest.atcoder.jp/tasks/yahoo_procon2019_qual_d

L = int(input())

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

INF = int(1e15)
dp = [[INF] * (L + 1) for _ in range(5)]

for i in range(4):
    dp[i][0] = 0

for i in range(n):
    dp[0][i + 1] = dp[0][i] + A[i]  # 全部取り除く
    dp[1][i + 1] = min(dp[j][i] for j in range(2)) + (A[i] % 2 if A[i] != 0 else 2)
    dp[2][i + 1] = min(dp[j][i] for j in range(3)) + (1 if A[i] % 2 == 0 else 0)
    dp[3][i + 1] = min(dp[j][i] for j in range(4)) + (A[i] % 2 if A[i] != 0 else 2)
    dp[4][i + 1] = min(dp[j][i] for j in range(5)) + A[i]  # 全部取り除く


print(min(dp[i][L] for i in range(1, 5)))

Submission status: Runtime Error

Solution code:
# https://yahoo-procon2019-qual.contest.atcoder.jp/tasks/yahoo_procon2019_qual_d

L = int(input())

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

INF = int(1e15)
dp = [[INF] * (L + 1)] for _ in range(5)]

for i in range(4):
    dp[i][0] = 0

for i in range(n):
    dp[0][i + 1] = dp[0][i] + A[i]  # 全部取り除く
    dp[1][i + 1] = min(dp[j][i] for j in range(2)) + (A[i] % 2 if A[i] != 0 else 2)
    dp[2][i + 1] = min(dp[j][i] for j in range(3)) + (1 if A[i] % 2 == 0 else 0)
    dp[3][i + 1] = min(dp[j][i] for j in range(4)) + (A[i] % 2 if A[i] != 0 else 2)
    dp[4][i + 1] = min(dp[j][i] for j in range(5)) + A[i]  # 全部取り除く


print(min(dp[i][L] for i in range(1, 5)))

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

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

DP = [[float("inf") for i in range(5)] for j in range(L+1)]
for i in range(L+1):
    DP[0][i] = 0

def cost(s, i, A):
    if s == 0 or s == 4:
        return A[i]
    elif s == 1 or s == 3:
        if A[i] > 0:
            if A[i]%2 == 0:
                return 0
            else:
                return 1
        else:
            return 2
    else:
        if A[i]%2 == 1:
            return 0
        else:
            return 1

for i in range(L):
    for j in range(5):
        for k in range(j,5):
            DP[i+1][k] = min(DP[i+1][k], DP[i][j]+ cost(k, i, A))



print(min(DP[L]))

Submission status: Runtime Error

Solution code:
dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    m = x % 2
    y = m + (x == 0) * 2
    z = 1 - m
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Submission status: Runtime Error

Solution code:
from itertools import accumulate,chain

"""
 i    j   k    l
0-even-odd-even-0

0: 0->0, n->n
even: 0->2, 1->1, 2->0
odd: 0->1, 1->0, 2->1
"""

L = int(input())
A = list(int(input()) for _ in range(L))

sA = list(chain((0,), accumulate(A)))
eA = list(chain((0,), accumulate(a%2 for a in A)))
zA = list(chain((0,), accumulate(a==0 for a in A)))


_,i = min((+sA[i]-eA[i]-2*zA[i],i) for i in range(L+1))
_,l = max((+sA[i]-eA[i]-2*zA[i],i) for i in range(L+1))
_,j = min((+zA[i]+eA[i]*2-i,i) for i in range(i,l+1))
_,k = max((+zA[i]+eA[i]*2-i,i) for i in range(i,l+1))

if not i <= j:
  j = i
if not j <= k:
  k = j


cost = sA[i]+(sA[L]-sA[l])
cost += (zA[j]-zA[i])*2 + eA[j]-eA[i]
cost += (zA[l]-zA[k])*2 + eA[l]-eA[k]
cost += (zA[k]-zA[j]) + (k-j-eA[k]+eA[j])
print(cost)

Submission status: Runtime Error

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

for i in range(L):
    if a[i]>0:
        a[i] = a[i] - ((a[i]-1)//2)*2
        #a[i] = (a[i]%2+1)%2+1

import numpy as np

#right


#12s
b = np.zeros(L)
b+=1
right_12s_lis=[]
for i in range(L):
    b[-i-1]=2
    right_12s_lis.append(sum(abs(a-b)))
    
ind_12s = np.argmin(np.array(right_12s_lis))
#use [-ind_12s-1]
val_12s=  min(right_12s_lis)

#10s
b = np.zeros(L)
right_10s_lis =[]
for i in range(L):
    b[-i-1]=0
    right_10s_lis.append(sum(abs(a-b)))
    
right_ind_10s = np.argmin(np.array(right_10s_lis))
#use [-ind_12s-1]
val_10s=  min(right_10s_lis)

#120s
b10 = np.zeros(L)
b10[:-ind_10s-1]=0
right_120s_lis=[]
for i in range(L-ind_10s):
    b10[-i-ind_10s]=2
    right_120s_lis.append(sum(abs(a-b)))
ind_120s = np.argmin(np.array(right_120s_lis))
val_120s = min(right_120s_lis)

right_flag=0
if val_12s<=val_120s:
    right_flag=1
    right_ind = ind_12s
else:
    right_flag=2
    right_ind =  ind_120s

#left

#12s
b = np.zeros(L)
b+=1
left_12s_lis=[]
for i in range(L):
    b[i]=2
    left_12s_lis.append(sum(abs(a-b)))
    
ind_12s = np.argmin(np.array(left_12s_lis))
#use [-ind_12s-1]
val_12s=  min(left_12s_lis)

#10s
b = np.zeros(L)
left_10s_lis =[]
for i in range(L):
    b[i]=0
    left_10s_lis.append(sum(abs(a-b)))
    
left_ind_10s = np.argmin(np.array(left_10s_lis))
#use [-ind_12s-1]
val_10s=  min(left_10s_lis)

#120s
b10 = np.zeros(L)
b10[:ind_10s]=0
left_120s_lis=[]
for i in range(L-ind_10s):
    b10[ind_10s:i]=2
    left_120s_lis.append(sum(abs(a-b)))
ind_120s = np.argmin(np.array(left_120s_lis))
val_120s = min(left_120s_lis)

left_flag = 0
if val_12s<=val_120s:
    left_flag=1
    left_ind = ind_12s
else:
    left_flag=2
    left_ind =  ind_120s

final_answer = np.ones(L)
if left_flag==1:
    final_answer[:left_ind]=2
else:
    final_answer[:left_ind_10s]=0
    final_answer[left_ind_10s:left_ind]=2

if right_flag==1:
    final_answer[-1-right_ind:]=2
else:
    final_answer[-1-right_ind_10s:]=0
    final_answer[-1-right_ind:-1-right_ind_10s]=2
    
print(int(sum(abs(a-final_answer))))

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] and f==1:
    s0+=O[i]
    A=A[i+1:]

  if A[i]==1:
    f=1
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]:
    s0+=O[i]
    A=A[i+1:]

    break

print(min(s,s0))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
l = int(input())
a_list = []
tmp_list = []
ans = 0
for _ in range(l):
    a = int(input())
    if a == 0 and len(tmp_list)>0:
        a_list.append(tmp_list)
        tmp_list = []
    elif a > 0:
        tmp_list.append(a)
if len(tmp_list) > 0:
    a_list.append(tmp_list)
a_list.sort(key=len, reverse=True)
ans += len(a_list) - 1
flag = -1
check = 0
for i in range(len(a_list[0])):
    if i == 0:
        if a_list[0][i] % 2 == 0:
            flag = 0
        else:
            flag = 1
    else:
        if flag == 0:
            if a_list[0][i] % 2 == 1:
                check += 1
                flag = 1
        else:
            if a_list[0][i] % 2 == 1:
                check += 1
                flag = 0
if check > 1:
    ans += check - 1
print(ans)

Submission status: Runtime Error

Solution code:
def f(n):
  if n==0:
    return [1,2]
  if n%2 == 0:
    return [1,0]
  return [0,1]
l = int(input())
x = [0]
x1 = 0
y = [0]
y1 = 0
z = [0]
z1 = 0
ll = []
for i in range(l):
  a = int(input())
  g = f(a)
  if a > l:
    l.append(i)
  x1 += a
  y1 += g[0]
  z1 += g[1]
  x.append(x1)
  y.append(y1)
  z.append(z1)
mn = min(try ll  l-1) 
mx = max(try ll else 0)
ans = l
for i in range(mn):
  si = x[i-1]
  for k in range(mx,l):
    sk = x[l-1]-x[k]
    for j in range(i-1,k+2):
      p = y[j]-y[i-1]
      q = z[j] - z[i-1]
      r = y[k] - y[j-1]
      s = z[k] - z[j-1]
      ssss = min(p+s,q+r)
      if ssss < ans:
        ans = ssss
print(ans)

Submission status: Runtime Error

Solution code:
L = int(input())
A = [int(input()) for i in range(L)]
# print(A)

# 始まるところで分けて咲き進む方で奇数なら1,偶数なら0、後から進む方はその逆、最後尾に0があればそれは数えない

res=10**9
left_back=0
left_first=0
right_first=0
right_back=0
t=0
#print(A)
index=0
for i in A:
    if(index==0 and i== 0):
        flag=1
        t+=1
        #print("A:",i)
    elif(i==0 and flag==1):
        t+=1
        #print("B:",i)
    else:
        flag = 0
        #print("C;",i)
    index+=1

A = A[t:]
A = A[::-1]
# print(A)
t=0
index=0
for i in A:
    if(index==0 and i== 0):
        flag=1
        t+=1
        #print("A:",i)
    elif(i==0 and flag==1):
        t+=1
        #print("B:",i)
    else:
        flag = 0
        #print("C;",i)
    index+=1

A = A[t:]
A = A[::-1]
# rint(A)
# 逆順OK
left_right=0
right_left=0
res_p=0
i_res=0
for i in range(L):
    left_right=0
    right_left=0
    left_back=0
    left_first=0
    right_first=0
    right_back=0    
    for j in A[:i]:
        #print(j)
        left_first += j%2
        if(j%2==0):
            left_back += 1
        if(j==0):
            left_first +=1
    if(A[0]%2==0):
        left_back-=1
    #print(":::")

    for k in A[i:]:
        #print(k)
        right_first += k%2
        
        if(k%2==0):
            right_back += 1
        if(k==0):
            right_first+=1
    if(A[-1]%2==0):
        right_back-=1
    # print(A[0],A[-1])
    
    left_right = left_first+right_back
    right_left = right_first + left_back
    res_p=res
    res = min(res,left_right,right_left)
    if(res<res_p):
        i_res=i

    #print("====")
print(res)
# print(i_res)
# print(0//2)
#print(A[i_res::])
#for i in A[i_res::]:
    #print(i%2)

Submission status: Runtime Error

Solution code:
def remcomp(lis):
	l = len(lis)
	max = sum(lis)
	res = max
	mem = 0
	for i in range(l):
		if lis[i] == 0:
			memm = mem
			cul = max - sum(lis[mem:i])
			res = min(res,cul)
			mem = i
	return([res,memm,mem])

L = int(input())
A = [0 for i in range(L+1)]
B = [0 for i in range(L+1)]

for i in range(L):
	A[i] = int(input())
	B[i] = A[i] % 2

print(remcomp(A)[0]+remcomp(B[memm,mem+1].append(0))[0])

Submission status: Runtime Error

Solution code:
L = int(input())
A =[]
for i in range(L):
    A.append(int(input()))
def reader(x):
    s = 0
    for i in x:
        if i ==0:
            s = s -1
        else:
            s = s + i
    return s
j = 0
flag = 0
startpoint = []
endpoint = []
for i in A:
    j = j+1
    if i == 0:
        if flag ==1:
            endpoint.append(j-2)
            flag = 0
    else:
        if flag == 0:
            startpoint.append(j-1)
            flag = 1
menseki = []
for s in startpoint:
    for e in endpoint:
        menseki.append(reader(A[s:(e+1)]))
m = max(menseki)
real = reader(A)
print(real-m)