Problem:


Score : 400 points

Problem Statement

N people are arranged in a row from left to right.

You are given a string S of length N consisting of 0 and 1, and a positive integer K.

The i-th person from the left is standing on feet if the i-th character of S is 0, and standing on hands if that character is 1.

You will give the following direction at most K times (possibly zero):

Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.

Find the maximum possible number of consecutive people standing on hands after at most K directions.

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of consecutive people standing on hands after at most K directions.

Sample Input 1

5 1
00010

Sample Output 1

4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:

Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=list(input())

ans=[0]
le=[]
ch=0

for i in range(n):
  if s[i]=='0':
    ch+=1
    if i==n-1:
      ans.append(i+1)
      le.append(ch)
  else:
    if ch>0:
      ans.append(i+1)
      le.append(ch)
      ch=0

s=-10000000


if len(ans)-1<=k:
  print(n)
  

else:
  for j in range(len(ans)):
    if j+k<=len(ans)-1:
      
      if j+k==len(ans)-1:
        t=ans[j+k]-ans[j]+(n-1)-ans[j+k]+1
      else:
        t=-ans[j]+ans[j+k+1]-le[j+k]
      s=max(s,t)
  print(s)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=list(input())

ans=[0]
ch=0

for i in range(n):
  if s[i]=='0':
    ch+=1
    if i==n-1:
      ans.append(i+1)
  else:
    if ch>0:
      ans.append(i+1)
      ch=0

s=-10000000

if len(ans)-1<=k:
  print(n)
  

else:
  for j in range(len(ans)):
    if j+k<=len(ans)-1:
      t=ans[j+k]-ans[j]
      if j+k==len(ans)-1:
        t+=(n-1)-ans[j+k]+1
      s=max(s,t)
  print(s)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=list(input())

ans=[0]
ch=0

for i in range(n):
  if s[i]=='0':
    ch+=1
    if i==n-1:
      ans.append(i+1)
  else:
    if ch>0:
      ans.append(i+1)
      ch=0

s=-10000000
print(ans)
if len(ans)-1<=k:
  print(n)
  

else:
  for j in range(len(ans)):
    if j+k<=len(ans)-1:
      t=ans[j+k]-ans[j]
      if j+k==len(ans)-1:
        t+=(n-1)-ans[j+k]+1
      s=max(s,t)
  print(s)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=list(input())

ans=[0]
ch=0

for i in range(n):
  if s[i]=='0':
    ch+=1
    if i==n-1:
      ans.append(i)
  else:
    if ch>0:
      ans.append(i)
      ch=0

s=-10000000
if len(ans)-1<=k:
  print(n)
  

else:
  for j in range(len(ans)):
    if j+k<=len(ans)-1:
      t=ans[j+k]-ans[j]
      if j+k==len(ans)-1:
        t+=(n-1)-ans[j+k]+1
      s=max(s,t)
  print(s)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=list(input())

ans=[0]
ch=0

for i in range(n):
  if s[i]=='0':
    ch+=1
    if i==n-1:
      ans.append(i)
  else:
    if ch>0:
      ans.append(i)
      ch=0

s=-10000000
if len(ans)-1<=k:
  print(n)
  

else:
  for j in range(len(ans)):
    if j+k+1<=len(ans)-1:
      s=max(s,ans[j+k+1]-ans[j])
  print(s)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[int(i) for i in input()]
i,k=0,K
while k>0 and i<N:
  while i<N and S[i]==1:
    i+=1
  while i<N and S[i]==0:
    i+=1
  k-=1
while i<N and S[i]==1:
  i+=1
j,k=0,K
while k>0 and j<N:
  while j<N and S[N-1-j]==1:
    j+=1
  while j<N and S[N-1-j]==0:
    j+=1
  k-=1
while j<N and S[N-1-j]==1:
  j+=1
print(max(i,j))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[int(i) for i in input()]
ans,i,k=0,0,K
while k>0 and i<N:
  while i<N and S[i]==1:
    i+=1
  while i<N and S[i]==0:
    i+=1
  k-=1
