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

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

def main():
    n = int(input())
    
    A = [0]*n
    A_sum = [0]*(n+1)
    a = [0]*n
    
    for i in range(n):
        x = int(input())
        A[i] = x
        A_sum[i+1] += A_sum[i] + x
        
        if x % 2:
            a[i] = 1
        elif x != 0:
            a[i] = 2
    
    
    odd = [0]*n
    even = [0]*n
    
    for i in range(n):
        if a[i] == 0:
            odd[i] += 1
            even[i] += 2
        elif a[i] == 1:
            even[i] += 1
        else:
            odd[i] += 1
        
    
    odd_left = [0]*(n+1)
    odd_right = [0]*(n+1)
    even_left = [0]*(n+1)
    even_right = [0]*(n+1)
    
    for i in range(n):
        odd_left[i+1] = min(A_sum[i+1], odd_left[i] + odd[i])
        even_left[i+1] = min(A_sum[i+1], even_left[i] + even[i])
    
    for i in range(n-1, -1, -1):
        odd_right[i] = min(A_sum[n] - A_sum[i], odd_right[i+1] + odd[i])
        even_right[i] = min(A_sum[n] - A_sum[i], even_right[i+1] + even[i])
    
    
    ans = 10**17
    
    for i in range(n+1):
        sub = min(odd_left[i] + even_right[i], even_left[i] + odd_right[i])
        ans = min(ans, sub)
    
    print(ans)
        
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    
    A = [0]*n
    A_sum = [0]*(n+1)
    a = [0]*n
    
    for i in range(n):
        x = int(input())
        A[i] = x
        A_sum[i+1] += A_sum[i] + x
        
        if x % 2:
            a[i] = 1
        elif x != 0:
            a[i] = 2
    
    
    odd = [0]*n
    even = [0]*n
    
    for i in range(n):
        if a[i] == 0:
            odd[i] += 1
            even[i] += 2
        elif a[i] == 1:
            even[i] += 1
        else:
            odd[i] += 1
        
    
    odd_left = [0]*(n+1)
    odd_right = [0]*(n+1)
    even_left = [0]*(n+1)
    even_right = [0]*(n+1)
    
    for i in range(n):
        odd_left[i+1] = min(A_sum[i+1], odd_left[i] + odd[i])
        even_left[i+1] = min(A_sum[i+1], even_left[i] + even[i])
    
    for i in range(n-1, -1, -1):
        odd_right[i] = min(A_sum[n] - A_sum[i], odd_right[i+1] + odd[i])
        even_right[i] = min(A_sum[n] - A_sum[i], even_right[i+1] + even[i])
    
    
    ans = 10**17
    
    for i in range(n):
        sub = min(odd_left[i] + even_right[i+1], even_left[i] + odd_right[i+1])
        ans = min(ans, sub)
    
    print(ans)
        
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
A = tuple(int(input()) for _ in range(N))

"""
0: zero_L
1: even_L
2: odd
3: even_R
4: zero_R
"""
dp = [inf] * 5
for i, a in enumerate(A):
    if i == 0:
        if a == 0:
            dp[0] = a
            dp[1] = 2
            dp[2] = 1
            dp[3] = 2
            dp[4] = a
        elif a % 2 == 0:
            dp[0] = a
            dp[1] = 0
            dp[2] = 1
            dp[3] = 0
            dp[4] = a
        else:
            dp[0] = a
            dp[1] = 1
            dp[2] = 0
            dp[3] = 1
            dp[4] = a
        continue

    newDP = [inf]*5
    if a == 0:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1]) + 2
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[2], dp[3]) + 2
        newDP[4] = min(dp[3], dp[4]) + a
    elif a % 2 == 1:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1]) + 1
        newDP[2] = min(dp[0], dp[1], dp[2])
        newDP[3] = min(dp[2], dp[3]) + 1
        newDP[4] = min(dp[3], dp[4]) + a
    else:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1])
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[2], dp[3])
        newDP[4] = min(dp[3], dp[4]) + a
    dp = newDP

print(min(dp))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
A = tuple(int(input()) for _ in range(N))

