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:
L=int(input())


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

    if a % 2 == 1:
        temp_k += 1
    else:
        if (ma_k < temp_k):
            ma_k = temp_k
        temp_k = 0

if(ma_k>ma_g):
    print(ma_k)
else:
    print(ma_g)

Submission status: Wrong Answer

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
print(ceil(even/2))

Submission status: Wrong Answer

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
print(ceil(even//2))

Submission status: Wrong Answer

Solution code:
L=int(input())


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

print(ma-1)

Submission status: Time Limit Exceeded

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]-2))
      else:
        DP[i][k] = min(DP[i][k],DP[i-1][j]+abs(b[i-1]-1))
print(min(DP[n]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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])
"""

P1 = P1[::-1]
P2 = P2[::-1]

dp = np.zeros((N+1, 4), dtype=int)
dp[0, :] = np.array([P1[0], P1[0]+P2[0], -P1[0], 0])
for i, (p1, p2) in enumerate(zip(P1, P2)):
    if i == 0: continue
    dp[i, 0] = np.maximum(dp[i-1, 0], p1)
    dp[i, 1] = np.maximum(dp[i-1, 1], p2+dp[i, 0])
    dp[i, 2] = np.minimum(dp[i-1, 2], p2-dp[i, 1])
    dp[i, 3] = np.minimum(dp[i-1, 3], p1+dp[i, 2])

print(dp[N, 3]+S)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

p1 = 0
p2 = 0
P1 = np.zeros(N+1, dtype=int)
P2 = np.zeros(N+1, dtype=int)
for i, a in enumerate(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[N-1-i] = p1
    P2[N-1-i] = 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])
"""

dp = np.zeros((N+1, 4), dtype=int)
dp[0, :] = np.array([P1[0], P1[0]+P2[0], -P1[0], 0])
for i, (p1, p2) in enumerate(zip(P1, P2)):
    if i == 0: continue
    dp[i, 0] = np.maximum(dp[i-1, 0], p1)
    dp[i, 1] = np.maximum(dp[i-1, 1], p2+dp[i, 0])
    dp[i, 2] = np.minimum(dp[i-1, 2], p2-dp[i, 1])
    dp[i, 3] = np.minimum(dp[i-1, 3], p1+dp[i, 2])

print(dp[N, 3]+S)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

p1 = 0
p2 = 0
P1 = np.zeros(N+1)
P2 = np.zeros(N+1)
for i, a in enumerate(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[N-1-i] = p1
    P2[N-1-i] = 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])