while i<N and S[i]==1:
  i+=1
j,k=0,K
while k>0 and j<N:
  while j<N and S[N-1-j]==1:
    j+=1
  while j<N and S[N-1-j]==0:
    j+=1
  k-=1
while j<N and S[N-1-j]==1:
  j+=1
print(max(i,j))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[int(i) for i in input()]
ans,i,k=0,0,K
while k>0 and i<N:
  while i<N and S[i]==1:
    i+=1
  while i<N and S[i]==0:
    i+=1
  k-=1
while i<N-1 and S[i+1]==1:
  i+=1
j,k=0,K
while k>0 and j<N:
  while j<N and S[N-1-j]==1:
    j+=1
  while j<N and S[N-1-j]==0:
    j+=1
  k-=1
while j<N-1 and S[N-2-j]==1:
  j+=1
print(max(i,j)+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
S=len(s)

a=[]
x=s[0]

for i in range(S):
    if x[-1]==s[i]:
        x+=s[i]
        if i==0:
            x=x[1:]

    else:
        a.append(x)
        x=s[i]
else:
    a.append(x)

A=len(a)

cnt=0
cnt_k=0
cnt_max=0
cnt_ty=0
flag=0

for i in range(2**A):
    for j in range(A):
        if i>>j&1:
            if a[j][0]=="0":
                cnt+=len(a[j])
                cnt_k+=1
            else:
                cnt+=len(a[j])
        else:
            if a[j][0]=="1":
                cnt+=len(a[j])
            else:
                if cnt_ty<cnt:
                    cnt_ty=cnt
                    cnt=0
                    flag+=1

    else:
        if cnt_ty<cnt:
            cnt_ty=cnt

        if cnt_k<=k:
            if flag>=1:
                if cnt_ty>cnt_max:
                    cnt_max=cnt_ty
            elif cnt>cnt_max:
                cnt_max=cnt
        cnt_k=0
        cnt=0
        cnt_ty=0

print(cnt_max)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
S = list(input())

S_zero={}
S_zero_group = 0
s_befor = ''
for s_idx,s in enumerate(S):
    if s != s_befor:
        if s == '0':
            S_zero_group += 1
            S_zero[S_zero_group] = [s_idx-1]
        elif s == '1':
            if S_zero_group in S_zero.keys():
                S_zero[S_zero_group].append(s_idx)
            
    s_befor = s
    
if S[-1] == '0':
    S_zero[S_zero_group].append(N)
    
if S_zero_group <= K:
    ans_ = N
else:   
    ans_=0
    for g_s in range(1,S_zero_group-K+2):
        g_e = g_s + K - 1
#         print('====',g_s,g_e)
        s = 0
        e = N-1

        if g_s != 1:
            s = S_zero[g_s-1][1]
        if g_e != S_zero_group:
            e = S_zero[g_e+1][0]

        ans= e-s+1
        print(e,s,ans)
        if ans > ans_:
            ans_=ans

print(ans_)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
S=len(s)

a=[]
x=s[0]

for i in range(S):
    if x[-1]==s[i]:
        x+=s[i]
        if i==0:
            x=x[1:]

    else:
        a.append(x)
        x=s[i]
else:
    a.append(x)

A=len(a)

cnt=0
cnt_k=0
cnt_max=0
cnt_ty=0
flag=0

for i in range(2**A):
    for j in range(A):
        if i>>j&1:
            if a[j][0]=="0":
                cnt+=len(a[j])
                cnt_k+=1
            else:
                cnt+=len(a[j])
        else:
            if a[j][0]=="1":
                cnt+=len(a[j])
            else:
                if cnt_ty<cnt:
                    cnt_ty=cnt
                    cnt=0
                    flag+=1

    else:
        if cnt_k<=k:
            if flag>=1:
                if cnt_ty>cnt_max:
                    cnt_max=cnt_ty
            elif cnt>cnt_max:
                cnt_max=cnt
        cnt_k=0
        cnt=0
        cnt_ty=0

print(cnt_max)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby, accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())
    S = readline().strip()

    vec = [len(list(g)) for _, g in groupby(S)]
    csum = [0]
    csum.extend(accumulate(vec))

    ans = 0
    for i in range(len(vec)):
        n = 2 * K if S[i] == '0' else 2 * K + 1
        if ans < csum[min(i + n, len(csum) - 1)] - csum[i]:
            ans = csum[min(i + n, len(csum) - 1)] - csum[i]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = list(map(int, input()))