"""
0: zero_L
1: even_L
2: odd
3: even_R
4: zero_R
"""
dp = [inf] * 5
for i, a in enumerate(A):
    if i == 0:
        if a == 0:
            dp[0] = 0
            dp[1] = 2
            dp[2] = 1
        elif a % 2 == 0:
            dp[0] = 2
            dp[1] = 0
            dp[2] = 1
        else:
            dp[0] = 1
            dp[1] = 1
            dp[2] = 0
        continue

    newDP = [inf]*5
    if a == 0:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1]) + 2
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[2], dp[3]) + 2
        newDP[4] = min(dp[3], dp[4]) + a
    elif a % 2 == 1:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1]) + 1
        newDP[2] = min(dp[0], dp[1], dp[2])
        newDP[3] = min(dp[2], dp[3]) + 1
        newDP[4] = min(dp[3], dp[4]) + a
    else:
        newDP[0] = dp[0] + a
        newDP[1] = min(dp[0], dp[1])
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[2], dp[3])
        newDP[4] = min(dp[3], dp[4]) + a
    dp = newDP

print(min(dp))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
A = tuple(int(input()) for _ in range(N))

"""
0: zero_L
1: even_L
2: odd
3: even_R
4: zero_R
"""
dp = [inf] * 5
for i, a in enumerate(A):
    if i == 0:
        if a == 0:
            dp[0] = 0
            dp[1] = 2
            dp[2] = 1
        elif a % 2 == 0:
            dp[0] = 2
            dp[1] = 0
            dp[2] = 1
        else:
            dp[0] = 1
            dp[1] = 1
            dp[2] = 0
        continue

    newDP = [inf]*5
    if a == 0:
        newDP[0] = dp[0]
        newDP[1] = min(dp[0], dp[1]) + 2
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[2], dp[3]) + 2
        newDP[4] = min(dp[3], dp[4])
    elif a % 2 == 1:
        newDP[0] = dp[0] + 1
        newDP[1] = min(dp[0], dp[1]) + 1
        newDP[2] = min(dp[0], dp[1], dp[2])
        newDP[3] = min(dp[2], dp[3]) + 1
        newDP[4] = min(dp[3], dp[4]) + 1
    else:
        newDP[0] = dp[0] + 2
        newDP[1] = min(dp[0], dp[1])
        newDP[2] = min(dp[0], dp[1], dp[2]) + 1
        newDP[3] = min(dp[2], dp[3])
        newDP[4] = min(dp[3], dp[4]) + 2
    dp = newDP

print(min(dp))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    inf=10**16
    dpl=[inf]*(n+1)
    dpl[0]=0
    odd=0
    aa=[]
    for i in range(n):
        a=II()
        odd+=a%2
        dpl[i+1]=min(odd,dpl[i]+1-a%2)
        aa.append(a)
    #print(dpl)

    dpr=[inf]*(n+1)
    dpr[n]=0
    odd=0
    for i in range(n-1,-1,-1):
        a=aa[i]
        odd+=a%2
        dpr[i]=min(odd,dpr[i+1]+1-a%2)
    #print(dpr)

    even=[0]
    for a in aa:
        if a%2:even.append(even[-1])
        else:even.append(even[-1]+1)
    #print(even)

    mn=inf
    ans=inf
    for i in range(n+1):
        mn=min(mn,dpl[i]-even[i])
        cur=mn+dpr[i]+even[i]
        ans=min(ans,cur)
    #print(aa)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

l = int(readline())
a = list(map(int,read().split()))

dp = [[0] * (l+1) for _ in range(5)]

for i in range(l):
    dp[0][i+1] = dp[0][i] + a[i]

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

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

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

for i in range(l):
    dp[4][i+1] = min(dp[3][i+1],
                    dp[3][i] + a[i],
                    dp[4][i] + a[i])

print(dp[-1][-1])

Submission status: Wrong Answer

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

def cost(k, a):
    if a % 2:
        a = 1
    elif a >= 2:
        a = 2

    if k == 0 or k == 4:
        return a

    if k == 1 or k == 3:
        return 2 - a

    return 1 - a % 2

dp = [[10**18] * 5 for _ in range(L + 1)]
dp[0][0] = 0

for i, a in enumerate(A, start=1):
    for j in range(5):
        for k in range(j, 5):
            b = dp[i - 1][j] + cost(k, a)
            if dp[i][k] > b:
                dp[i][k] = b

ans = min(dp[L])
print(ans)

