Problem:


Score : 700 points

Problem Statement

N cells are arranged in a row.
Some of them may contain tokens.
You are given a string s that consists of 0s and 1s.
If the i-th character of s is 1, the i-th cell (from left) contains a token.
Otherwise, it doesn't contain a token.

Snuke wants to perform the following operation as many times as possible.
In each operation, he chooses three consecutive cells.
Let's call the cells X, Y, Z from left to right.
In order for the operation to be valid, both X and Z must contain tokens and Y must not contain a token.
Then, he removes these two tokens and puts a new token on Y.

How many operations can he perform if he performs operations in the optimal way?

Constraints

1 \leq N \leq 500,000

|s| = N

Each character in s is either 0 or 1.

Input

Input is given from Standard Input in the following format:

N
s

Output

Print the answer.

Sample Input 1

7
1010101

Sample Output 1

2

For example, he can perform two operations in the following way:

Perform an operation on the last three cells. Now the string that represents tokens becomes 1010010.

Perform an operation on the first three cells. Now the string that represents tokens becomes 0100010.

Note that the choice of operations matters.
For example, if he chooses three cells in the middle first, he can perform no more operations.

Sample Input 2

50
10101000010011011110001001111110000101010111100110

Sample Output 2

10



Sample input:
7
1010101


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5 * 10**5 + 1)
n = int(input())
a = input()
grupa = []
tmp = 0
sol = 0

def solve(niz):
    k = len(niz)
    if k < 2:
        return 0
    s = sum(x - 1 for x in niz)
    ret = max(
            s - (niz[0] - 1) + 1,
            s - (niz[k - 1] - 1) + 1
            )
    for i in range(1, k - 1):
        if niz[i] == 1:
            ret = max(ret, max(
                solve(niz[:i]) + solve(niz[i:]),
                solve(niz[:i + 1]) + solve(niz[i + 1:])
                ))
        else:
            ret = max(ret, s - (niz[i] - 1) + 2)
    return ret

a += '0'
for i in range(n + 1):
    if a[i] == '1':
        tmp += 1
    if a[i] == '0':
        if tmp > 0:
            grupa.append(tmp)
        tmp = 0
        if i == n or a[i + 1] == '0':
            sol += solve(grupa)
            grupa = []
print(sol)

Submission status: Wrong Answer

Solution code:
def get_score(q):
    score = 0
    l = len(q)
    if l < 2:
        return 0
    if l % 2 == 0:
        for i in range(0,l,2):
            score += max(q[i], q[i+1])
    else:
        m = float('inf')
        for i in range(0, l, 2):
            m = min(m, q[i])
        score = sum(q) - m - l//2
    return score


n = int(input())
s = input()
parts = list(filter(lambda x:x, map(lambda x:x.strip('0'), s.split('00'))))
total = 0
for part in parts:
    p = []
    cnt = 0
    for c in part:
        if c == '1':
            cnt += 1
        else:
            p.append(cnt)
            cnt = 0
    if cnt > 0:
        p.append(cnt)
    q = []
    L = len(p)
    for i in range(L):
        if p[i] > 1:
            if i>0 and q and q[-1] > 1:
                if q[-1] == 1:
                    pass
                else:
                    q[-1] -= 1
                    q.append(1)
                q.append(p[i]-1)
                total += 1
            else:
                q.append(p[i])
        else:
            q.append(p[i])
    total += get_score(q)
    # print(p,q)
    
print(total)
            



    # ones = list(map(lambda x:len(x)-2, part.split('0')))
    # print(part, ones)
    # len_ = len(ones)
    # if len_ <= 1:
    #     continue
    # total += len_ - 1
    # ones[0] += 1
    # ones[-1] += 1
    # print(part, sum(ones) - min(ones), ones)
    # total += sum(ones) - min(ones)
# print(total)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from copy import deepcopy
import re
result = 0


N = int(input())
s = input() + "0"

#text = s.replace("10", "a").replace("a0", "100")
text = s
ts = text.split("00")
if len(ts) > 1:
    for i in range(1, len(ts)):
        ts[i] = "0" + ts[i]
    for i in range(len(ts)-1):
        ts[i] = ts[i] + "0"

for t in ts:
    tmpa = 0
    tmpb = 0
    
    A = (t.replace("10", "a") + "0") .replace("a0", "100")
    B = (t[::-1].replace("10", "a") + "0").replace("a0", "100")
    typea = re.findall("a1+", A)
    typeb = re.findall("a1+", B)
    
    for a in typea:
        tmpa += len(a) - 1
    tmpa += re.sub("a1+", "d", A).replace("aa", "b").count("b")
    
    for b in typeb:
        tmpb += len(b) - 1
    tmpb += re.sub("a1+", "d", B).replace("aa", "b").count("b")
    result += max(tmpa, tmpb)
    