"""

dp = np.zeros((N+1, 4), dtype=int)
dp[0, :] = np.array([P1[0], P1[0]+P2[0], -P1[0], 0])
for i, (p1, p2) in enumerate(zip(P1, P2)):
    if i == 0: continue
    dp[i, 0] = np.maximum(dp[i-1, 0], p1)
    dp[i, 1] = np.maximum(dp[i-1, 1], p2+dp[i, 0])
    dp[i, 2] = np.minimum(dp[i-1, 2], p2-dp[i, 1])
    dp[i, 3] = np.minimum(dp[i-1, 3], p1+dp[i, 2])

print(dp[N, 3]+S)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
A = np.array(A, dtype=int)

# dp[i]: i まで見たときの答えの最小値
# dp[i][0]: どこも通ってない
# dp[i][1]: D まで通った
# dp[i][2]: S まで通った
# dp[i][3]: T まで通った
# dp[i][4]: U まで通った
dp = np.zeros((N, 5), dtype=int)

dp[:, 0] = A.cumsum()
dp[0, 1] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0, 2] = int(A[0] % 2 != 1)
dp[0, 3] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0, 4] = A[0]
for i in range(1, N):
    dp[i, 1] = dp[i - 1, :1 + 1].min() + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i, 2] = dp[i - 1, :2 + 1].min() + int(A[i] % 2 != 1)
    dp[i, 3] = dp[i - 1, :3 + 1].min() + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i, 4] = dp[i - 1, :4 + 1].min() + A[i]
print(dp[-1].min())

Submission status: Time Limit Exceeded

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

def main():
  l = int(input())
  dp = [[float('inf') for _ in range(l+1)] for _ in range(5)]
  dp[0][0] = 0
  for i in range(l):
    a = int(input())
    for j in range(5):
      for k in range(j, 5):
        cost = a
        if k == 1 or k == 3:
          if a % 2 == 0 and a > 0:
            cost = 0
          elif a > 0:
            cost = 1
          else:
            cost = 2
        elif k == 2:
          if a % 2 == 1:
            cost = 0
          else:
            cost = 1
        if dp[k][i+1] > dp[j][i] + cost:
          dp[k][i+1] = dp[j][i] + cost
  print(min([dpp[-1] for dpp in dp]))


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
l = int(input())
al = [int(input()) for _ in range(l)]
INF = 10**15
dp = [[INF]*5 for _ in range(l+1)]  # 0,偶数,奇数,偶数,0の状態
dp[0][0] = 0

def cost(i, k):
    # i番目を状態kにした時に必要な回数
    if k==0 or k==4:
        return al[i]
    elif k==1 or k==3:
        if al[i]>0:
            return al[i]%2
        else:
            return 2
    else:
        if al[i]%2==0:
            return 1
        else:
            return 0

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(i, k)
            )

print(min(dp[l]))

Submission status: Time Limit Exceeded

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

#DP
import numpy as np
L = int(input())
A = [int(input()) for i in range(L)]

DP = np.zeros(5, dtype = int)

def cost(a:int) -> np.array:
    if a:
        return np.array([a,a%2,(a+1)%2,a%2,a])
    else:
        return np.array([0,2,1,2,0])

for i in range(L):
    n  = np.array([np.min(DP[:i+1]) for i in range(5)])
    DP = n + cost(A[i])

print(np.min(DP))

Submission status: Time Limit Exceeded

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

#DP
import numpy as np
L = int(input())
A = [int(input()) for i in range(L)]

DP = np.zeros(5, dtype = int)

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

for i in range(L):
    n  = np.array([np.min(DP[:i+1]) for i in range(5)])
    DP = n + cost(A[i])

print(np.min(DP))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from operator import itemgetter


# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]

# if __name__ == '__main__':

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

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

if __name__ == '__main__':
	dp = [[0 for j in range(5)] for i in range(L+1)]
	for i in range(L+1):
		for j in range(5):
			dp[i][j] = sys.maxsize
	
	dp[0][0] = 0
	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(i, k))

	ans = dp[L][0]
	for i in range(1, 5):
		ans = min(ans, dp[L][i])
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# D以下orUより大きい場所への遷移
def to0or4(base: int, nex: int):
    return base + nex

# Dより大きくS以下 or Gより大きくU以下の場所への遷移
def to1or3(base: int, nex: int):
    if nex == 0:
        return base + 2
    
    elif nex % 2:
        return base + 1
    
    else:
        return base


# Sより大きくG以下の場所への遷移
def to2(base: int, nex: int):
    if nex % 2:
        return base
    
    else:
        return base + 1
    
n = ni()
a = [ni() for _ in range(n)]
suma = sum(a)  

# 配るDP
dp = [[suma]*5 for _ in range(n+1)]
dp[0] = [0]*5

for i in range(n):
    for idx in range(5):
        for jdx in range(idx,5):
            
            if jdx == 0 or jdx == 4:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to0or4(dp[i][idx], a[i]))
            
            elif jdx == 1 or jdx == 3:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to1or3(dp[i][idx], a[i]))
                
            elif jdx == 2:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to2(dp[i][idx], a[i]))
   
print(min(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
L = int(input())
li = [int(input()) for i in range(L)]
li2 = [n%2 for n in li]
li3 = [1 if n == 0 else 0 for n in li]
m = L
for left in range(L+1):
    A = sum(li[:left])
    for a in range(L+1-left):
        start = left + a
        B = sum(li2[left:start]) + 2*sum(li3[left:start])
        for b in range(L+1-start):
            goal = start + b
            C = goal - start - sum(li2[start:goal])
            for c in range(L+1-goal):
                right = goal + c
                D = sum(li2[goal:right]) + 2*sum(li3[goal:right])
                E = sum(li[right:])
                x = A + B + C + D + E
                if m > x:
                    m = x
print(m)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


l = int(input())
a = [None]*l
for i in range(l):
    a[i] = int(input())
dp = [[float("inf")]*(l+1) for _ in range(5)]
for i in range(5):
    dp[i][0] = 0
def c1(v):
    if v==0:
        return 2
    else:
        return v%2
def c2(v):
    if v%2==0:
        return 1
    else:
        return 0
for i in range(1,l+1):
    v = a[i-1]
    m = dp[0][i-1]
    dp[0][i] = m + v
    m = min(m, dp[1][i-1])
    dp[1][i] = m + c1(v)
    m = min(m, dp[2][i-1])
    dp[2][i] = m + c2(v)
    m = min(m, dp[3][i-1])
    dp[3][i] = m + c1(v)
    m = min(m, dp[4][i-1])
    dp[4][i] = m + v
ans = min(dp[i][l] for i in range(5))
print(ans)

Submission status: Accepted

Solution code:
l = int(input())
a = [int(input()) for _ in range(l)]
a.insert(0, 0)
dp = [[1000000] * (l + 1) for _ in range(4)]
for i in range(4):
    dp[i][0] = 0
for i in range(1, l + 1):
    dp[0][i] = dp[0][i - 1] + a[i]
for i in range(1, 4):
    for j in range(1, l + 1):
        if i == 2:
            x = abs(a[j] % 2 - 1)
        else:
            x = abs(2 - min(a[j] % 2 + 2, a[j]))
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1] + x)
ans = dp[3][l]
s = 0
for i in range(l - 1, -1, -1):
    s += a[i + 1]
    ans = min(ans, dp[3][i] + s)
print(ans)

Submission status: Accepted

Solution code:
L=int(input())
A=[int(input()) for i in range(L)]
INF=10**16
DP=[[INF]*5 for i in range(L+1)]
DP[0]=[0]*5
for i in range(L):
  for j in range(5):
    DP[i+1][4]=min(DP[i+1][4],DP[i][j]+A[i])
  DP[i+1][0]=DP[i][0]+A[i]
  for k in [1,3]:
    for j in range(k+1):
      if A[i]:
        DP[i+1][k]=min(DP[i+1][k],DP[i][j]+(A[i]&1))
      else:
        DP[i+1][k]=min(DP[i+1][k],DP[i][j]+2)
  for j in range(3):
    DP[i+1][2]=min(DP[i+1][2],DP[i][j]+1-(A[i]&1))
print(min(DP[L]))

Submission status: Accepted

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[0], dp[1], dp[2], dp[3]) + 2
        newDP[4] = min(dp[0], dp[1], dp[2], 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[0], dp[1], dp[2], dp[3]) + 1
        newDP[4] = min(dp[0], dp[1], dp[2], 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[0], dp[1], dp[2], dp[3])
        newDP[4] = min(dp[0], dp[1], dp[2], dp[3], dp[4]) + a
    dp = newDP

print(min(dp))

Submission status: Accepted

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
    aa=[II() for _ in range(n)]

    dpl=[inf]*(n+1)
    dpl[0]=0
    s=0
    for i in range(n):
        a=aa[i]
        s+=a
        dpl[i+1]=s
        if a==0:dpl[i+1]=min(dpl[i+1],dpl[i]+2)
        else:dpl[i+1]=min(dpl[i+1],dpl[i]+a%2)
    #print(dpl)

    dpr=[inf]*(n+1)
    dpr[n]=0
    s=0
    for i in range(n-1,-1,-1):
        a=aa[i]
        s+=a
        dpr[i]=s
        if a==0:dpr[i]=min(dpr[i],dpr[i+1]+2)
        else:dpr[i]=min(dpr[i],dpr[i+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: Accepted

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],
                    min(dp[0][i], 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],
                    min(dp[0][i], dp[1][i], dp[2][i]) + (a[i]-1)%2)

for i in range(l):
    dp[3][i+1] = min(dp[2][i+1],
                    min(dp[0][i], dp[1][i], dp[2][i], 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],
                    min(dp[0][i], dp[1][i], dp[2][i], dp[3][i], dp[4][i]) + a[i])

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

Submission status: Accepted

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

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

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

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

ans = min([dp[N][4], dp[N][3], dp[N][2]])
print(ans)

Submission status: Accepted

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

L = int(input())
A = [int(input()) for _ in range(L)]
INF = 10**18
dp = [[INF] * 5 for _ in range(L+1)]
dp[0][0] = 0
# none, even, odd, even, none
for i in range(L):
    for j in range(5):
        for k in range(j, 5):
            if k in (0, 4): # none
                dp[i+1][k] = min(dp[i+1][k], dp[i][j] + A[i])
            if k in (1, 3): # even
                if A[i] == 0:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + 2)
                else:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + (A[i] % 2))
            if k == 2: # odd
                if A[i] == 0:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + 1)
                else:
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + 1 - (A[i] % 2))
print(min(dp[L]))

Submission status: Accepted

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

dat=[A[i] for i in range(N)]
for i in range(1,N):
    dat[i]+=dat[i-1]

evenf=[0]*N
evenf[0]=A[0]%2
for i in range(1,N):
    t=A[i]%2
    if A[i]==0:
        t=2
    evenf[i]=min(evenf[i-1]+t,dat[i])

evenb=[0]*N
evenb[N-1]=A[-1]%2
for i in range(N-2,-1,-1):
    t=A[i]%2
    if A[i]==0:
        t=2
    if i!=0:
        evenb[i]=min(evenb[i+1]+t,dat[-1]-dat[i-1])
    else:
        evenb[i]=min(evenb[i+1]+t,dat[-1])

oddf=[0 for i in range(N)]
for i in range(1,N):
    t=(1+A[i])%2
    oddf[i]=min(oddf[i-1]+t,evenf[i])

ans=oddf[-1]
for i in range(N-1):
    ans=min(ans,evenb[i+1]+oddf[i])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

L = ni()
# odd => 0, even => 1
A = [ni() for _ in range(L)]
assert len(A) == L

INF = 1 << 60
S = 5  # num of states


def solve():
    dp = [[INF] * S for _ in range(L + 1)]
    for s in range(S):
        dp[0][s] = 0
    for i in range(1, L + 1):
        a = A[i - 1]
        dp[i][0] = dp[i - 1][0] + a
        tm = min(dp[i - 1][0], dp[i - 1][1])
        dp[i][1] = tm + (2 if a == 0 else a % 2)
        tm = min(tm, dp[i - 1][2])
        dp[i][2] = tm + (1 - a % 2)
        tm = min(tm, dp[i - 1][3])
        dp[i][3] = tm + (2 if a == 0 else a % 2)
        tm = min(tm, dp[i - 1][4])
        dp[i][4] = tm + a
    # print(*dp, sep="\n", file=sys.stderr)
    return min(dp[L])


print(solve())

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
L=int(input())
b=[0]*5
a=[0]*5
for i in range(L):
    n=int(input())
    a[0]=b[0]+n
    a[1]=min(b[0],b[1])+n%2
    a[2]=min(b[0],b[1],b[2])+(not n%2)
    a[3]=min(b[0],b[1],b[2],b[3])+n%2
    a[4]=min(b[0],b[1],b[2],b[3],b[4])+n
    if not n:
        a[1]+=2
        a[3]+=2
    b=a.copy()
print(min(a))

Submission status: Accepted

Solution code:
import itertools

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

e_cs = [int(not (v % 2)) for v in a]
o_cs = [2 if v == 0 else v % 2 for v in a]

cs = [0] + list(itertools.accumulate(a))
cost = [a, o_cs, e_cs, o_cs, a]

# dp = [[None] * 5 for _ in range(l + 1)]
# def dfs(i=0, t=0):
#     if dp[i][t] is not None:
#         return dp[i][t]
#
#     if i == l:
#         dp[i][t] = 0
#         return 0
#     if t == 4:
#         dp[i][t] = cs[l] - cs[i]
#         return dp[i][t]
#     dp[i][t] = min(dfs(i + 1, t) + cost[t][i], dfs(i, t + 1))
#     return dp[i][t]

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

for i in reversed(range(l)):
    for t in reversed(range(5)):
        if t == 4:
            dp[i][t] = cs[l] - cs[i]
            continue
        dp[i][t] = min(dp[i + 1][t] + cost[t][i], dp[i][t + 1])

print(dp[0][0])

Submission status: Accepted

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)]
dp = [[0]*5 for _ in range(n+1)]
for i in range(n):
  dp[i+1][0] = dp[i][0] + l[i]
  dp[i+1][1] = min(dp[i][:2]) + (l[i] % 2 if l[i] else 2)
  dp[i+1][2] = min(dp[i][:3]) + (l[i] + 1) % 2
  dp[i+1][3] = min(dp[i][:4]) + (l[i] % 2 if l[i] else 2)
  dp[i+1][4] = min(dp[i][:5]) + l[i]
print(min(dp[n]))

Submission status: Accepted

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

L = int(input())
A = [int(input()) for _ in range(L)]
dpl = [[10**18]*2 for _ in range(L+1)]
dpl[0][1] = 0
acc = 0

for i in range(1, L+1):
    dpl[i][0] = min(dpl[i-1][0], dpl[i-1][1])+(1 if A[i-1]%2==0 else 0)
    acc += A[i-1]
    dpl[i][1] = acc
    
    if A[i-1]%2==0:
        if A[i-1]>=2:
            dpl[i][1] = min(dpl[i][1], dpl[i-1][1])
        else:
            dpl[i][1] = min(dpl[i][1], dpl[i-1][1]+2)
    else:
        dpl[i][1] = min(dpl[i][1], dpl[i-1][1]+1)
    
acc = 0
dpr = [[10**18]*2 for _ in range(L+1)]
dpr[L][1] = 0

for i in range(L-1, -1, -1):
    dpr[i][0] = min(dpr[i+1][0], dpr[i+1][1])+(1 if A[i]%2==0 else 0)
    acc += A[i]
    dpr[i][1] = acc
    
    if A[i]%2==0:
        if A[i]>=2:
            dpr[i][1] = min(dpr[i][1], dpr[i+1][1])
        else:
            dpr[i][1] = min(dpr[i][1], dpr[i+1][1]+2)
    else:
        dpr[i][1] = min(dpr[i][1], dpr[i+1][1]+1)

ans = 10**18

for i in range(L+1):
    ans = min(ans, dpl[i][0]+dpr[i][1], dpl[i][1]+dpr[i][0], dpl[i][1]+dpr[i][1])

print(ans)

Submission status: Accepted

Solution code:
n  = int(input())
a = [int(input()) for i in range(n)]

# 0区間、偶数区間(2以上)、奇数区間、偶数区間(2以上)、0区間
dp = [[0] * (5) for i in range(n + 1)]
for i in range(n):
    dp[i + 1][0] = dp[i][0] + a[i]

    dp[i + 1][1] = min(dp[i][0:2]) + (a[i] % 2)
    if a[i] == 0:
        dp[i + 1][1] += 2
        
    dp[i + 1][2] = min(dp[i][0:3]) + (a[i] + 1) % 2
    
    dp[i + 1][3] = min(dp[i][0:4]) + (a[i] % 2)
    if a[i] == 0:
        dp[i + 1][3] += 2
        
    dp[i + 1][4] = min(dp[i][0:5]) + a[i]

print(min(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    from itertools import accumulate as ac
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    a_ac = [0]+list(ac(a))
    s = a_ac[-1]

    dp0 = [0]*(n+1)
    dp1 = [0]*(n+1)
    dp2 = [0]*(n+1)
    dp3 = [0]*(n+1)

    for i in range(1, n+1):
        p = dp0[i-1]
        q = dp1[i-1]
        ai = a[i-1]
        dp0[i] = min(p+((ai+1) % 2), q+(ai % 2 if ai > 0 else 2), a_ac[i])
        dp1[i] = min(q+(ai % 2 if ai > 0 else 2), a_ac[i])

    for i in range(n-1, -1, -1):
        p = dp2[i+1]
        q = dp3[i+1]
        ai = a[i]
        dp2[i] = min(p+((ai+1) % 2), q+(ai % 2 if ai > 0 else 2), s-a_ac[i])
        dp3[i] = min(q+(ai % 2 if ai > 0 else 2), s-a_ac[i])

    dp_l = [min(i, j) for i, j in zip(dp0, dp1)]
    dp_r = [min(i, j) for i, j in zip(dp2, dp3)]
    print(min([i+j for i, j in zip(dp_l, dp_r)]))


main()

Submission status: Accepted

Solution code:
L = int(input())
dp = [[0]*5 for i in range(L+1)]
for i in range(L):
    x = int(input())
    c = [x, x%2 if x else 2, 1-x%2, x%2 if x else 2, x]
    for j in range(5):
        dp[i+1][j] = 10**18
        for k in range(j+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][k]+c[j])
print(min(dp[-1]))

Submission status: Accepted

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

def cost(k, a):
    if k == 0 or k == 4:
        return a

    if a % 2:
        a = 1
    elif a >= 2:
        a = 2

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

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[:: -1], 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: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [0] * N
dp = [[0] * 5 for _ in range(N + 1)]
for i in range(N): a[i] = int(input())
for i in range(N + 1):
  for j in range(5): dp[i][j] = 10 ** 15

dp[0][0] = 0
for i in range(N):
  for j in range(5):
    for k in range(j, 5):
      w = a[i]
      if k % 2:
        if a[i] > 0: w = a[i] % 2
        else: w = 2
      elif k == 2: w = int(a[i] % 2 == 0)
      dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + w)
print(min(dp[-1]))

Submission status: Accepted

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,ni)
                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()