cnt = [0] * n
e_cnt = 0
ans = 0

for i in range(n):
    if s[i] == 0 and (i == 0 or s[i - 1] == 1):
        e_cnt += 1

if e_cnt <= k:
    print(n)
    exit()

def cnt_set(start, end, plus):
    c = 0
    pre = start
    for i in range(start, end, plus):
        if s[i] == 1:
            c += 1
        else:
            cnt[i] = c if c != 0 else cnt[pre]
            c = 0
        pre = i


def solve():
    mx = 0 
    c = 0
    for i in range(n):
        if cnt[i] != 0:
            if c == 0:
                c += cnt[i]
            c += 1
        else:
            if mx < c:
                mx = c
                c = 0
    return mx

for i in range(k):
    cnt_set(0, n, 1)
    cnt_set(n - 1, -1, -1)
    if 0 not in s:
        break

    ans += solve()
    cnt = [0] * n
print(ans)

Submission status: Wrong Answer

Solution code:

import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    s=input()

if n==1:
    print(1)
    sys.exit()

ss=[]
if s[0]=="1" and s[1]=="1":
    zcnt=1
elif s[0]=="1" and s[1]=="0":
    ss.append(1)
    zcnt=0
elif s[0]=="0" and s[1]=="0":
    ss.append(0)
    zcnt=1
elif s[0]=="0" and s[1]=="1":
    ss.append(0)
    ss.append(1)
    zcnt=1

for i in range(1,n-1):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        zcnt=1
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        zcnt=1
        
for i in range(n-1,n):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
        ss.append(zcnt)
        ss.append(0)
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        ss.append(1)
        ss.append(0)
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
        ss.append(zcnt)
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        ss.append(1)

#print(ss)

if len(ss)<=2*k+1:
    print(n)
    sys.exit()

smax=0
for i in range(2*k+1):
    smax+=ss[i]
#print(smax)    
ssum=smax    
kk=2*k
for i in range(2,len(ss)-kk,2):
    ssum=ssum-ss[i-2]-ss[i-1]+ss[i+kk-1]+ss[i+kk]
    smax=max(smax,ssum)

print(smax)

Submission status: Wrong Answer

Solution code:

import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    s=input()
elif icase==1:
    n,k=14,2
    s="11101010110011"
elif icase==2:
    n,k=15,2
    s="111010101100110"
elif icase==3:
    n,k=16,2
    s="1110101011001101"
    s="1110101011001100"

if n==1:
    print(1)
    sys.exit()

ss=[]
if s[0]=="1" and s[1]=="1":
    zcnt=1
elif s[0]=="1" and s[1]=="0":
    ss.append(1)
    zcnt=0
elif s[0]=="0" and s[1]=="0":
    ss.append(0)
    zcnt=1
elif s[0]=="0" and s[1]=="1":
    ss.append(0)
    ss.append(1)
    zcnt=1

for i in range(1,n-1):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        zcnt=1
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        zcnt=1
        
for i in range(n-1,n):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
        ss.append(zcnt)
        ss.append(0)
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        ss.append(1)
        ss.append(0)
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
        ss.append(zcnt)
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        ss.append(1)

#print(ss)

if len(ss)<=2*k+1:
    print(n)
    sys.exit()

smax=0
for i in range(2*k+1):
    smax+=ss[i]