print(result)

Submission status: Wrong Answer

Solution code:
raw_input()

prev1 = '0'
prev2 = '0'
active = False
ones = 0
a = []
now = []
for c in raw_input():
  s = prev2 + prev1 + c
  if active:
    if s == '101':
      now.append(ones)
      ones = 0
    elif s == '100':
      active = False
      now.append(ones)
      a.append(now)
    if c == '1':
      ones += 1
  else:
    if prev2 == '1':
      ones += 1
    else:
      ones = 0
    if s == '101':
      now = [ones]
      active = True
      ones = 1
  prev2 = prev1
  prev1 = c
if active:
  a.append(now)

print sum(sum(sorted(xs)[-int(len(xs)/2):]) for xs in a)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
s=input()
x=len(s.split("101"))-1
y=s.split("0")
j=-1
yy=0
for i in range(len(y)):
    if (y[i]=="" or i==len(y)-1) and j!=-1:
        ii=i
        if i==len(y)-1:
            ii+=1
        x1=0
        x2=0
        for k in range(ii-j):
          if k<ii-j-1:
            if k%2==0:
             x1+=max(len(y[j:ii][k]),len(y[j:ii][k+1]))
            else:
             x2+=max(len(y[j:ii][k]),len(y[j:ii][k+1]))
        if ii-j>1:
         yy+=max(x1,x2)
        
        j=-1

    if len(y[i])>0 and j==-1:
        j=i
print(yy)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
x = raw_input().strip()
def solve(b, s):
    if len(b) == 1:
        return 0
    t = []
    p = b[0]
    r = 0
    for x in b[1:]:
        if p == 1:
            t.append(p)
            p = x
        elif x != 1:
            t.append(p - 1)
            t.append(1)
            r += 1
            p = x - 1
        else:
            t.append(p)
            p = x
    t.append(p)
    m = 1001001001
    dp = [0, (-m, m)]
    for x in t:
        b = dp[1][0] + max(dp[1][1], x)
        if b < dp[0]:
            b = dp[0]
        c = dp[1][0]
        if c < dp[0]:
            c = dp[0]
        dp = [b, (c, x)]
    return r + max(dp[0], dp[1][0])
a = []
p = ans = s = 0
c = x[0] == '1'
for i in xrange(1, n):
    if x[i-1] == x[i] == '0':
        if p < i - 1:
            ans += solve(a, s)
        a = []
        c = s = 0
        p = i
    elif x[i-1] != x[i] == '0':
        a.append(c)
        s += c
        c = 0
    else:
        c += 1
if p < n - 1:
    if c:
        a.append(c)
    s += c
    ans += solve(a, s)
print ans

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

i = 0
count = 0

while i < N - 2:
    if S[i:i + 3] == '000':
        i += 3
    elif S[i:i + 3] == '001':
        i += 2
    elif S[i:i + 3] == '010':
        i += 1
    elif S[i:i + 3] == '011':
        i += 2
    elif S[i:i + 3] == '100':
        i += 3
    elif S[i:i + 3] == '101':
        S = S[:i] + '010' + S[i + 3:]
        count += 1
        i += 1
    elif S[i:i + 3] == '110':
        i += 1
    elif S[i:i + 3] == '111':
        i += 2

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())

ans = 0
tmp = 1
while ans != tmp :
    tmp = ans
    for now in range(1,n-1) :
        if s[now] == '0' and s[now-1] == s[now+1] == '1' :
            ans += 1
            s[now] = '1'
            s[now-1] = '0'
            s[now+1] = '0'

    for now in range(n-2,0,-1) :
        if s[now] == '0' and s[now-1] == s[now+1] == '1' :
            ans += 1
            s[now] = '1'
            s[now-1] = '0'
            s[now+1] = '0'

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()



next ={0:-1,1:-1,2:-1,3:-1,-1:-1}
next[int(s[:2],2)]=0
for i in range(2,N):
    #print(next)
    now = next
    next = {0:0,1:0,2:0,3:0,-1:-1}
    if s[i] =='1':
        next[0]=-1
        next[1] = max(now[0],now[2])
        next[2]=  max(now[2]+1,next[-1])
        next[3]=  max(now[1],now[3])

    else:
        next[0]= max(now[0],now[2])
        next[2]= max(now[1],now[3])
        next[1]=-1
        next[3]=-1
        if i !=N-1 and now[3]>=0:
            next[-1] +=now[3]+1

