Submission #5102973

---

Source Code Expand

import sys
input = sys.stdin.readline

L=int(input())
A=[int(input()) for i in range(L)]
            
SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)

def div2(x):
    if x==0:
        return 2
    else:
        return x%2
    
DP0=[0]*(L+1)
DP1=[0]*(L+1)
DP2=[0]*(L+1)
DP3=[0]*(L+1)


for i in range(L):
    DP0[i]=DP0[i-1]+A[i]
    DP1[i]=min(DP0[i-1]+div2(A[i]),DP1[i-1]+div2(A[i]))
    DP2[i]=min(DP2[i-1]+(A[i]+1)%2,DP1[i-1]+(A[i]+1)%2)
    DP3[i]=min(DP3[i-1]+A[i],DP2[i-1]+A[i])

ANS=min(DP0[L-1],DP1[L-1],DP2[L-1],DP3[L-1])

DP0=[0]*(L+1)
DP1=[0]*(L+1)
DP2=[0]*(L+1)
DP3=[0]*(L+1)


for i in range(L):
    DP0[i]=DP0[i-1]+A[i]
    DP1[i]=min(DP0[i-1]+(A[i]+1)%2,DP1[i-1]+(A[i]+1)%2)
    DP2[i]=min(DP2[i-1]+div2(A[i]),DP1[i-1]+div2(A[i]))
    DP3[i]=min(DP3[i-1]+A[i],DP2[i-1]+A[i])

ANS=min(DP0[L-1],DP1[L-1],DP2[L-1],DP3[L-1],ANS)

print(ANS)

Submission Info

Judge Result