Submission status: Wrong Answer

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

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a == 0), dpLBack[i - 1] + (a == 0), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[-i]
    dpR[i] = min(dpR[i - 1] + (a == 0), dpRBack[i - 1] + (a == 0), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = min(dpL[L], dpR[0])
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

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

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a == 0), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[-i]
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a == 0), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = min(dpL[L], dpR[0])
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

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

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a == 0), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[-i]
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a == 0), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = 10**18
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

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

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a != 2), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[-i]
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a != 2), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = 10**18
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

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

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a != 2), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a != 2), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = 10**18
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

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

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    dpLBack[i] = dpLBack[i - 1]
    if a == 0:
        dpLBack[i] += 2
    if a == 1:
        dpLBack[i] += 1
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i], cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
for i, a in enumerate(A, start=1):
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a != 2))

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    dpRBack[i] = dpRBack[i - 1]
    if a == 0:
        dpRBack[i] += 2
    if a == 1:
        dpRBack[i] += 1
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i], cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
for i, a in enumerate(A, start=1):
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a != 2))

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = 10**18
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

Solution code:
L = int(input())
A = []

for _ in range(L):
    a = int(input())
    if a % 2:
        A.append(1)
    else:
        A.append(0 if a == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    dpLBack[i] = dpLBack[i - 1]
    if a == 0:
        dpLBack[i] += 2
    if a == 1:
        dpLBack[i] += 1
    cnt += a
    dpLBack[i] = min(dpLBack[i], cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
for i, a in enumerate(A, start=1):
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a != 2))

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    dpRBack[i] = dpRBack[i - 1]
    if a == 0:
        dpRBack[i] += 2
    if a == 1:
        dpRBack[i] += 1
    cnt += a
    dpRBack[i] = min(dpRBack[i], cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
for i, a in enumerate(A, start=1):
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a != 2))

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = 10**18
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)

Submission status: Wrong Answer

Solution code:
L = int(input())
A = [int(input()) % 4 for _ in range(L)]
A = [a % 2 if a % 2 else a for a in A]

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    dpLBack[i] = dpLBack[i - 1]
    if a == 0:
        dpLBack[i] += 2
    if a == 1:
        dpLBack[i] += 1
    cnt += a
    dpLBack[i] = min(dpLBack[i], cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
for i, a in enumerate(A, start=1):
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a != 2))

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    dpRBack[i] = dpRBack[i - 1]
    if a == 0:
        dpRBack[i] += 2
    if a == 1:
        dpRBack[i] += 1
    cnt += a
    dpRBack[i] = min(dpRBack[i], cnt)

dpR = [10**10] * (L + 1)
for i, a in enumerate(A, start=1):
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a != 2))

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = 10**18
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])
print(ans)

Submission status: Wrong Answer

Solution code:
L = int(input())
A = [int(input()) % 4 for _ in range(L)]
A = [a % 2 if a % 2 else a for a in A]

dpL = [10**10] * (L + 1)
dpL[0] = 0
for i, a in enumerate(A, start=1):
    dpL[i] = dpL[i - 1]
    if a == 0:
        dpL[i] += 2
    if a == 1:
        dpL[i] += 1

dpR = [10**10] * (L + 1)
dpR[0] = 0
for i, a in enumerate(A[:: -1], start=1):
    dpR[i] = dpR[i - 1]
    if a == 0:
        dpR[i] += 2
    if a == 1:
        dpR[i] += 1
dpR = dpR[:: -1]