print(max(next[i] for i in range(3)))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())

ans = 0
for now in range(1,n-1) :
    if s[now-1] == s[now+1] == '1'  and s[now] == '0':
        ans += 1
        s[now] = '1'
        s[now-1] = '0'
        s[now+1] = '0'

for now in range(n-2,0,-1) :
    if s[now-1] == s[now+1] == '1'  and s[now] == '0':
        ans += 1
        s[now] = '1'
        s[now-1] = '0'
        s[now+1] = '0'

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

i = 0
ans = 0
while (i<=len(S)-1):
    if S[i:i+3] == "101":
        S = S.replace("101", "010", 1)
        i += 1
        ans += 1
    else:
        i += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
# def makelist(n, m):
#     return [[0 for i in range(m)] for j in range(n)]

N = int(input())
s = input()

dp = [False]*N

for i in range(1, N-1):
    if s[i-1:i+2] == "101":
        dp[i] = True


ans = 0
revFlag = False
for i in range(1, N-1):
    if dp[i] == True:
        ans += 1
        revFlag = True
    else:
        if s[i] == '0':
            revFlag = False
        elif s[i] == '1':
            if revFlag:
                if dp[i+1]:
                    ()
                else:
                    ans += 1
            else:
                ()

print(ans)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
s=input()
x=len(s.split("101"))-1
y=s.split("0")
j=-1
yy=0
for i in range(len(y)):
    if y[i]=="" and j!=-1:
        x1=0
        x2=0
        for k in range(i-j):
          if k<i-j-1:
            if k%2==0:
             x1+=max(len(y[j:i][k]),len(y[j:i][k+1]))
            else:
             x2+=max(len(y[j:i][k]),len(y[j:i][k+1]))
        if i-j>1:
         yy+=max(x1,x2)
        j=-1

    if len(y[i])>0 and j==-1:
        j=i
print(yy)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

ss = []
cnt = 0
for c in s:
    if c == '1':
        cnt += 1
    else:
        if cnt > 0:
            ss.append(cnt)
            cnt = 0
        ss.append(cnt)
if cnt > 0:
    ss.append(cnt)
def solve(seq):
    l = len(seq)
    if not seq:
        return 0
    while seq[-1] == 0:
        seq.pop()

    #dp = [0]*(l+1)
    dp = [[0]*3 for i in range(l+1)]
    #print(seq)
    for i in range(l):
        # 0 -> 0, 1 -> 0, 2 -> 0
        nxt = max(dp[i])
        dp[i+1][0] = max(dp[i+1][0], nxt)
        if i+1 < l:
            if seq[i] >= 2:
                # 0 -> 1
                dp[i+1][1] = max(dp[i+1][1], dp[i][0] + seq[i])
            if seq[i] >= 2 and seq[i+1] >= 2:
                # 1 -> 1
                dp[i+1][1] = max(dp[i+1][1], dp[i][1] + seq[i]-1)
                # 2 -> 1
                dp[i+1][1] = max(dp[i+1][1], dp[i][2] + 1)
                # 1 -> 2
                dp[i+1][2] = max(dp[i+1][2], dp[i][1] + max(seq[i], seq[i+1])-1)
                # 2 -> 2
                dp[i+1][2] = max(dp[i+1][2], dp[i][2] + seq[i+1]-1)
            if seq[i+1] >= 2:
                # 0 -> 2
                dp[i+1][2] = max(dp[i+1][2], dp[i][0] + max(seq[i], seq[i+1]-1))
        if i+2 <= l:
            dp[i+2][0] = max(dp[i+2][0], dp[i][0] + max(seq[i], seq[i+1]))
            if seq[i] >= 2:
                dp[i+2][0] = max(dp[i+2][0], dp[i][1] + max(seq[i]-1, seq[i+1]))
        #print(dp[i])
    #print(dp[l])
    #print("-")
    return max(max(e) for e in dp)
idx = 0
cur = []
ans = 0
while idx < len(ss):
    if idx+1 < len(ss) and ss[idx] == ss[idx+1] == 0:
        idx += 2
        ans += solve(cur)
        cur = []
    elif not cur and ss[idx] == 0:
        idx += 1
    else:
        if ss[idx]:
            cur.append(ss[idx])
        idx += 1
if cur:
    ans += solve(cur)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

ss = []
cnt = 0
for c in s:
    if c == '1':
        cnt += 1
    else:
        if cnt > 0:
            ss.append(cnt)
            cnt = 0
        ss.append(cnt)
