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(map(int,list(input())))
x = [-1]
for i in range(n-1):
    if s[i] != s[i+1]:
        x.append(i)
x.append(n-1)
t = len(x)
ans = 1

for i in range(t-1):
    if i == 0:
        ans = max(ans,x[min(t-1,i+2*k)]-x[i])
    else:
        ans = max(ans,x[min(t-1,i+2*k+1)]-x[i])

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
s = list(map(int,list(input())))
x = []
f = s[0]
cnt = 1
del s[0]
for i in s:
    if f != i:
        x.append(cnt)
        cnt = 1
        f = i
    else:
        cnt += 1
x.append(cnt)

ans = 1

for i in range(len(x)-k):
    ans = max(ans,sum(x[i:i+k+1]))
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    S = SS()

    # 1の塊の長さと位置を調べる
    l = []
    if S[0] == '1':
        l.append(0)
    for i in range(N - 1):
        if S[i] == '0' and S[i+1] == '1':
            l.append(i + 1)
        elif S[i] == '1' and S[i+1] == '0':
            l.append(i + 1)
    if S[-1] == '1':
        l.append(N)
    # print(S)
    # print(l)

    # 1の塊をK+1個くっつけた場合の長さを調べる
    ans = 0
    for i in range(len(l) // 2 - K):
        ans = max(l[2*i+2*K+1] - l[2*i], ans)

    # 端の0を逆立ちさせた場合
    # if S[0] == '0':
    #     ans = max(l[2*K-1], ans)
    # if S[-1] == '0':
    #     ans = max(N - l[len(l)-2*K], ans)
    
    # 全部1だった場合(塊の間も無いし端の0もない)
    if l == [0, N]:
        ans = N

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
s = input()
range_len = 2 * k + 1
ans = 0
block_len = []
block_len.append(0)
now = "1"
for i in s:
    if now == i:
        block_len[-1] += 1
    else:
        block_len.append(1)
        now = i
l_block = len(block_len)
# print(block_len)
if l_block <= range_len:
    print(n)
else:
    # 尺取
    tmp = sum(block_len[:range_len])
    ans = tmp
    for idx in range(l_block - range_len):
        tmp += block_len[idx + range_len] - block_len[idx]
        # print(tmp, idx)
        if idx % 2 == 1:
            # print(ans, tmp)
            ans = max(ans, tmp)

    print(ans)

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
s = input()
range_len = 2 * k + 1
if n <= range_len:
    print(n)
else:
    ans = 0
    block_len = []
    block_len.append(0)
    now = "1"
    for i in s:
        if now == i:
            block_len[-1] += 1
        else:
            block_len.append(1)
            now = i
    l_block = len(block_len)
    # print(block_len)
    if l_block <= range_len:
        print(n)
    else:
        # 尺取
        tmp = sum(block_len[:range_len])
        ans = tmp
        for idx in range(l_block - range_len):
            tmp += block_len[idx + range_len] - block_len[idx]
            # print(tmp, idx)
            if idx % 2 == 1:
                # print(ans, tmp)
                ans = max(ans, tmp)

        print(ans)

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
s = input()
range_len = 2 * k + 1
if n <= range_len:
    print(n)
else:
    ans = 0
    block_len = []
    block_len.append(0)
    now = "1"
    for i in s:
        if now == i:
            block_len[-1] += 1
        else:
            block_len.append(1)
            now = i
    l_block = len(block_len)
    # print(block_len)
    if l_block <= k:
        print(n)
    else:
        # 尺取
        tmp = sum(block_len[:range_len])
        ans = tmp
        for idx in range(l_block - range_len):
            tmp += block_len[idx + range_len] - block_len[idx]
            # print(tmp, idx)
            if idx % 2 == 1:
                # print(ans, tmp)
                ans = max(ans, tmp)

        print(ans)

Submission status: Wrong Answer

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

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

ans = 0
if S[0] == '0':
    s = [0] + s
if S[-1] == '0':
    s = s + [0]

if 2*K + 1 > len(s):
    print(sum(s))
    exit()

print(s)
for i in range(0, len(s), 2):
    if i + 2*K >= len(s):
        break
    ans = max(ans, sum(s[i:i+2*K+1]))

print(ans)

Submission status: Wrong Answer

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

S2=[]
signs=[]
if S[0]=='1':
  sign=1
else:
  sign=0
count = 1
for i in range(1,N):
  if S[i] != S[i-1]:
    S2.append(count)
    signs.append(sign)
    sign = 1- sign
    count = 0
  count += 1
  
S2.append(count)
signs.append(sign)
  
cumS = [0]
for i in range(len(S2)):
  cumS.append(cumS[-1]+S2[i])
  
k = K*2+1
if len(S2)>=k:
  MAX=0
  for i in range(len(S2)-k+1):
    if signs[i] == 1:
      tmp = cumS[i+k]-cumS[i]
      if tmp > MAX:
        MAX = tmp
  
  if signs[0]==0:
    MAX = max(MAX,cumS[k-1]-cumS[0])
  if signs[1]==0:
    MAX = max(MAX,cumS[-1]-cumS[-k])
    
else:
  MAX=cumS[-1]
  
print(MAX)

Submission status: Wrong Answer

Solution code:
from itertools import groupby

N, K = map(int, input().split())
S = input()

S = [[i, len(list(j))] for i, j in groupby(S)]

s = []
for i in range(len(S)//2):
    s.append(S[2*i][1] + S[2*i+1][1])

if len(S) % 2 != 0:
    if s == []:
        s = [S[0][1]]
    elif S[-1][0] == "1":
        s[-1] += S[-1][1]
    else:
        s.append(S[-1][1])
    
ans = sum(s[:K])
if len(s) <= K:
    print(ans)
else:
    k = ans
    for i in range(0,len(s)-K):
        k = k - s[i] + s[K+i]
        ans = max(ans, k)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
T=S+'2'
dp=[]
p,q=0,0
for i in T:
  if i=='1':
    if 0<q:
      dp.append(q)
    p+=1
    q=0
  else:
    if 0<p:
      dp.append(p)
    p=0
    q+=1
if S[0]=='0':
  if len(dp)<=2*K:
    print(sum(dp))
  else:
    if S[N-1]=='0':
      dp.append(0)
    dp.insert(0,0)
    ans=sum(dp[:2*K])
    bns=ans
    for i in range(2*K,len(dp),2):
      bns+=dp[i]+dp[i-1]-dp[i-2*K]-dp[i-2*K-1]
      ans=max(ans,bns)
    print(ans)
else:
  if len(dp)<=2*K+1:
    print(sum(dp))
  else:
    if S[N-1]=='1':
      dp.append(0)
    ans=sum(dp[:2*K])
    bns=ans
    for i in range(2*K,len(dp),2):
      bns+=dp[i]+dp[i-1]-dp[i-2*K]-dp[i-2*K-1]
      ans=max(ans,bns)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
S+='2'
dp=[]
p,q=0,0
for i in S:
  if i=='1':
    if 0<q:
      dp.append(q)
    p+=1
    q=0
  else:
    if 0<p:
      dp.append(p)
    p=0
    q+=1
if S[0]=='0':
  if len(dp)<=2*K:
    print(sum(dp))
  else:
    if S[N-1]=='0':
      dp.append(0)
    dp.insert(0,0)
    ans=sum(dp[:2*K])
    bns=ans
    for i in range(2*K,len(dp),2):
      bns+=dp[i]+dp[i-1]-dp[i-2*K]-dp[i-2*K-1]
      ans=max(ans,bns)
    print(ans)
else:
  if len(dp)<=2*K+1:
    print(sum(dp))
  else:
    if S[N-1]=='1':
      dp.append(0)
    ans=sum(dp[:2*K])
    bns=ans
    for i in range(2*K,len(dp),2):
      bns+=dp[i]+dp[i-1]-dp[i-2*K]-dp[i-2*K-1]
      ans=max(ans,bns)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
S+='2'
dp=[]
p,q=0,0
for i in S:
  if i=='1':
    if 0<q:
      dp.append(q)
    p+=1
    q=0
  else:
    if 0<p:
      dp.append(p)
    p=0
    q+=1
if S[0]=='0':
  p=[]
  if len(dp)<=2*K:
    print(sum(dp))
  else:
    if S[N-1]=='0':
      dp.append(0)
    ans=sum(dp[:2*K-1])
    bns=ans
    for i in range(2*K-1,len(dp)):
      bns+=dp[i]-dp[i-2*K]
      ans=max(ans,bns)
    print(ans)
else:
  if len(dp)<=2*K+1:
    print(sum(dp))
  else:
    if S[N-1]=='1':
      dp.append(0)
    ans=sum(dp[:2*K])
    bns=ans
    cns=ans
    for i in range(2*K,len(dp),2):
      bns+=dp[i]+dp[i-1]-dp[i-2*K]-dp[i-2*K-1]
      ans=max(ans,bns)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=input()
S+='2'
dp=[]
p,q=0,0
for i in S:
  if i=='1':
    if 0<q:
      dp.append(q)
    p+=1
    q=0
  else:
    if 0<p:
      dp.append(p)
    p=0
    q+=1
if S[0]=='0':
  p=[]
  if len(dp)<=2*K:
    print(sum(dp))
  else:
    if S[N-1]=='0':
      dp.append(0)
    ans=sum(dp[:2*K-1])
    bns=ans
    for i in range(2*K-1,len(dp)):
      bns+=dp[i]-dp[i-2*K]
      ans=max(ans,bns)
    print(ans)
else:
  if len(dp)<=2*K+1:
    print(sum(dp))
  else:
    if S[N-1]=='1':
      dp.append(0)
    print(dp)
    ans=sum(dp[:2*K])
    bns=ans
    cns=ans
    for i in range(2*K,len(dp),2):
      bns+=dp[i]+dp[i-1]-dp[i-2*K]-dp[i-2*K-1]
      ans=max(ans,bns)
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
s = input()
ms = 0
ps = 0
temp = [0]
if s[0] == "0":
    temp.append(0)
for i in s:
    # print(i,ps,ms)
    if i == "0":
        ms += 1
        if ps:
            temp.append(ps)
            ps = 0
    else:
        ps += 1
        if ms:
            temp.append(ms)
            ms = 0
if ms:
    temp.append(ms)
else:
    temp.append(ps)
# print(temp)
for i in range(len(temp)-1):
    temp[i+1] += temp[i]
# print(temp)
ans = 0
if len(temp)-(2*k+1) <= 0:
    ans = temp[-1]
else:
    for i in range(0,len(temp)-(2*k+1),2):
        ans = max(ans,temp[i+2*k+1]-temp[i])
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
flag=s[0]
a=[0,1]
for i in s[1:]:
  if flag==i:a[-1]+=1
  else:
    a+=[a[-1]+1]
    flag=i
a+=[a[-1]]
m=len(a)
l=0
r=int(s[0]=='0')+1
ans=a[r]
while r<m:
  ans=max(a[r]-a[l],ans)
  if r+2-l>2*k+1:
    if l:l+=2
    else:l+=int(s[0]=='0')
    r+=2
  else:
    r+=2
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
flag=s[0]
a=[0,1]
for i in range(1,n):
  if flag==s[i]:a[-1]+=1
  else:
    a+=[a[-1]+1]
    flag=s[i]
a+=[a[-1]]
m=len(a)
l=int(s[0]=='0')
r=l+1
ans=a[r]
while r<m:
  ans=max(a[r]-a[l],ans)
  if r+2-l>2*k+1:
    l+=2
    r+=2
  else:
    r+=2
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=[int(i) for i in input()]
l1,l0=[],[]
b,c=1,0
for i in s:
  if b==i: c+=1
  else:
    if b: l1+=[c]
    else: l0+=[c]
    c=1
  b=i
if b:
  l1+=[c]
  l0+=[0]
else:
  l0+=[c]
S=[0]
for i,j in zip(l1,l0):
  S+=[S[-1]+i+j]
m=len(S)-1
if m<=k: print(n)
else:
  a=0
  for i in range(k,m):
    a=max(a,S[i]-S[i-k]+l1[i])
  print(a)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
L = [0]
X = ['1']
pos = 0
for i in range(N):
  if S[i] != X[pos]:
    L.append(1)
    X.append(S[i])
    pos += 1
  else:
    L[pos] += 1
while pos < 2 * K + 4:
  L.append(0)
  X.append('1')
  pos += 1
L.append(0)
X.append('1')
n = len(L)
for i in range(1, n):
  L[i] += L[i-1]
M = L[2*K]
for i in range(1, n-2*K):
  if X[i] == '1':
    M = max(L[2*K+i] - L[i-1], M)

Submission status: Wrong Answer

Solution code:
from itertools import groupby
from math import ceil

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

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

m = len(block)
res = block[0]
left, right = 0, 2*k
val = sum(block[left:right-1])
while right <= m:
    val += block[right-1] if right == m else block[right-1] + block[right]
    res = max(res, val)
    val -= block[left] + block[left+1]
    left += 2
    right += 2
print(res)

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
S = list(input())
X = []
Y = []
cnt = 0
flag = 0
for i in range(N):
    if flag==int(S[i]):
        cnt += 1
    else:
        if flag==1:
            Y.append(cnt)
            flag = 0
            cnt = 1
        elif flag==0:
            X.append(cnt)
            flag = 1
            cnt = 1
    if i==N-1:
        if flag==1:
            Y.append(cnt)
        else:
            X.append(cnt)
LX = len(X)
LY = len(Y)
if X[0]==0:
    l0 = 1
    r0 = min(K,LX-1)
else:
    l0 = 0
    r0 = min(K-1,LX-1)

l1 = 0
r1 = min(K-1,LY-1)

out = sum(X[l0:(r0+1)])+sum(Y[l1:(r1+1)])
cand = out

while (r1+1<=LY-1) and (r0+1<=LX-1):
    cand += X[r0+1]+Y[r1+1]
    cand += -1*(X[l0]+Y[l0])
    out = max(out,cand)
    l0+=1
    r0+=1
    l1+=1
    r1+=1
print(out)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()+"2"
L = []
cnt = 0
temp = int(S[0])

for x in S:
  if temp == int(x):
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
    temp = int(x)

if S[0] == "0":
  Lcs = [0, 0]
else:
  Lcs = [0]

for x in L:
  Lcs.append(Lcs[-1] + x)
 
ans = Lcs[1]
N = len(Lcs)
i = 2

while i + 2*(K-1) <= N-1:
  if i + 2*(K-1) == N-1:
    ans = max(ans, Lcs[i + 2*(K-1)]-Lcs[i-2])
  else:
    ans = max(ans, Lcs[i + 2*(K-1) +1]-Lcs[i-2])
  i += 2

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()+"2"
L = []
cnt = 0
temp = int(S[0])

for x in S:
  if temp == int(x):
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
    temp = int(x)

if S[0] == "0":
  Lcs = [0, 0]
else:
  Lcs = [0]

for x in L:
  Lcs.append(Lcs[-1] + x)
 
ans = Lcs[1]
N = len(Lcs)
i = 2

while i + 2*(K-1) <= N-1:
  if i + 2*(K-1) == N-1:
    ans = max(ans, Lcs[i + 2*(K-1)]-Lcs[i-2])
  else:
    ans = max(ans, Lcs[i + 2*(K-1) +1]-Lcs[i-2])
    print(ans)
  i += 2

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
a=[]
b=s[0]
c=0
mc=0
for i in range(n):
  if s[i]==b:
    c+=1
  elif s[i]=="1":
    a.append(-1*c)
    c=1
    b="1"
    mc+=1
  else:
    a.append(c)
    c=1
    b="0"
if s[i]=="1":
  a.append(c)
else:
  a.append(-c)
  mc+=1

mc2=min(k,mc)
sm=0
i=0
while mc2>=0 and i<len(a):
  if a[i]>0:
    sm+=a[i]
  else:
    if mc2>0:
      sm-=a[i]
      mc2-=1
    else:
      break
  i+=1
smm=sm
st=0

while i<len(a):
  sm=sm-abs(a[st])+abs(a[i])
  st+=1
  i+=1

  if sm> smm: smm=sm
print(smm)

Submission status: Wrong Answer

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

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

m = len(cnt)
if( m <= 2*k+1):
    print(n)
    exit()

l = 0
r = 2*k+1
tmp = sum(cnt[:r])
ans = tmp
while(r+2 <= m):
    tmp += cnt[r] + cnt[r+1] - cnt[l] - cnt[l+1]
    ans = max(ans,tmp)
    l += 2
    r += 2
print(ans)

Submission status: Wrong Answer

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

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

m = len(cnt)
if( m <= 2*k+1):
    print(n)
    exit()

l = 0
r = 2*k+2
tmp = sum(cnt[:r])
ans = tmp
while(r+2 <= m):
    tmp += cnt[r] + cnt[r+1] - cnt[l] - cnt[l-1]
    ans = max(ans,tmp)
    l += 2
    r += 2
print(ans)

Submission status: Wrong Answer

Solution code:

n,k=map(int,input().split())
s=list(input())
t=[int(int(i)==0) for i in s]
for i in range(1,n):
  t[i]+=t[i-1]
# print(t)
t=[t[0]]+t
from bisect import*
ans=0
for i in range(t[-1]):
  tmp=bisect(t,i+k+1)-bisect(t,i)
  ans=max(ans,tmp)
print(ans+1)

Submission status: Wrong Answer

Solution code:

n,k=map(int,input().split())
s=list(input())
t=[int(int(i)==0) for i in s]
for i in range(1,n):
  t[i]+=t[i-1]
# print(t)
t=[t[0]]+t+[t[-1]]
from bisect import*
ans=0
for i in range(t[-1]):
  tmp=bisect(t,i+k+1)-bisect(t,i)
  ans=max(ans,tmp)
print(ans+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=list(input())
t=[int(int(i)==0) for i in s]
for i in range(1,n):
  t[i]+=t[i-1]
# print(t)
from bisect import*
ans=0
for i in range(t[-1]):
  tmp=bisect(t,i+k+1)-bisect(t,i)
  ans=max(ans,tmp)
print(ans+1)

Submission status: Wrong Answer

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

n,k = map(int, input().split())
s = input().rstrip()

li = []
fi = int(s[0])
cnt = 1
for i in range(1, n):
    if s[i-1] == s[i]:
        cnt += 1
    else:
        li.append(cnt)
        cnt = 1
li.append(cnt)

ans = 0
ma = k*2+1 if fi == 1 else k*2
ma = min(ma, len(li))
nn = max(1, len(li) - ma + 1)
for j in range(0, nn):
    sum = 0
    i = j
    tmp = 0
    while tmp != ma:
        sum += li[i]
        tmp += 1
        i += 1
    ans = max(ans, sum)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
        if S[i] == 0:
            cnt += 1
    num += 1
L.append(num)
if S[-1] == '0':
    cnt += 1
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
        if S[i] == 0:
            cnt += 1
    num += 1
L.append(num)
if S[-1] == 0:
    cnt += 1
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

Submission status: Wrong Answer

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k <= len(off)-1:
        b += off[i+k]
      b -= off[i-1]
    # print (a,b)
    s = a+b
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k-1 <= len(off)-1:
        b += off[i+k-1]
      b -= off[i-2]
    s = a+b
    print (a,b)
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Wrong Answer

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k <= len(off)-1:
        b += off[i+k]
      b -= off[i-1]
    # print (a,b)
    s = a+b
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k-1 <= len(off)-1:
        b += off[i+k-1]
      b -= off[i-1]
    s = a+b
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Wrong Answer

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = sum(on[i:i+k]) + sum(off[i:i+k+1])
    # print (sum(on[i:i+k]),sum(off[i:i+k+1]))
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      s = sum(on[i:i+k]) + sum(off[i:i+k])
      # print (sum(on[i:i+k]),sum(off[i:i+k]))
    else:
      s = sum(on[i:i+k]) + sum(off[i-1:i+k])
      # print (sum(on[i:i+k]),sum(off[i-1:i+k]))
    ans = max(ans,s)
if ans == 0:
  print (n)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N+1)

for l in range(N):
	while r < N and used[r] - used[l-1] <= K:
		r += 1
		if S[r-1] == 1 and S[r] == 0:
			used[r] = used[r-1] + 1
		else:
			used[r] = used[r-1]
	ans = max(ans, r-l)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = input()

flg = [int(S[0])]
count = []
cnt = 1
tmp = S[0]

for x in S[1:]:
	if x == tmp:
		cnt += 1
	else:
		tmp = x
		flg.append(int(tmp))
		count.append(cnt)
		cnt = 1
count.append(cnt)

ans = 0
m = len(flg)
i = 0
while i+2*K <= m:
	if flg[i]:
		ans = max(ans, sum(count[i:i+2*K+1]))
	else:
		ans = max(ans, sum(count[i:i+2*K]))
	i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
L = [0]
X = ['1']
pos = 0
for i in range(N):
  if S[i] != X[pos]:
    L.append(1)
    X.append(S[i])
    pos += 1
  else:
    L[pos] += 1
while pos < 2 * K + 2:
  L.append(0)
  X.append('1')
  pos += 1
for i in range(1, pos+1):
  L[i] += L[i-1]
M = L[2*K]
for i in range(1, pos+1-2*K):
  if X[i] == '1':
    M = max(L[2*K+i] - L[i-1], M)
print(M)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
S = list(input())
nums = []
now = 1
cnt = 0
for s in S:
    if s == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

sums = [0] + list(np.cumsum(nums))
left = 0
right = left + K * 2
maxi = 0
if N < 3:
    maxi = N
while right < len(nums):
    if sums[right+1] - sums[left] > maxi:
        maxi = sums[right+1] - sums[left]
    right += 2
    left += 2
print(maxi)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
S = list(input())
nums = []
now = 1
cnt = 0
for s in S:
    if s == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

sums = [0] + list(np.cumsum(nums))
left = 0
right = left + K * 2
maxi = 0
if N < 3:
    maxi = len(nums)
while right < len(nums):
    if sums[right+1] - sums[left] > maxi:
        maxi = sums[right+1] - sums[left]
    right += 2
    left += 2

print(maxi)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
L = [0, 1]
X = ['1', S[0]]
pos = 1
for i in range(1, N):
  if S[i] != S[i-1]:
    L.append(1)
    X.append(S[i])
    pos += 1
  else:
    L[pos] += 1
while pos < 2 * K + 2:
  L.append(0)
  X.append('1')
  pos += 1
for i in range(1, pos+1):
  L[i] += L[i-1]
M = L[2*K-1]
for i in range(1, pos+1-2*K):
  if X[i] == '1':
    M = max(L[2*K+i] - L[i-1], M)
print(M)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
L = [0, 1]
X = ['1', S[0]]
pos = 1
for i in range(1, N):
  if S[i] != S[i-1]:
    L.append(1)
    X.append(S[i])
    pos += 1
  else:
    L[pos] += 1
while pos < 2 * K + 2:
  L.append(0)
  X.append('1')
  pos += 1
for i in range(1, pos+1):
  L[i] += L[i-1]
M = L[2*K]
for i in range(1, pos+1-2*K):
  if X[i] == '1':
    M = max(L[2*K+i] - L[i-1], M)
print(M)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = list(input())
nums = []
now = 1
cnt = 0
for s in S:
    if s == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

left = 0
right = left + K * 2
maxi = 1
while right < N:
    if sum(nums[left:right+1]) > maxi:
        maxi = sum(nums[left:right+1])
    right += 2
    left += 2

print(maxi)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = list(input())
nums = []
now = 1
cnt = 0
for s in S:
    if s == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

left = 0
right = left + K * 2
maxi = 0
while right < N:
    if sum(nums[left:right+1]) > maxi:
        maxi = sum(nums[left:right+1])
    right += 2
    left += 2

print(maxi)

Submission status: Wrong Answer

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

s = list(map(int,input()))

ans = 0

x = []

f = s[0]

z = 0
o = 0
ans = 0

Word = s

count=1
if len(Word)>1:
    for i in range(1,len(Word)):
       if Word[i-1]==Word[i]:
          count+=1
       else :
           x.append(count)
           count=1
    x.append(count)
else:
    i=0
    x.append(count)
    
if k > len(x):
    print(sum(x))
else:
    for i in range(len(x)-k):
        ans = max(ans,sum(x[i:i+k+1]))
    print(ans)

Submission status: Wrong Answer

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

nums=[]

if(s[0]=='0'):
    nums.append(0)

num=s[0]
numi=0
for i in range(n):
    if(s[i]==num):
        numi+=1
    else:
        nums.append(numi)
        numi=1
        num=s[i]
else:
    nums.append(numi)

if(s[-1]=='1'):
    nums.append(0)

#print(nums)

ans=0
zero_num=len(nums)//2
if(zero_num<=k):
    print(sum(nums))
else:
    l=2*k
    sumi=sum(nums[:l+1])
    ans=sumi
    i=0
    while(l+2<len(nums)):
        sumi+=(nums[l+1]+nums[l+2])
        l+=2
        sumi-=(nums[i]+nums[i+1])
        i+=2
        ans=max(ans,sumi)

    l=1-2*k
    sumi=sum(nums[l:])
    ans=max(ans,sumi)
    i=-1
    while(0<=l-2):
        sumi+=(nums[l-1]+nums[l-2])
        l-=2
        sumi-=(nums[i]+nums[i-1])
        i-=2
        ans=max(ans,sumi)
    print(ans)

Submission status: Wrong Answer

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

nums=[]

if(s[0]=='0'):
    nums.append(0)

num=s[0]
numi=0
for i in range(n):
    if(s[i]==num):
        numi+=1
    else:
        nums.append(numi)
        numi=1
        num=s[i]
else:
    nums.append(numi)

if(s[-1]=='1'):
    nums.append(0)

#print(nums)

ans=0
zero_num=len(nums)//2
if(zero_num<=k):
    print(sum(nums))
else:
    l=2*k
    sumi=sum(nums[:l+1])
    ans=sumi
    i=0
    while(l+2<len(nums)):
        sumi+=(nums[l+1]+nums[l+2])
        l+=2
        sumi-=(nums[i]+nums[i+1])
        i+=2
        ans=max(ans,sumi)

    ans=max(ans,sum(nums[1-2*k:]))
    print(ans)

Submission status: Wrong Answer

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

nums=[]

if(s[0]=='0'):
    nums.append(0)

num=s[0]
numi=0
for i in range(n):
    if(s[i]==num):
        numi+=1
    else:
        nums.append(numi)
        numi=1
        num=s[i]
else:
    nums.append(numi)

if(s[-1]=='1'):
    nums.append(0)

print(nums)

ans=0
zero_num=len(nums)//2
if(zero_num<=k):
    print(sum(nums))
else:
    l=2*k
    sumi=sum(nums[:l+1])
    ans=sumi
    i=0
    while(l+2<len(nums)):
        sumi+=(nums[l+1]+nums[l+2])
        l+=2
        sumi-=(nums[i]+nums[i+1])
        i+=2
        ans=max(ans,sumi)

    ans=max(ans,sum(nums[1-2*k:]))
    print(ans)