#print(smax)    
ssum=smax    
kk=2*k
for i in range(2,len(ss)-kk,2):
    ssum=ssum-ss[i-2]-ss[i-1]+ss[i-2+kk]+ss[i-1+kk+1]
    smax=max(smax,ssum)
#    print(i,ssum)

print(smax)

Submission status: Wrong Answer

Solution code:

import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    s=input()
elif icase==1:
    n,k=14,2
    s="11101010110011"
elif icase==2:
    n,k=15,2
    s="111010101100110"
elif icase==3:
    n,k=16,2
    s="1110101011001101"
    s="1110101011001100"

if n==1:
    print(1)
    sys.exit()

ss=[]
if s[0]=="1" and s[1]=="1":
    zcnt=1
elif s[0]=="1" and s[1]=="0":
    ss.append(1)
    zcnt=0
elif s[0]=="0" and s[1]=="0":
    ss.append(0)
    zcnt=1
elif s[0]=="0" and s[1]=="1":
    ss.append(0)
    ss.append(1)
    zcnt=1

for i in range(1,n-1):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        zcnt=1
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        zcnt=1
        
for i in range(n-1,n):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
        ss.append(zcnt)
        ss.append(0)
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        ss.append(1)
        ss.append(0)
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
        ss.append(zcnt)
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        ss.append(1)

#print(ss)

if len(ss)<=2*k+1:
    print(sum(ss))
    sys.exit()

smax=0
for i in range(2*k+1):
    smax+=ss[i]
#print(smax)    
ssum=smax    
kk=2*k
for i in range(2,len(ss)-kk,2):
    ssum=ssum-ss[i-2]-ss[i-1]+ss[i-2+kk]+ss[i-1+kk+1]
    smax=max(smax,ssum)
#    print(i,ssum)

print(smax)

Submission status: Wrong Answer

Solution code:

import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    s=input()
elif icase==1:
    n,k=14,2
    s="11101010110011"
elif icase==2:
    n,k=15,2
    s="111010101100110"
elif icase==3:
    n,k=16,2
    s="1110101011001101"
    s="1110101011001100"

if n==1:
    print(1)
    sys.exit()

ss=[]
if s[0]=="1" and s[1]=="1":
    zcnt=1
elif s[0]=="1" and s[1]=="0":
    ss.append(1)
    zcnt=0
elif s[0]=="0" and s[1]=="0":
    ss.append(0)
    zcnt=1
elif s[0]=="0" and s[1]=="1":
    ss.append(0)
    ss.append(1)
    zcnt=1

for i in range(1,n-1):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        zcnt=1
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        zcnt=1
        
for i in range(n-1,n):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
        ss.append(zcnt)
        ss.append(0)
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        ss.append(1)
        ss.append(0)
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
        ss.append(zcnt)
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        ss.append(1)

print(ss)

if len(ss)<=2*k+1:
    print(sum(ss))
    sys.exit()

smax=0
for i in range(2*k+1):
    smax+=ss[i]
print(smax)    
ssum=smax    
kk=2*k
for i in range(2,len(ss)-kk,2):
    ssum=ssum-ss[i-2]-ss[i-1]+ss[i-2+kk]+ss[i-1+kk+1]
    smax=max(smax,ssum)
    print(i,ssum)

print(smax)

Submission status: Wrong Answer

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
n,k=map(int,input().split())
s=input()
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
a+=[0]*3
k*=2
for i in range(m-k):
  if s[a[i]]=='0':cnt=a[i+k]-a[i]
  else:cnt=a[i+k+1]-a[i]
  ans=max(ans,cnt)
print([ans,n][m<=k+1])

Submission status: Wrong Answer

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
n,k=map(int,input().split())
s=input()
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
l=0
r=s[0]=='1'
k*=2
ans=0
while r<m:
  ans=max(a[r]-a[l],ans)
  if r-l<k+1:r+=2
  else:
    r+=2
    l+=2
print([ans,n][m<=k])

Submission status: Wrong Answer

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
n,k=map(int,input().split())
s=input()
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
a+=[0]*3
k*=2
for i in range(s[0]=='0',m-k+1,2):
  ans=max(ans,a[i+k+1]-a[i])