if cnt > 0:
    ss.append(cnt)
def solve(seq):
    l = len(seq)
    if not seq:
        return 0
    while seq[-1] == 0:
        seq.pop()

    #dp = [0]*(l+1)
    dp = [[0]*3 for i in range(l+1)]
    for i in range(l):
        # 0 -> 0, 1 -> 0, 2 -> 0
        nxt = max(dp[i])
        dp[i+1][0] = max(dp[i+1][0], nxt)
        if i+1 < l:
            if seq[i] >= 2:
                # 0 -> 1
                dp[i+1][1] = max(dp[i+1][1], dp[i][0] + seq[i])
            if seq[i] >= 2 and seq[i+1] >= 2:
                # 1 -> 1
                dp[i+1][1] = max(dp[i+1][1], dp[i][1] + seq[i]-1)
                # 2 -> 1
                dp[i+1][1] = max(dp[i+1][1], dp[i][2] + 1)
                # 1 -> 2
                dp[i+1][2] = max(dp[i+1][2], dp[i][1] + max(seq[i], seq[i+1])-1)
                # 2 -> 2
                dp[i+1][2] = max(dp[i+1][2], dp[i][2] + seq[i+1]-1)
            if seq[i+1] >= 2:
                # 0 -> 2
                dp[i+1][2] = max(dp[i+1][2], dp[i][0] + max(seq[i], seq[i+1]-1))
        if i+2 <= l:
            dp[i+2][0] = max(dp[i+2][0], dp[i][0] + max(seq[i], seq[i+1]))
            dp[i+2][0] = max(dp[i+2][0], dp[i][1] + max(seq[i]-1, seq[i+1]))

    return max(max(e) for e in dp)
idx = 0
cur = []
ans = 0
while idx < len(ss):
    if idx+1 < len(ss) and ss[idx] == ss[idx+1] == 0:
        idx += 2
        ans += solve(cur)
        cur = []
    elif not cur and ss[idx] == 0:
        idx += 1
    else:
        if ss[idx]:
            cur.append(ss[idx])
        idx += 1
if cur:
    ans += solve(cur)
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
s=input()
temp=[]
arr=[]
i=0
while True:
 if s[i]=="1":
  if i==len(s)-1:
   temp.append(1)
   if len(temp)>1:
    arr.append(temp)
   break
  for j in range(i+1,len(s)):
   if s[j]!="1":
    break
  temp.append(j-i)
  i=j
  if j==len(s)-1:
   if s[j]=="1":
    temp[-1]+=1
   if len(temp)>1:
    arr.append(temp)
   break
 elif i==len(s)-1:#0end
  if len(temp)>0:
   arr.append(temp)
  break
 elif s[i:i+2]=="01":
  i+=1
  if i==len(s)-1:
   temp.append(1)
   if len(temp)>1:
    arr.append(temp)
   break
  for j in range(i+1,len(s)):
   if s[j]!="1":
    break
  temp.append(j-i)
  i=j
  if j==len(s)-1:
   if s[j]=="1":
    temp[-1]+=1
   if len(temp)>1:
    arr.append(temp)
   break
 elif s[i:i+2]=="00":
  if len(temp)>0:
   if len(temp)>1:
    arr.append(temp)
   temp=[]
  if i==len(s)-2:
   break
  i+=2
res=0
for l in arr:
 dp=[0 for i in range(len(l))]
 dp[1]=max(l[0],l[1])
 for i in range(2,len(l)):
  dp[i]=max(dp[i-1],dp[i-2]+max(l[i-1],l[i]))
 res+=dp[-1]
print(res)

Submission status: Wrong Answer

Solution code:
s=input()
s=input()
temp=[]
arr=[]
i=0
while True:
 if s[i]=="1":
  if i==len(s)-1:
   temp.append(1)
   if len(temp)>1:
    arr.append(temp)
   break
  for j in range(i+1,len(s)):
   if s[j]!="1":
    break
  temp.append(j-i)
  i=j
  if j==len(s)-1:
   if s[j]=="1":
    temp[-1]+=1
   if len(temp)>1:
    arr.append(temp)
   break
 elif i==len(s)-1:#0end
  if len(temp)>0:
   arr.append(temp)
  break
 elif s[i:i+2]=="01":
  i+=1
  if i==len(s)-1:
   temp.append(1)
   if len(temp)>1:
    arr.append(temp)
   break
  for j in range(i+1,len(s)):
   if s[j]!="1":
    break
  temp.append(j-i)
  i=j
  if j==len(s)-1:
   if s[j]=="1":
    temp[-1]+=1
   if len(temp)>1:
    arr.append(temp)
   break
 elif s[i:i+2]=="00":
  if len(temp)>0:
   if len(temp)>1:
    arr.append(temp)
   temp=[]
  if i==len(s)-2:
   break
  i+=2