accA = [0] * (L + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 10**18
for mid in range(1, L - 1):
    N = accA[L] - accA[mid]
    left = dpL[mid] + min(N, (L - mid) - N)
    right = dpR[mid] + min(accA[mid], mid - accA[mid])
    ans = min(ans, left, right)
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

"""
状態をそのままdpのインデックスとする。
https://drken1215.hatenablog.com/entry/2019/02/10/014800
"""

def solve():
    def cost(k,i):
        ai = a[i]
        if k == 0:
            return ai
        elif k == 1:
            if ai == 0:
                return 2
            return ai&1
        elif k == 2:
            return 1-(ai&1)
        elif k == 3:
            if ai == 0:
                return 2
            return ai&1
        else:
            return ai

    l = I()
    a = IR(l)
    dp = [[float("inf")]*5 for i in range(l)]
    for i in range(5):
        dp[0][i] = cost(i,0)
    for i in range(l-1):
        ni = i+1
        for j in range(5):
            for k in range(j,5):
                c = cost(k,i)
                nd = dp[i][j]+c
                if nd < dp[ni][k]:
                    dp[ni][k] = nd
    print(min(dp[l-1]))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
''' Hey stalker :) '''
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    n = get_int()
    li = [get_int() for _ in range(n)]

    def solve(li):
        prefix = [0]
        back = [0]
        for i in li:
            if i % 2 == 0 and i > 0:
                back.append(max(back[-1] + 1, 1))
            else:
                back.append(max(back[-1] - 1, -1))
        back = back[1:]
        #print(back)
        for i in li:
            prefix.append(prefix[-1]+i)
        suffix = [0]*(n+1)
        for i, ele in reversed(list(enumerate(li))):
            suffix[i] = suffix[i+1] + ele
        dp = [suffix[0]]
        #print(prefix)
        #print(suffix)
        ans = INF
        for i, ele in enumerate(li):
            dp.append(((ele%2)^1) + min(suffix[i+1] + prefix[i], dp[-1] - ele))
            ans = min(ans, dp[-1] - back[i])
            #print(i,ele, ans)
        #print(dp)
        return ans
    a1 = solve(li)
    li.reverse()
    a1 = min(a1, solve(li))
    print(a1)



''' Pythonista fLite 1.1 '''
import sys
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right
#from functools import reduce
import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()
#[main() for _ in range(int(input()))]
print(*out, sep='\n')

Submission status: Wrong Answer

Solution code:
l=int(input())
A=[int(input())for _ in range(l)]
dp=[0]*5
for i in range(l):
    a,b,c,d,e,f=dp+[A[i]]
    p=int(f==0)*2
    dp=[a+f,min(a,b)+f%2+p,min(a,b,c)+(f+1)%2,min(b,c,d)+f%2+p,min(d,e)+f]
print(min(dp))

Submission status: Wrong Answer

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
DP = [[0 for i in range(5)] for j in range(n+1)]
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] = DP[i-1][j]+a[i-1]
      elif k == 1 or k == 3:
        DP[i][k] = DP[i-1][j]+abs(b[i-1]-2)
      else:
        DP[i][k] = DP[i-1][j]+abs(b[i-1]-1)
print(min(DP[n]))