print([ans,n][m<=k])

Submission status: Wrong Answer

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
n,k=map(int,input().split())
s=input()
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
a+=[0]*3
k*=2
for i in range(m-k+1):
  if s[a[i]]=='0':cnt=a[i+k]-a[i]
  else:cnt=a[i+k+1]-a[i]
  ans=max(ans,cnt)
print([ans,n][m<=k])

Submission status: Wrong Answer

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
n,k=map(int,input().split())
s=input()
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
a+=[0]*3
k*=2
for i in range(m-k):
  if s[a[i]]=='0':cnt=a[i+k]-a[i]
  else:cnt=a[i+k+1]-a[i]
  ans=max(ans,cnt)
print([ans,n][m<=k])

Submission status: Wrong Answer

Solution code:

# spent 4 hrs for this question why i am noob:(
def main():
	n , k = map(int , input().split())
	hd = input()
	grp=[]
	if hd[0]=='1':
		grp = [[0,0]]
	else:
		grp=[[0,0]]
	cnt =1
	for i in range(1, len(hd)):
		if hd[i]==hd[i-1]:
			cnt = cnt+1
		else:
			grp.append([cnt,i])
			cnt = 1
	grp .append([cnt , len(hd)-1])
	pre = [0 for i in range(0 , len(grp)+9)]
	pre[0]=grp[0][0]
	for i in range(1, len(grp)):
		pre[i]=pre[i-1]+grp[i][0]
	ans = 0
	for i in range(0 , len(grp)):
		if hd[grp[i][1]]=='0':
			rgt = min(i+2*k, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		else:
			rgt = min(i+2*k+1, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
			print(ans,i, pre[rgt], pre[i])
		if rgt==len(grp)-1:
			break
	print(ans)
if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:
def main():
	n , k = map(int , input().split())
	hd = input()
	grp=[]
	if hd[0]=='1':
		grp = [[0,1]]
	else:
		grp=[[0,0]]
	cnt =1
	for i in range(1, len(hd)):
		if hd[i]==hd[i-1]:
			cnt = cnt+1
		else:
			grp.append([cnt,hd[i-1]])
			cnt = 1
	grp .append([cnt , hd[len(hd)-1]])
	pre = [0 for i in range(0 , len(grp)+9)]
	pre[0]=grp[0][0]
	for i in range(1, len(grp)):
		pre[i]=pre[i-1]+grp[i][0]
	ans = 0
	for i in range(0 , len(grp)):
	#	print(pre[i])
		if grp[i][1]==0:
			rgt = min(i+2*k, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		else:
			rgt = min(i+2*k+1, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
	print(ans)
if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:
def main():
	n , k = map(int , input().split())
	hd = input()
	grp = [[0,0]]
	cnt =1
	for i in range(1, len(hd)):
		if hd[i]==hd[i-1]:
			cnt = cnt+1
		else:
			grp.append([cnt,hd[i-1]])
			cnt = 1
	grp .append([cnt , hd[len(hd)-1]])
	pre = [0 for i in range(0 , len(grp)+9)]
	pre[0]=grp[0][0]
	for i in range(1, len(grp)):
		pre[i]=pre[i-1]+grp[i][0]
	ans = 0
	for i in range(0 , len(grp)):
	#	print(pre[i])
		if grp[i][1]==0:
			rgt = min(i+2*k, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		else:
			rgt = min(i+2*k+1, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
	print(ans)
if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = str(input())
if (S[0]=='1') and (S[-1]=='0'):
  S = S[::-1]
li = []

cnt = 1
for i in range(1, N):
  if S[i] == S[i-1]:
    cnt += 1
  else:
    li.append(cnt)
    cnt = 1
li.append(cnt)

if S[0] == '0':
  n = K * 2
  if len(li) <= n:
    ans = sum(li)
  else:
    ans = sum(li[:n])
    tmp = ans
    for i in range(len(li)-n):
      tmp = tmp - li[i] + li[i+n]
      ans = max(ans, tmp)
    if S[-1] == '1':
      ans = max(ans, tmp+li[i])
else:
  n = K * 2 + 1
  if len(li) <= n:
    ans = sum(li)
  else:
    ans = sum(li[:n])
    tmp = ans
    for i in range(len(li)-n):
      tmp = tmp - li[i] + li[i+n]
      ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = str(input())
li = []

cnt = 1
for i in range(1, N):
  if S[i] == S[i-1]:
    cnt += 1
  else:
    li.append(cnt)
    cnt = 1
li.append(cnt)

if S[0] == '0':
  n = K * 2
else:
  n = K * 2 + 1
  
if len(li) <= n:
  ans = sum(li)
else:
  ans = sum(li[:n])
  tmp = ans
  for i in range(len(li)-n):
    tmp = tmp - li[i] + li[i+n]
    ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = str(input())
li = []

cnt = 1
for i in range(1, N):
  if S[i] == S[i-1]:
    cnt += 1
  else:
    li.append(cnt)
    cnt = 1
li.append(cnt)
print(li)

if S[0] == '0':
  n = K * 2
else:
  n = K * 2 + 1
  
if len(li) <= n:
  ans = sum(li)
else:
  ans = sum(li[:n])
  for i in range(len(li)-n+1):
    ans = max(ans, sum(li[i:i+n]))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
s=input()

def rle(string):
    _rle_str = string[0]
    _rle_cnt = 1
    _ans_l = []
    for _i in range(1, len(string)):
        if _rle_str == string[_i]:
            _rle_cnt += 1
        else:
            _ans_l.append([_rle_str, _rle_cnt])
            _rle_str = string[_i]
            _rle_cnt = 1
    _ans_l.append([_rle_str, _rle_cnt])
    return _ans_l

rle_s=rle(s)

ans=-1

left=0
wa=0

if rle_s[0][0]=="0":
    cnt=1
    wa=rle_s[0][1]
    right=1
else:
    cnt=0
    right=0

if len(rle_s)==1 and k>=1:
    print(rle_s[0][1])

while right<len(rle_s):
    print(right, left, wa, cnt)
    if cnt==k:
        if rle_s[right][0]=="0":
            if rle_s[left][0]=="0":
                wa-=rle_s[left][1]
                cnt-=1
            else:
                wa-=rle_s[left][1]
            left+=1

        else:
            wa+=rle_s[right][1]
            right+=1
            ans=max(ans, wa)

    elif cnt<k:
        if rle_s[right][0]=="0":
            cnt+=1
            wa+=rle_s[right][1]
        else:
            wa+=rle_s[right][1]
        right+=1
        ans=max(ans, wa)

    else:
        if rle_s[left][0]=="0":
            wa-=rle_s[left][1]
            cnt-=1
        else:
            wa-=rle_s[left][1]
        left+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int, input().split())
s=input()

def rle(string):
    _rle_str = string[0]
    _rle_cnt = 1
    _ans_l = []
    for _i in range(1, len(string)):
        if _rle_str == string[_i]:
            _rle_cnt += 1
        else:
            _ans_l.append([_rle_str, _rle_cnt])
            _rle_str = string[_i]
            _rle_cnt = 1
    _ans_l.append([_rle_str, _rle_cnt])
    return _ans_l

rle_s=rle(s)

ans=-1

left=0
wa=0

if rle_s[0][0]=="0":
    cnt=1
    wa=rle_s[0][1]
    right=1
else:
    cnt=0
    right=0


# print(rle_s)
while right<len(rle_s):
    # print(right, left, wa, cnt)
    if cnt==k:
        if rle_s[right][0]=="0":
            if rle_s[left][0]=="0":
                wa-=rle_s[left][1]
                cnt-=1
            else:
                wa-=rle_s[left][1]
            left+=1

        else:
            wa+=rle_s[right][1]
            right+=1
            ans=max(ans, wa)

    elif cnt<k:
        if rle_s[right][0]=="0":
            cnt+=1
            wa+=rle_s[right][1]
        else:
            wa+=rle_s[right][1]
        right+=1
        ans=max(ans, wa)

    else:
        if rle_s[left][0]=="0":
            wa-=rle_s[left][1]
            cnt-=1
        else:
            wa-=rle_s[left][1]
        left+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF = 10**20
def main():
    N,K=mi()
    S_t = list(input())
    S = ["1"] + S_t + ["1","X"]

    one_count = 0
    zero_count = 0
    in_one_seq = True

    arc = []
    for s in S:
        if s == "X":
            arc.append(one_count)
            break

        if s == "0" and in_one_seq:
            arc.append(one_count)
            one_count = 0
            zero_count += 1
            in_one_seq = False

        elif s == "0" and not in_one_seq:
            zero_count += 1


        elif s == "1" and in_one_seq:
            one_count += 1
        
        else:
            arc.append(zero_count)
            zero_count = 0
            one_count += 1
            in_one_seq = True
    


    if arc[0] == 1:
        arc[0] = 0
    else:
        arc[0] -= 1
    
    if arc[-1] == 1:
        arc[-1] = 0
    else:
        arc[-1] -= 1
    
    X = [] # (score,l,r,count,j)
    Y = []
    for i in range(len(arc)):
        if i % 2 == 0: continue
        l = arc[i-1]
        r = arc[i+1]
        score = l + r + arc[i]
        count = arc[i]
        j = len(X)
        X.append((-1*score,l,r,count,j))
        Y.append((-1*score,l,r,count,j))
    
    heapq.heapify(Y) # Yは最大スコアのindexを吐く

    # print("Y:",Y)
    # print(X)

    if len(Y) == 0:
        print(len(S_t))
        exit()
        
    for i in range(K):
        if len(Y) == 0: break
        y,_,_,_,j = heapq.heappop(Y)
        mx_score,_,_,_,_ = X[j]
        
        # print(y,j)
        if 0 <= j-1:
            if X[j-1] in Y:
                Y.remove(X[j-1])

                l = X[j-1][1]
                r = -1 * mx_score
                count = X[j-1][3]

                X[j-1] = (-(l+r+count),l,r,count,X[j-1][4])
                heapq.heappush(Y,X[j-1])
            
        if j+1 < len(X):
            if X[j+1] in Y:
                Y.remove(X[j+1])

                l = -1 * mx_score
                r = X[j+1][2]
                count = X[j+1][3]

                X[j+1] = (-(l+r+count),l,r,count,X[j+1][4])
                heapq.heappush(Y,X[j+1])

        # print(X)
        # print("Y:",Y)
        
        
    # print(Y)
    if len(Y) == 0:
        print(len(S_t))
    else:
        mx = heapq.heappop(Y)
        l = mx[1]
        r = mx[2]
        print(max(l,r))
        


    





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF = 10**20
def main():
    N,K=mi()
    S_t = list(input())
    S = ["1"] + S_t + ["1","X"]

    one_count = 0
    zero_count = 0
    in_one_seq = True

    arc = []
    for s in S:
        if s == "X":
            arc.append(one_count)
            break

        if s == "0" and in_one_seq:
            arc.append(one_count)
            one_count = 0
            zero_count += 1
            in_one_seq = False

        elif s == "0" and not in_one_seq:
            zero_count += 1


        elif s == "1" and in_one_seq:
            one_count += 1
        
        else:
            arc.append(zero_count)
            zero_count = 0
            one_count += 1
            in_one_seq = True
    


    if arc[0] == 1:
        arc[0] = 0
    else:
        arc[0] -= 1
    
    if arc[-1] == 1:
        arc[-1] = 0
    else:
        arc[-1] -= 1
    
    X = [] # (score,l,r,count,j)
    Y = []
    for i in range(len(arc)):
        if i % 2 == 0: continue
        l = arc[i-1]
        r = arc[i+1]
        score = l + r + arc[i]
        count = arc[i]
        j = len(X)
        X.append((-1*score,l,r,count,j))
        Y.append((-1*score,l,r,count,j))
    
    heapq.heapify(Y) # Yは最大スコアのindexを吐く

    # print("Y:",Y)
    # print(X)

    if len(Y) <= 1:
        print(len(S_t))
        exit()
        
    for i in range(K):
        if len(Y) == 0: break
        y,_,_,_,j = heapq.heappop(Y)
        mx_score,_,_,_,_ = X[j]
        
        # print(y,j)
        if 0 <= j-1:
            if X[j-1] in Y:
                Y.remove(X[j-1])

                l = X[j-1][1]
                r = -1 * mx_score
                count = X[j-1][3]

                X[j-1] = (-(l+r+count),l,r,count,X[j-1][4])
                heapq.heappush(Y,X[j-1])
            
        if j+1 < len(X):
            if X[j+1] in Y:
                Y.remove(X[j+1])

                l = -1 * mx_score
                r = X[j+1][2]
                count = X[j+1][3]

                X[j+1] = (-(l+r+count),l,r,count,X[j+1][4])
                heapq.heappush(Y,X[j+1])

        # print(X)
        # print("Y:",Y)
        
        
    # print(Y)
    if len(Y) == 0:
        print(len(S_t))
    else:
        mx = heapq.heappop(Y)
        l = mx[1]
        r = mx[2]
        print(max(l,r))
        


    





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF = 10**20
def main():
    N,K=mi()
    S_t = list(input())
    S = ["1"] + S_t + ["1","X"]

    one_count = 0
    zero_count = 0
    in_one_seq = True

    arc = []
    for s in S:
        if s == "X":
            arc.append(one_count)
            break

        if s == "0" and in_one_seq:
            arc.append(one_count)
            one_count = 0
            zero_count += 1
            in_one_seq = False

        elif s == "0" and not in_one_seq:
            zero_count += 1


        elif s == "1" and in_one_seq:
            one_count += 1
        
        else:
            arc.append(zero_count)
            zero_count = 0
            one_count += 1
            in_one_seq = True
    


    if arc[0] == 1:
        arc[0] = 0
    else:
        arc[0] -= 1
    
    if arc[-1] == 1:
        arc[-1] = 0
    else:
        arc[-1] -= 1
    
    X = [] # (score,l,r,count,j)
    Y = []
    for i in range(len(arc)):
        if i % 2 == 0: continue
        l = arc[i-1]
        r = arc[i+1]
        score = l + r + arc[i]
        count = arc[i]
        j = len(X)
        X.append((-1*score,l,r,count,j))
        Y.append((-1*score,l,r,count,j))
    
    heapq.heapify(Y) # Yは最大スコアのindexを吐く

    # print("Y:",Y)
    # print(X)

    if len(Y) <= 1:
        print(len(S_t))
        exit()
        
    for i in range(K):
        if len(Y) == 1: break
        y,_,_,_,j = heapq.heappop(Y)
        mx_score,_,_,_,_ = X[j]
        
        # print(y,j)
        if 0 <= j-1:
            if X[j-1] in Y:
                Y.remove(X[j-1])

                l = X[j-1][1]
                r = -1 * mx_score
                count = X[j-1][3]

                X[j-1] = (-(l+r+count),l,r,count,X[j-1][4])
                heapq.heappush(Y,X[j-1])
            
        if j+1 < len(X):
            if X[j+1] in Y:
                Y.remove(X[j+1])

                l = -1 * mx_score
                r = X[j+1][2]
                count = X[j+1][3]

                X[j+1] = (-(l+r+count),l,r,count,X[j+1][4])
                heapq.heappush(Y,X[j+1])

        # print(X)
        # print("Y:",Y)
        
        
    # print(Y)

    mx = heapq.heappop(Y)
    l = mx[1]
    r = mx[2]
    print(max(l,r))
        


    





if __name__ == "__main__":
    main()