print(arr)
res=0
for l in arr:
 dp=[0 for i in range(len(l))]
 dp[1]=max(l[0],l[1])
 for i in range(2,len(l)):
  dp[i]=max(dp[i-1],dp[i-2]+max(l[i-1],l[i]))
 res+=dp[-1]
print(res)

Submission status: Wrong Answer

Solution code:
import copy
N=int(input())
s=[i=="1" for i in input()]
ans=0
#数値セット
pack=[]


#メインの計算 tmp...1がいくつ続いているか
def calc(TMP):
	tmp=copy.deepcopy(TMP)
	if(len(tmp)<2):
		return 0
	if(len(tmp)==2):
		return max(tmp)
	#print(tmp)
	res=0
	#index=1~ -2の範囲で1が無ければ優勝
	good = -1
	for i in range(1,len(tmp)-1):
		if tmp[i]==1:
			good=i
			break
	if good==-1:
		for i in range(1,len(tmp)-1):
			tmp[i]-=2
		tmp[0]-=1
		tmp[-1]-=1
		return sum(tmp)-min(tmp)+len(tmp)-1
	#そうでなければ面倒くさい
	else:
		a = calc(tmp[0:good])  +calc(tmp[good:])
		b = calc(tmp[0:good+1])+calc(tmp[good+1:])
		c = calc(tmp[0:good])+calc(tmp[good+1:])
		return max(a,b,c)

befIndex=0	
nowIndex=0
zero=True
while nowIndex<len(s):
	#sの現在地が0 
	if not s[nowIndex]:
		#1つ前も0
		if zero:
			#出荷よー！
			tt=calc(pack)
			#print(tt)
			ans+=tt
			#1が出るまで進める
			while nowIndex<len(s) and not s[nowIndex]:
				nowIndex+=1
			befIndex=nowIndex
			pack=[1]
			zero=False
		else:
			zero=True
	#nowIndexが1の場合
	else:
		#1つ前は0
		if zero:
			pack.append(1)
		#１つ前も1
		else:
			pack[-1]+=1
		zero=False
	nowIndex+=1
ans+=calc(pack)
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
s=input()
temp=[]
arr=[]
i=0
while True:
 if s[i]=="1":
  if i==len(s)-1:
   temp.append(1)
   if len(temp)>1:
    arr.append(temp)
   break
  for j in range(i+1,len(s)):
   if s[j]!="1":
    break
  temp.append(j-i)
  i=j
  if j==len(s)-1:
   if s[j]=="1":
    temp[-1]+=1
   if len(temp)>1:
    arr.append(temp)
   break
 elif i==len(s)-1:#0end
  if len(temp)>0:
   arr.append(temp)
  break
 elif s[i:i+2]=="01":
  i+=1
  if i==len(s)-1:
   temp.append(1)
   if len(temp)>1:
    arr.append(temp)
   break
  for j in range(i+1,len(s)):
   if s[j]!="1":
    break
  temp.append(j-i)
  i=j
  if j==len(s)-1:
   if len(temp)>1:
    arr.append(temp)
   break
 elif s[i:i+2]=="00":
  if len(temp)>0:
   if len(temp)>1:
    arr.append(temp)
   temp=[]
  if i==len(s)-2:
   break
  i+=2
res=0
for l in arr:
 dp=[0 for i in range(len(l))]
 dp[1]=max(l[0],l[1])
 for i in range(2,len(l)):
  dp[i]=max(dp[i-1],dp[i-2]+max(l[i-1],l[i]))
 res+=dp[-1]
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()



next ={0:-1,1:-1,2:-1,3:-1}
next[int(s[:2],2)]=0
for i in range(2,N):
    #print(next)
    now = next
    next = {0:0,1:0,2:0,3:0}
    if s[i] =='1':
        next[0]=-1
        next[1] = max(now[0],now[2])
        next[2]=  max(now[2]+1,0)
        next[3]=  max(now[1],now[3])
    else:
        next[0]= max(now[0],now[2])
        next[2]= max(now[1],now[3])
        next[1]=-1
        next[3]=-1

print(max(next[i] for i in range(3)))

Submission status: Wrong Answer

Solution code:
N=int(input())
s=[i=="1" for i in input()]
ans=0
#数値セット
pack=[]