Submission status: Wrong Answer

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

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

  DP[i][1][2] = min(DP[i][1][2],DP[i-1][0][0]+abs(a[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][1][2]+abs(a[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][2][1]+abs(a[i-1]-1))

  for k in (1,2):
    DP[i][2][k] = min(DP[i][2][k],DP[i-1][2][k]+abs(a[i-1]-2))
  DP[i][2][2] = min(DP[i][2][2],DP[i-1][1][2]+abs(a[i-1]-2))
  DP[i][2][1] = min(DP[i][2][1],DP[i-1][0][0]+abs(a[i-1]-2))
print(min(*DP[n][0]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
  if a[i]%2:
    a[i] = 1
  elif a[i]:
    a[i] = 2
sm = sum(a)
DP = [[[10**18 for i in range(3)] for j in range(3)] for k in range(n+1)]
for i in range(3):
  for j in range(3):
    DP[0][i][j] = 0
for i in range(1,n+1):
  for k in (0,2):
    DP[i][0][k] = min(DP[i][0][k],DP[i-1][0][k]+abs(a[i-1]))
  for l in (1,2):
    DP[i][0][2] = min(DP[i][0][2],DP[i-1][l][2]+abs(a[i-1]))
  DP[i][0][2] = min(DP[i][0][2],DP[i-1][2][1]+abs(a[i-1]))

  DP[i][1][2] = min(DP[i][1][2],DP[i-1][0][0]+abs(a[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][1][2]+abs(a[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][2][1]+abs(a[i-1]-1))

  for k in (1,2):
    DP[i][2][k] = min(DP[i][2][k],DP[i-1][2][k]+abs(a[i-1]-2))
  DP[i][2][2] = min(DP[i][2][2],DP[i-1][1][2]+abs(a[i-1]-2))
  DP[i][2][1] = min(DP[i][2][1],DP[i-1][0][0]+abs(a[i-1]-2))
ans = 10**18
for i in range(3):
  ans = min(ans,*DP[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
  if a[i]%2:
    a[i] = 1
  elif a[i]:
    a[i] = 2
sm = sum(a)
DP = [[[sm for i in range(3)] for j in range(3)] for k in range(n+1)]
for i in range(3):
  for j in range(3):
    DP[0][i][j] = 0
for i in range(1,n+1):
  for k in (0,2):
    DP[i][0][k] = min(DP[i][0][k],DP[i-1][0][k]+abs(a[i-1]))
  for l in (1,2):
    DP[i][0][2] = min(DP[i][0][2],DP[i-1][l][2]+abs(a[i-1]))
  DP[i][0][2] = min(DP[i][0][2],DP[i-1][2][1]+abs(a[i-1]))

  DP[i][1][2] = min(DP[i][1][2],DP[i-1][0][0]+abs(a[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][1][2]+abs(a[i-1]-1))
  DP[i][1][2] = min(DP[i][1][2],DP[i-1][2][1]+abs(a[i-1]-1))

  for k in (1,2):
    DP[i][2][k] = min(DP[i][2][k],DP[i-1][2][k]+abs(a[i-1]-2))
  DP[i][2][2] = min(DP[i][2][2],DP[i-1][1][2]+abs(a[i-1]-2))
  DP[i][2][1] = min(DP[i][2][1],DP[i-1][0][0]+abs(a[i-1]-2))
ans = sm
for i in range(3):
  ans = min(ans,*DP[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
  if a[i]%2:
    a[i] = 1
  elif a[i]:
    a[i] = 2
sm = sum(a)
DP = [[[sm for i in range(3)] for j in range(3)] for k in range(n+1)]
for i in range(3):
  for j in range(3):
    DP[0][i][j] = 0
for i in range(1,n+1):
  for j in range(3):
    if j == 0:
      for k in (0,1,2):
        DP[i][0][k] = min(DP[i][0][k],DP[i-1][0][k]+abs(a[i-1]))
      for l in (1,2):
        DP[i][0][2] = min(DP[i][0][2],DP[i-1][l][2]+abs(a[i-1]))
      DP[i][0][2] = min(DP[i][0][2],DP[i-1][2][1]+abs(a[i-1]))
    if j == 1:
      DP[i][1][2] = min(DP[i][1][2],DP[i-1][0][0]+abs(a[i-1]-1))
      DP[i][1][2] = min(DP[i][1][2],DP[i-1][1][2]+abs(a[i-1]-1))
      DP[i][1][2] = min(DP[i][1][2],DP[i-1][2][1]+abs(a[i-1]-1))
    if j == 2:
      for k in (1,2):
        DP[i][2][k] = min(DP[i][2][k],DP[i-1][2][k]+abs(a[i-1]-2))
      DP[i][2][2] = min(DP[i][2][2],DP[i-1][1][2]+abs(a[i-1]-2))
      DP[i][2][1] = min(DP[i][2][1],DP[i-1][0][0]+abs(a[i-1]-2))
ans = sm
for i in range(3):
  ans = min(ans,*DP[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
  if a[i]%2:
    a[i] = 1
  elif a[i]:
    a[i] = 2
sm = sum(a)
DP = [[[sm for i in range(3)] for j in range(3)] for k in range(n+1)]
for i in range(3):
  for j in range(3):
    DP[0][i][j] = 0
for i in range(1,n+1):
  for j in range(3):
    if j == 0:
      for k in (0,2):
        DP[i][0][k] = min(DP[i][0][k],DP[i-1][0][k]+abs(a[i-1]))
      for l in (1,2):
        DP[i][0][2] = min(DP[i][0][2],DP[i-1][l][2]+abs(a[i-1]))
      DP[i][0][2] = min(DP[i][0][2],DP[i-1][2][1]+abs(a[i-1]))
    if j == 1:
      DP[i][1][2] = min(DP[i][1][2],DP[i-1][0][0]+abs(a[i-1]-1))
      DP[i][1][2] = min(DP[i][1][2],DP[i-1][1][2]+abs(a[i-1]-1))
      DP[i][1][2] = min(DP[i][1][2],DP[i-1][2][1]+abs(a[i-1]-1))
    if j == 2:
      for k in (1,2):
        DP[i][2][k] = min(DP[i][2][k],DP[i-1][2][k]+abs(a[i-1]-2))
      DP[i][2][2] = min(DP[i][2][2],DP[i-1][1][2]+abs(a[i-1]-2))
      DP[i][2][1] = min(DP[i][2][1],DP[i-1][0][0]+abs(a[i-1]-2))
ans = sm
for i in range(3):
  ans = min(ans,*DP[n][i])
print(ans)

Submission status: Wrong Answer

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

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

p1 = 0
p2 = 0
P1 = [0]
P2 = [0]
for a in A:
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1.append(p1)
    P2.append(p2)

S = sum(A)
dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N] = [P1[N], P1[N]+P2[N], P1[N], 0]

for i in reversed(range(N)):
    dp[i][0] = max(dp[i+1][0], P1[i])
    dp[i][1] = max(dp[i+1][1], P2[i]+dp[i][0])
    dp[i][2] = min(dp[i+1][2], P2[i]-dp[i][1])
    dp[i][3] = min(dp[i+1][3], P1[i]+dp[i][2])

print(dp[0][3]+S)

Submission status: Wrong Answer

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

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

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