#メインの計算 tmp...1がいくつ続いているか
def calc(tmp):
	if(len(tmp)<2):
		return 0
	#print(tmp)
	res=0
	#index=1~ -2の範囲で1が無ければ優勝
	good = -1
	for i in range(1,len(tmp)-1):
		if tmp[i]==1:
			good=i
			break
	if good==-1:
		for i in range(1,len(tmp)-1):
			tmp[i]-=2
		tmp[0]-=1
		tmp[-1]-=1
		return sum(tmp)-min(tmp)+len(tmp)-1
	#そうでなければ面倒くさい
	else:
		a = calc(tmp[0:i])  +calc(tmp[i:])
		b = calc(tmp[0:i+1])+calc(tmp[i+1:])
		c = calc(tmp[0:i])+calc(tmp[i+1:])
		return max(a,b,c)

befIndex=0	
nowIndex=0
zero=True
while nowIndex<len(s):
	#sの現在地が0 
	if not s[nowIndex]:
		#1つ前も0
		if zero:
			#出荷よー！
			tt=calc(pack)
			#print(tt)
			ans+=tt
			#1が出るまで進める
			while nowIndex<len(s) and not s[nowIndex]:
				nowIndex+=1
			befIndex=nowIndex
			pack=[1]
			zero=False
		else:
			zero=True
	#nowIndexが1の場合
	else:
		#1つ前は0
		if zero:
			pack.append(1)
		#１つ前も1
		else:
			pack[-1]+=1
		zero=False
	nowIndex+=1
ans+=calc(pack)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
s=[i=="1" for i in input()]
ans=0
#数値セット
pack=[]


#メインの計算 tmp...1がいくつ続いているか
def calc(tmp):
	if(len(tmp)<2):
		return 0
	#print(tmp)
	res=0
	#index=1~ -2の範囲で1が無ければ優勝
	good = -1
	for i in range(1,len(tmp)-1):
		if tmp[i]==1:
			good=i
			break
	if good==-1:
		for i in range(1,len(tmp)-1):
			tmp[i]-=2
		tmp[0]-=1
		tmp[-1]-=1
		return sum(tmp)-min(tmp)+len(tmp)-1
	#そうでなければ面倒くさい
	else:
		return max(calc(tmp[0:i])+calc(tmp[i:]),calc(tmp[0:i+1])+calc(tmp[i+1:]))

	
befIndex=0	
nowIndex=0
zero=True
while nowIndex<len(s):
	#sの現在地が0 
	if not s[nowIndex]:
		#1つ前も0
		if zero:
			#出荷よー！
			tt=calc(pack)
			#print(tt)
			ans+=tt
			#1が出るまで進める
			while nowIndex<len(s) and not s[nowIndex]:
				nowIndex+=1
			befIndex=nowIndex
			pack=[1]
			zero=False
		else:
			zero=True
	#nowIndexが1の場合
	else:
		#1つ前は0
		if zero:
			pack.append(1)
		#１つ前も1
		else:
			pack[-1]+=1
		zero=False
	nowIndex+=1
ans+=calc(pack)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()

i = 0
count = 0

while i < N - 2:
    if S[i:i + 3] == '101':
        S = S[:i] + '010' + S[i + 3:]
        count += 1
        if i > 0:
            i -= 1
        else:
            i += 1
    else:
        i += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
check = [0] * (N-2)

for i in range(N-2):
    j = 2
    right = 0
    k = 0
    left = 0
    if s[i:i+3] == "101":
        while i + j < N :
            if s[i+j] == "1":
                right += 1
            else:
                break
            j += 1

        while i - k >= 0:
            if s[i-k] == "1":
                left += 1
            else:
                break
            k += 1
        
        check[i] = max(left, right)
cnt = 0
for i in range(N-5):
    if (check[i] > 0) & (check[i+3] > 0):
        cnt += 1
         

for i in range(N-4):
    if check[i] >= 1:
        check[i+1] = max(check[i+1]-1, 0)
        check[i+2] = max(check[i+2]-1, 0)

print(sum(check)-cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = list(input())

count = 0
idx = 0
while True:
    if N - 2 <= idx:
        break
    if s[idx:idx + 3] == ['1', '0', '1']:

        countL = 1
        for i in range(0, idx)[::-1]:
            if s[i] == '0':
                break
            countL += 1

        countR = 1
        for i in range(idx + 3, N):
            if s[i] == '0':
                break
            countR += 1

        if countR <= countL:
            count += countL
            s[idx + 2] = '0'
            idx += 3
        else:
            count += countR
            idx += countR + 2
    idx += 1

print(count)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	nums = [int(x) for x in list(input())]

	if n <= 2:
		print(0)
	else:
		cnt = 0
		while True:
			prv_cnt = cnt
			i = 0
			while True:
				if nums[i:(i+3)] == [1, 0, 1]:
					nums[i:(i+3)] = [0, 1, 0]
					cnt += 1
					i += 1
				else:
					i += 1
				if i >= n - 2:
					break
			if cnt == prv_cnt:
				break

		print(cnt)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

ss = []
cnt = 0
for c in s:
    if c == '1':
        cnt += 1
    else:
        if cnt > 0:
            ss.append(cnt)
            cnt = 0
        ss.append(cnt)
if cnt > 0:
    ss.append(cnt)
def solve(seq):
    l = len(seq)
    if not seq:
        return 0
    while seq[-1] == 0:
        seq.pop()

    #dp = [0]*(l+1)
    dp = [[0]*3 for i in range(l+1)]
    for i in range(l):
        if i+1 <= l:
            nxt = max(dp[i])
            for j in range(3):
                dp[i+1][j] = max(dp[i+1][j], nxt)
            if i+1 < l:
                dp[i+1][1] = max(dp[i+1][1], dp[i][0] + seq[i])
                if seq[i] >= 2:
                    dp[i+1][1] = max(dp[i+1][1], dp[i][1] + seq[i]-1)
                    if seq[i+1] >= 2:
                        dp[i+1][2] = max(dp[i+1][2], max(seq[i], seq[i+1])-1)
                if seq[i+1] >= 2:
                    dp[i+1][1] = max(dp[i+1][1], dp[i][2] + 1)
                    dp[i+1][2] = max(dp[i+1][2], seq[i+1]-1)
        if i+2 <= l:
            dp[i+2][0] = max(dp[i+2][0], dp[i][0] + max(seq[i], seq[i+1]))
    return max(max(e) for e in dp)
idx = 0
cur = []
ans = 0
while idx < len(ss):
    if idx+1 < len(ss) and ss[idx] == ss[idx+1] == 0:
        idx += 2
        ans += solve(cur)
        cur = []
    elif not cur and ss[idx] == 0:
        idx += 1
    else:
        if ss[idx]:
            cur.append(ss[idx])
        idx += 1
if cur:
    ans += solve(cur)
print(ans)

Submission status: Wrong Answer

Solution code:
import re

rep_zeros = re.compile('0{2,}')
rep_ioioi = re.compile('((?:10)+1)')

n = input()
s = input().strip('0')
ans = 0

for ps in re.split(rep_zeros, s):
    fs = re.split(rep_ioioi, ps)
    if len(fs) == 1:
        continue
    ls = list(map(len, fs))
    for l in ls[1::2]:
        ans += (l + 1) // 4
    mls = ls[0::2]
    ans += sum(mls) - min(mls)
    if len(mls) >= 4 and mls[0] == mls[-1] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import re

rep_zeros = re.compile('0{2,}')
rep_ioioi = re.compile('((?:10)+1)')

n = input()
s = input().strip('0')
ans = 0

for ps in re.split(rep_zeros, s):
    fs = re.split(rep_ioioi, ps)
    if len(fs) == 1:
        continue
    ls = list(map(len, fs))
    for l in ls[1::2]:
        ans += (l + 1) // 4
    mls = ls[0::2]
    ans += sum(mls) - min(mls)
    print(mls)
    if len(mls) >= 4 and mls[0] == mls[-1] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = list(input())

count = 0
idx = 0
while True:
    if N - 2 <= idx:
        break
    if s[idx:idx + 3] == ['1', '0', '1']:

        countL = 1
        for i in range(0, idx)[::-1]:
            if s[i] == '0':
                break
            countL += 1

        countR = 1
        for i in range(idx + 3, N):
            if s[i] == '0':
                break
            countR += 1

        if countR <= countL:
            count += countL
            s[idx + 2] = '0'
        else:
            count += countR
            idx += countR
            s[idx + 1] = '0'
    idx += 1

print(count)

Submission status: Wrong Answer

Solution code:
import re

rep_zeros = re.compile('0{2,}')
rep_ioioi = re.compile('((?:10)+1)')

n = input()
s = input().strip('0')
ans = 0

for ps in re.split(rep_zeros, s):
    fs = re.split(rep_ioioi, ps)
    if len(fs) == 1:
        continue
    ls = list(map(len, fs))
    for l in ls[1::2]:
        ans += (l + 1) // 4
    mls = ls[0::2]
    ans += sum(mls) - min(mls)
    if len(mls) >= 5 and mls[0] == mls[-1] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = list(input())

count = 0
idx = 0
while True:
    if N - 2 <= idx:
        break
    if s[idx:idx + 3] == ['1', '0', '1']:

        countL = 1
        for i in range(0, idx)[::-1]:
            if s[i] == '0':
                break
            countL += 1

        countR = 1
        for i in range(idx + 3, N):
            if s[i] == '0':
                break
            countR += 1

        print(countL, countR)
        if countR <= countL:
            count += countL
            s[idx + 2] = '0'
        else:
            count += countR
            idx += countR
            s[idx + 1] = '0'
    idx += 1

print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(N, S, i):
    cnt = 0
    if S[i] == "0":
        while i < N and S[i] == "0":
            i += 1
        return 0, i
    cnt1s = []
    while True:
        cnt1 = 0
        while i < N and S[i] == "1":
            i += 1
            cnt1 += 1
        if cnt1 == 0:
            break
        cnt1s.append(cnt1)
        i += 1
    # print(cnt1s)
    if len(cnt1s) <= 1:
        cnt = 0
    elif len(cnt1s) <= 3:
        cnt = max(cnt1s)
    elif len(cnt1s) == 4:
        cnt = max(cnt1s[0:2]) + max(cnt1s[2:4])
    elif len(cnt1s) % 2 == 0:
        c1 = 0
        for j in range(0, len(cnt1s), 2):
            c1 += max(cnt1s[j:j+2])
        c2 = max(cnt1s[0:3]) + max(cnt1s[-3:])
        for j in range(3, len(cnt1s)-3, 2):
            c2 += max(cnt1s[j:j+2])
        cnt = max(c1, c2)
    else:
        c1 = max(cnt1s[0:3])
        c2 = max(cnt1s[-3:])
        for j in range(3, len(cnt1s), 2):
            c1 += max(cnt1s[j:j+2])
        for j in range(0, len(cnt1s)-3, 2):
            c2 += max(cnt1s[j:j+2])
        cnt = max(c1, c2)

    return cnt, i


def main():
    N = int(input())
    S = input().strip()
    ans = 0
    i = 0
    while i < N:
        a, i = solve(N, S, i)
        ans += a
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:

N = int(input())
s = input()
check = [0] * (N-2)

for i in range(N-2):
    j = 2
    right = 0
    k = 0
    left = 0
    if s[i:i+3] == "101":
        while i + j < N :
            if s[i+j] == "1":
                right += 1
            else:
                break
            j += 1

        while i - k >= 0:
            if s[i-k] == "1":
                left += 1
            else:
                break
            k += 1
        
        check[i] = max(left, right)


for i in range(N-5):
    if check[i] >= 1:
        check[i+1] = max(check[i+1]-1, 0)
        check[i+2] = max(check[i+2]-1, 0)
        check[i+3] = max(check[i+2]-1,0)


print(sum(check))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [c for c in input()]

i = 0
count = 0

while i < N - 2:
    if S[i] == '1' and S[i + 1] == '0' and S[i + 2] == '1':
        S[i] = '0'
        S[i + 1] = '1'
        S[i + 2] = '0'
        count += 1
        if i > 0:
            i -= 1
    i += 1

print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from copy import deepcopy
import re
result1 = 0
result2 = 0

N = int(input())
s = input()

text1 = s.replace("10", "a").replace("a0", "100")
text2 = s[::-1].replace("10", "a").replace("a0", "100")

typea = re.findall("a1+", text1)

for a in typea:
    result1 += len(a)-1

result1 += re.sub("a1+", "d", text1).replace("aa", "b").count("b")

typea = re.findall("a1+", text2)

for a in typea:
    result2 += len(a)-1

result2 += re.sub("a1+", "d", text2).replace("aa", "b").count("b")
print(max(result1, result2))

Submission status: Wrong Answer

Solution code:
import re
n=input()
a=input()

r=re.findall('101+',a)
def ll(i):
    return len(i)-2

print(sum([ll(i) for i in r]))

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
check = [0] * (N-2)

for i in range(N-2):
    j = 2
    right = 0
    k = 0
    left = 0
    if s[i:i+3] == "101":
        while i + j < N :
            if s[i+j] == "1":
                right += 1
            else:
                break
            j += 1

        while i - k >= 0:
            if s[i-k] == "1":
                left += 1
            else:
                break
            k += 1
        
        check[i] = max(left, right)

for i in range(N-4):
    if check[i] >= 1:
        check[i+1] = max(check[i+1]-1, 0)
        check[i+2] = max(check[i+2]-1, 0)

print(sum(check))