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.

Solution (Python):
N,K=map(int, input().split())
instr=input()
lft=0
rgt=1
voids=0 if instr[0] == '1' else 1

rlast='1' if instr[0] == '1' else '0'
llast='1' if instr[0] == '1' else '0'
maxlen=0
while lft < rgt:
    
    if voids <= K and rgt < N:
        maxlen = max(maxlen, rgt-lft)
        if instr[rgt-1] == '1' and instr[rgt] == '0':
            voids+=1
            rlast = '0'
        rlast = instr[rgt-1]
        rgt += 1
    else:
        if (voids <= K):
            maxlen = max(maxlen, rgt-lft)
        llast = instr[lft]
        if lft+1 < N and instr[lft] == '0' and instr[lft+1] == '1':
            voids -= 1
        lft += 1

print(maxlen)

Solution (Python):
n,k = map(int,input().split())
s = input()
next = 0
l = []
ans = 0
if s[0]=='0':
    cnt=1
else:
    cnt = 0
for i in range(1,n):
    if s[i]=='0' and s[i-1]=='1':
        cnt += 1
    if s[i]=='1' and s[i-1]=='0':
        l.insert(0,i)
    if s[i]=='0' and s[i-1]=='1' and cnt==k+1:
        ans = max(ans,i-next)
        next = l.pop()
        cnt -= 1
    if i==n-1 and s[i]=='1':
        ans = max(ans,i+1-next)
    if i==n-1 and s[i]=='0':
        ans = max(ans,i+1-next)
if ans==0:
    print(n)
else:
    print(ans)

Solution (Python):
N,K = (int(x) for x in input().split())
S = list(input())
size = [1]
memo = S[0]
for i in range(1,N):
    if S[i] == memo:
        size[-1] += 1
    else:
        memo = S[i]
        size += [1]

if S[0] == '0':
    size = [0] + size
if S[-1] == '0':
    size += [0]

if int((len(size)-1)/2) <= K:
    print(N)
else:
    ans = sum(size[0:K*2+1])
    a = ans
    for i in range(2,len(size)-(K*2))[::2]:
        a = a - (size[i-2] + size[i-1]) + (size[i+K*2-1] + size[i+K*2])
        if ans < a:
            ans = a
    print(ans)

Solution (Python):
n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)


width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for i in range(length//2+length%2)]
s_ruiseki=[0 for i in range(length+1)]
s_ruiseki[0]=0
s_ruiseki[1]=s_seqcnt[0]
for i in range(1,length):
    s_ruiseki[i+1]=s_seqcnt[i]+s_ruiseki[i]

for i in range(length//2+length%2):
    num=0
    if 2*i+width-1>=length:
        s_sum[i]=s_ruiseki[length]-s_ruiseki[2*i]
        break
    else:
        s_sum[i]=s_ruiseki[2*i+width]-s_ruiseki[2*i]

print(max(s_sum))

Solution (Python):
n,k=[int(x) for x in input().split()]
s=input()
diff=[0]
for i in range(1,len(s)):
    if s[i]!=s[i-1]:
        diff.append(i)
diff.append(n)
ans=0
for i in range(len(diff)-1):
    if s[diff[i]]=="0":
        if len(diff)-1<2*k+i:
            ans=max(diff[-1]-diff[i],ans)
        else:
            ans=max(diff[2*k+i]-diff[i],ans)
    else:
        if len(diff)-1<2*k+1+i:
            ans=max(diff[-1]-diff[i],ans)
        else:
            ans=max(diff[2*k+1+i]-diff[i],ans)
print(ans)

Solution (Python):
N,K = [int(i) for i in input().split()]
S   = input()

Z =[]
last=1
cnt =0
n = len(S)

for i,s in enumerate(S):
    if s =="0" and i==n-1:
        if last==0:
            right = i
            Z.append((left, right))
            cnt += 1    
        else:
            Z.append((i,i))
            cnt += 1
    elif last==1 and s=="0":
        left = i
        last = 0
    elif last==0 and s =="1":
        right = i-1
        last  = 1
        Z.append((left, right))
        cnt += 1

    




if K>=cnt:
    print(N)
else:
    
    len_z=len(Z)
    rem = cnt - K
    
    
    kouho = []
    _, right = Z[rem-1]
    kouho.append(n-1-right)

    left, _ =Z[len_z-rem]
    kouho.append(left)

    for i in range(rem-1):
        L = Z[i]
        R = Z[len_z-rem+i+1]
        _,right = L
        left,_  = R
        kouho.append(left-right-1)

    print(max(kouho))

Solution (Python):
N, K = [int(n) for n in input().split()]
S = input()

sentous = []
sentou = 0
max_count = 0
count = 0
prev = '1'
for s in S:
    count += 1
    sentou += 1
    if s != prev and s == '1':
        sentous.append(sentou - 1)
        sentou = 1
    elif s != prev and s == '0':
        if K > 0:
            K -= 1
        else:
            if count - 1 > max_count:
                max_count = count - 1
            count -= sentous.pop(0)
    prev = s

print(max(max_count, count))

Solution (Python):
from numpy import cumsum
N, K = map(int, input().split())
S = input()
*S, = map(int, list(S))
zeros = [0]
ones = [0]
if S[0] == 0:
    ones.append(0)
cnt = 1
now = S[0]
for i in range(1, N):
    if now == S[i]:
        cnt += 1
    else:
        if now == 0:
            zeros.append(cnt)
        else:
            ones.append(cnt)
        cnt = 1
        now = S[i]
if now == 0:
    zeros.append(cnt)
else:
    ones.append(cnt)
if S[-1] == 0:
    ones.append(0)

c_zero = cumsum(zeros)
c_one = cumsum(ones)



if len(zeros) <= K:
    print(len(S))
else:
    ans = 0
    for i in range(0, len(zeros) - K):
        
        
        aaa = c_zero[i+K]-c_zero[i] + c_one[i+K+1]-c_one[i]
        
        
        
        ans = max(aaa, ans)
    print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
S = input()
secheadinds = []
secendinds = []
prevone = True
onehead = 0
for ind, si in enumerate(S):
    if prevone == False and si == "1":
        prevone = True
        onehead = ind
    if prevone == True and si == "0":
        secheadinds += [ onehead ]
        secendinds += [ ind - 1 ]
        prevone = False
secendinds += [N-1]

if len(secheadinds) <= K:
    print(N)
else:
    ret = 0
    for ind in range(len(secheadinds) - K + 1):
        seclen = secendinds[ind+K]-secheadinds[ind] + 1
        ret = max(ret,seclen)
    print(ret)

Solution (Python):
import numpy as np

n, k = [int(x) for x in input().split()]
s = input()

zero_list = np.array([len(x) for x in s.split("1") if len(x) > 0])
one_list = np.array([len(x) for x in s.split("0") if len(x) > 0])

if k >= len(zero_list):
    print(len(s))
else:
    max_num = 0

    if len(zero_list) < len(one_list):
        for i in range(len(zero_list) - k + 1):
            tmp = zero_list[i:i+k].sum() + one_list[i:i+k+1].sum()
            if tmp > max_num:
                max_num = tmp
    else:
        if len(zero_list) == len(one_list) and int(s[0]) == 1:
            zero_list = np.insert(zero_list, 0, 0)
        max_num = zero_list[:k].sum() + one_list[:k].sum()
        for i in range(len(one_list) - k):
            tmp = zero_list[i+1:i+k+1].sum() + one_list[i:i+k+1].sum()
            if tmp > max_num:
                max_num = tmp
        tmp = zero_list[-k:].sum() + one_list[-k:].sum()
        if tmp > max_num:
            max_num = tmp

    print(max_num)

Solution (Python):
from sys import stdin

import numpy as np




N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip().split()[0]

B = [0]
count = 0
oz = 1
for s in S:
  if int(s) == oz:
    count+=1
  else:
    B.append(count)
    count=1
    oz=int(s)
B.append(count)
if oz==0:
  B.append(0)

L = len(B)-1
if 2*K+1>L:
  K = int(L/2)

B = np.cumsum(B)

C = []
for i in range(L):
  start = 2*i
  last = 2*i+2*K+1
  if last>L:
    
    break
  C.append(B[last]-B[start])

ans = max(C)
print(ans)

Solution (Python):

import numpy as np
N, K = map(int, input().split())
s = input()
S = []
S.append(1)
for c in s:
    S.append(int(c))
S.append(1)


Blocks = 2 * K + 1
l = len(S)
count = 0
Zone = []
for i in range(l-1):
    count += 1 
    if S[i] != S[i+1]:
        Zone.append(count)
        count = 0
        
if S[l-2] != S[l-1]:
    Zone.append(1)
else:
    Zone.append(count+1)


Persons = []
if Blocks >= len(Zone):
    print(N)
else:
    Persons.append(sum(Zone[0:Blocks]))
    j = 0
    while Blocks + j < len(Zone):
        Persons.append(Persons[int(j/2)]+Zone[Blocks+j]+Zone[Blocks+j+1]-Zone[j]-Zone[j+1])
        j += 2
    Persons[0] -= 1
    Persons[len(Persons)-1] -= 1
    
    print(max(Persons))

Solution (Python):
from itertools import accumulate
N,K = map(int,input().split())
S = input()

arr = []
now = S[0]
if now == "1":
    count = 1
else:
    count = -1
for c in S[1:]:
    next = c
    if c == now:
        if now == "1":
            count += 1
        else:
            count -= 1
    else:
        arr.append(count)
        if now == "1":
            count = -1
            now = "0"
        else:
            count = 1
            now = "1"
arr.append(count)

anss = []
Sum = 0
head = 0
if arr[0] < 0:
    arr = [0] + arr
arr2 = [0] + list(accumulate(list(map(abs, arr))))
while head+2*K <= len(arr):
    tail = head+2*K
    Sum += arr2[tail+(tail < len(arr2)-1)]-arr2[head]
    
    anss.append(Sum)
    head += 2
    Sum = 0
if anss == []:
    ans = sum(map(abs,arr))
else:
    ans = max(anss)
print(ans)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline


def main():
    n,k = map(int,input().split())
    s = list(input())

    
    
    tank = []
    cnt = 1
    for i in range(1,n):
        if s[i] != s[i-1]:
            tank.append(cnt)
            cnt = 0
        cnt += 1
        if i == n-1:
            tank.append(cnt)
    
    p = len(tank)

    
    if s[0] == '0' and (p+1)//2 <= k:
        print(n)
        exit()
    if p//2 <= k and s[0] == '1':
        print(n)
        exit()

    
    ans = 0
    
    res = 0
    if s[0] == '0':
        for j in range(2*k):
            res += tank[j]
        ans = res
        for j in range(2*k,p):
            if j == 2*k:
                res -= tank[0]
            elif j%2 == 0:
                res= res - tank[j-2*k] -tank[j-2*k-1]
            res += tank[j]
            ans = max(ans,res)

    else:
        for j in range(2*k+1):
            res += tank[j]
        ans = res
        for j in range(2*k+1,p):
            if j % 2 == 1:
                res = res- tank[j-2*k-1]-tank[j-2*k]
            res += tank[j]
            ans = max(ans,res)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


n, k = map(int, input().split())
s = input()
s += "2"
n += 1

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

fin = False
i = 0
while i < n:
    if fin:
        break
    for j in range(i, n):
        if s[j] != s[i]:
            nums.append(j-i)
            i = j
            break
        if i == n-1:
            fin = True
            break

if s[-2] == "0":
    nums.append(0)

length = min([2*k+1, len(nums)])

ans = 0
for i in range(0, length):
    ans += nums[i]

oldsum = ans
for i in range(0, len(nums), 2):
    if i + length + 1 < len(nums):
        newsum = oldsum - (nums[i] + nums[i+1]) + (nums[length+i] + nums[length+i+1])
        if newsum > ans:
            ans = newsum
        oldsum = newsum
    else:
        break

print(ans)

Solution (Python):
import sys
from itertools import groupby
from itertools import accumulate

input = sys.stdin.readline

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

sakadati = []

sakadati.append(0)
if S[0] == 0:
    sakadati.append(0)

for key, value in groupby(S):
    sakadati.append(len(list(value)))

sakadati.append(0)

rui = list(accumulate(sakadati))

max = 0
for i in range(len(rui) - 2 * K - 1):
    if i % 2 == 1:
        continue
    cur = rui[i + 2 * K + 1] - rui[i]
    if max < cur:
        max = cur

if len(rui) <= 2*K+1:
    print(len(S))
else:
    print(max)

Solution (Python):
import itertools

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

before = s[0]
count = 1
lst = []
head = True if before == '1' else False
tail = True if s[-1] == '1' else False

for i in s[1:]:
    if i == before:
        count += 1
    else:
        lst.append(count)
        count = 1
        before = i
lst.append(count)

S = 0

lst1 = lst
if not head:
    S = sum(lst1[:2*k])
    lst1 = lst1[1:]
if not tail:
    S = max(S, sum(lst1[-2*k:]))
    lst1 = lst1[:-1]

lst1.insert(0,0)
accum_lst = list(itertools.accumulate(lst1))


N = len(lst1)
if N <= 2*k + 1:
    S = max(S, accum_lst[-1])
else:
    K = 2*k+1
    for i in range(0, N-K, 2):
        S = max(S, accum_lst[i+K] - accum_lst[i])
        

print(S)

Solution (Python):
N, K = (int(i) for i in input().split())
S = input()

cnt = 0
mite = "1"
nlist = []
mlist = []
for i in S:
    if i != mite:
        if mite == "0":
            mite = "1"
            nlist.append(cnt)
            cnt = 0
        else:
            mite = "0"
            mlist.append(cnt)
            cnt = 0
    cnt += 1

if mite == "0":
    nlist.append(cnt)
else:
    mlist.append(cnt)

if len(mlist) == len(nlist):
    mlist.append(0)






initm = sum(mlist[0 : K + 1]) 
initn = sum(nlist[0 : K]) 

mmm = initm + initn


for i in range(len(mlist) - K - 1):
 
    initm += mlist[K + 1 + i]
    initm -= mlist[i]
    initn += nlist[K + i]
    initn -= nlist[i]
    mmm = max(mmm, initm + initn)
  
print(mmm)

Solution (Python):
n,k = map(int,input().split())
s = input()
l = [0]*n
if int(s[0]) == 0:
    l[0] = 1
for i in range(1,n):
    if s[i] ==  "0" and s[i-1]=="0":
        l[i] = l[i-1]
    elif s[i] == "0" and s[i-1] =="1":
        l[i] = l[i-1] + 1
    else:
        l[i] = l[i-1]
def solve(x):
    for i in range(0,n-x+1):
        if i ==0:
            if l[x-1] <= k:
                return True
            else:
                continue
        elif s[i] == "0":
            if l[i+x-1] - l[i] + 1 <= k:
                return True
        else:
           if l[i+x-1] - l[i] <= k:
               return True
    return False


def binary_search(ok,ng):
    while abs(ok-ng) >1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok
a = binary_search(1,n)
if solve(a+1):
    print(a+1)
else:
    print(a)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

if N==1:
    print(1)
    exit()

L=[]
cnt0=0
if S[0]=='0':
    L.append(0)
    cur=0
else:
    cur=1
cnt=0
for i in range(N):
    if cur==0:
        if S[i]=='0':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=1
            cnt0+=1
    else:
        if S[i]=='1':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=0
else:
    if cnt!=0:
        if cur==0:
            L.append(cnt)
            cnt0+=1
        else:
            L.append(cnt)
if S[-1]=='0':
    L.append(0)

acc=[0]+list(accumulate(L))
mx=0
if cnt0<K:
    K=cnt0
for i in range(0, len(acc), 2):
    if i+(K*2+1)<len(acc):
        mx=max(mx, acc[i+(K*2+1)]-acc[i])
print(mx)

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

A = [0]
B = [0]
for s in S:
  if s == '1':
    A[-1] += 1
  elif A[-1] != 0:
    A.append(0)
  if s == '0':
    B[-1] += 1
  elif B[-1] != 0:
    B.append(0)

ans = 0
c,d,e,f = 0,0,0,0

for i in range(min(len(A),len(B))):
  a = 0
  if i == 0:
    if S[0] == '1':
      c,d = sum(A[i:min(i + K + 1,len(A))]),sum(B[i:min(i + K,len(B))])
      a = c + d
    else:
      c,d = sum(A[i:min(i + K,len(A))]) , sum(B[i:min(i + K,len(B))])
      a = c + d
  else:
    if S[0] == '1':
      if i + K < len(A):
        c += A[min(i + K,len(A) - 1)] - A[i - 1]
        d += B[min(i + K - 1,len(B) - 1)] - B[i - 1]
        a = c + d
    else:
      if i + K <= len(A):
        c += A[min(i + K - 1,len(A) - 1)] - (0 if i == 1 else A[i - 2])
        d += B[min(i + K - 1,len(B) - 1)] - B[i - 1]
        a = c + d
  ans = max(ans,a)
print(ans)

Solution (Python):
n,k = [int(i) for i in input().split()]
s = [int(i) for i in input()]

num = [0]
which = s[0]
sign = [which]
for i in s:
  if i != which:
    which = 1-which
    num.append(0)
    sign.append(which)
  num[-1] += 1

num_0 = len(sign) - sum(sign)

if k >= num_0:
  print(sum(num))
  exit()

if sign[0] == 0:
  num = [0] + num

if sign[-1] == 0:
  num.append(0)

sum_now = sum(num[0:2*k+1])
ans = sum_now

for i in range(0,len(num),2):
  if i == 0:
    continue
  if i+2*k >= len(num):
    break
  
  plus = num[i+2*k-1]+num[i+2*k]
  minus = num[i-2] + num[i-1]
  diff = plus - minus
  sum_now += diff
  if sum_now > ans:
    ans = sum_now

print(ans)

Solution (Python):
import numpy as np
n,k = map(int,input().split())	
s=list(input())	

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    elif s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        elif s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
li = np.array(li)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))

Solution (Python):
n,k = map(int,input().split())
s = input()
if s[0] == "0":
    zero = []
    one = []
    c = 1
    now = s[0]
    for i in range(1, n):
        if s[i] == now:
            c += 1
            if i == n - 1:
                if now == "0":
                    zero.append(c)
                else:
                    one.append(c)
        else:
            if now == "0":
                zero.append(c)
                if i == n - 1:
                    one.append(1)
            else:
                one.append(c)
                if i == n - 1:
                    zero.append(1)
            c = 1
            now = s[i]

    pos_zero = len(zero)
    
    if pos_zero <= k:
        print(n)
        exit()
    q = sum(zero[:k])
    sum_zero = [q]
    for i in range(pos_zero - k):
        q = q - zero[i] + zero[k + i]
        sum_zero.append(q)
    pos_one = len(one)
    q = sum(one[:k])
    sum_one = [q]
    for i in range(pos_one - k):
        q = q - one[i] + one[k + i]
        sum_one.append(q)
    ans = sum_zero[0] + sum_one[0]
    
    
    for i in range(1, pos_zero - k + 1):
        if i - 1 < pos_one and i < len(sum_one):
            ansq = sum_zero[i] + sum_one[i] + one[i - 1]
        elif i < len(sum_one):
            ansq = sum_zero[i] + sum_one[i]
        elif i-1 < pos_one:
            ansq = sum_zero[i] + one[i-1]
        else:
            ansq = sum_zero[i]
        ans = max(ans, ansq)

    print(ans)
else:
    zero = []
    one = []
    c = 1
    now = s[0]
    for i in range(1, n):
        if s[i] == now:
            c += 1
            if i == n - 1:
                if now == "0":
                    zero.append(c)
                else:
                    one.append(c)
        else:
            if now == "0":
                zero.append(c)
                if i == n - 1:
                    one.append(1)
            else:
                one.append(c)
                if i == n - 1:
                    zero.append(1)
            c = 1
            now = s[i]
    one.append(0)
    pos_zero = len(zero)
    
    if pos_zero <= k:
        print(n)
        exit()
    q = sum(zero[:k])
    sum_zero = [q]
    for i in range(pos_zero - k):
        q = q - zero[i] + zero[k + i]
        sum_zero.append(q)
    pos_one = len(one)
    q = sum(one[:k+1])
    sum_one = [q]
    for i in range(pos_one - k -1):
        q = q - one[i] + one[k + i + 1]
        sum_one.append(q)
    ans = sum_zero[0] + sum_one[0]
    
    
    for i in range(1, pos_zero - k + 1):
        ansq = sum_zero[i] + sum_one[i]
        ans = max(ans, ansq)

    print(ans)

Solution (Python):


def solve():
    N, K = list(map(int, input().split(" ")))
    S = input()

    
    i = 0
    ruiseki = [0]
    while True:
        if i >= N:
            break
        
        num = 0
        if S[i] == "1":
            while i < N and S[i] == "1":
                num += 1
                i += 1
            ruiseki.append(num + ruiseki[-1])
        else:
            while i < N and S[i] == "0":
                num += 1
                i += 1
            ruiseki.append(num + ruiseki[-1])

    import math
    if S[0] == "1":
        zero_num = math.floor((len(ruiseki)-1)/2)
    else:
        zero_num = math.ceil((len(ruiseki)-1)/2)

    if K >= zero_num:
        print(ruiseki[-1])
        return

    ans = 0
    if S[0] == "1":
        for i in range(2, len(ruiseki), 2):
            end = i + 2*(K-1)
            if end >= len(ruiseki):
                break
            if end+1 < len(ruiseki):
                
                end += 1

            ans = max(ruiseki[end]-ruiseki[i-2], ans)

    else:
        for i in range(1, len(ruiseki), 2):
            end = i + 2*(K-1)
            if end >= len(ruiseki):
                break
            if end+1 < len(ruiseki):
                end += 1

            if i-2 >= 0:              
                ans = max(ruiseki[end]-ruiseki[i-2], ans)
            else:
                ans = max(ruiseki[end]-ruiseki[i-1], ans)

    print(ans)            




if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict
import sys

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

if 0 not in S:
    print(N)
    sys.exit(0)

left = defaultdict(int)
right = defaultdict(int)
index = 0
for i in range(1, N):
    if S[i-1] == 0 and S[i] == 1:
        right[index] = i
        index += 1
    elif S[i-1] == 1 and S[i] == 0:
        left[index] = i-1

    if i == N-1:
        if S[i] == 0:
            right[index] = i
            left[index+1] = i
        if S[i] == 1:
            left[index] = i

ans = 0
for ind in range(index+1):
    a = left[ind+1] - right[ind-K] + 1
    if ans < a:
        ans = a


print(ans)

Solution (Python):
n, k = [int(item) for item in input().split()]
s = [int(item) for item in list(input())]

dp = [0] * (n + 1)
dp[0] = [0, 0, 0]
for i in range(1, n + 1):
    if s[i - 1]:
        dp[i] = [dp[i - 1][0], dp[i - 1][1] + 1, dp[i - 1][2] + 1]
    elif i == 1 or s[i - 1 - 1]:
        dp[i] = [dp[i - 1][0] + 1, dp[i - 1][1] + 1, 0]
    else:
        dp[i] = [dp[i - 1][0], dp[i - 1][1] + 1, 0]

K = [[0] * 2 for _ in range(max((n + 1), k + 1))]
for x in dp:
    K[x[0]] = [x[1], x[2]]


ans = 0

for i in range(dp[-1][0] + 1):
    if k + i <= dp[-1][0]:
        ans = max(ans, K[i + k][0] - K[i][0] + K[i][1])
    else:
        ans = max(ans, K[dp[-1][0]][0] - K[i][0] + K[i][1])







print(ans)

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

s = []

cnt = 1
current = S[0]

for i in range(1, N):
    if S[i] == current:
        cnt += 1
    else:
        current = S[i]
        s += [cnt]
        cnt = 1
s += [cnt]


if S[0] == '0':
    k = (len(s)+1)//2
else:
    k = len(s)//2

if k <= K:
    print(N)
    
else:
    
    n = len(s)
    
    first = 0
    if S[0] == '0':
        end = K*2
    else:
        end = K*2+1
    m = sum(s[first:end])
    current = m
    
    if S[0] == '0':
        first = 1
    else:
        first = 2
    end += 2
    
    while(end < n):
        current = current - s[first-1] + s[end-2] + s[end-1]
        if first != 1:
            current -= s[first-2]
            
        if m < current:
            m = current
        first += 2
        end += 2
        
    current = sum(s[first:])
    if m < current:
        m = current
        
    print(m)

Solution (Python):
read = input
n,k = map(int, read().split())
a = read()
a = '1' + a + '1'

pstart = 0
pcnt = 0
ptype = '1'
b = []

for tp in enumerate(a):
    i, c = tp
    if ptype == c:
        pcnt = pcnt + 1
    else :
        b.append((pstart, i-1, pcnt))
        pstart = i
        ptype = c
        pcnt = 1
b.append((pstart, i, pcnt))

if k >= len(b)//2:
    print(sum(map(lambda tp:tp[2], b)) - 2)
else :
    start = 0
    end = k * 2
    ans = 0
    S = [0 for i in range(len(b)+10)]
    S[0] = b[0][2]
    for i in range(1, len(b)):
        S[i] = S[i-1] + b[i][2]
    while(end <= len(b) - 1):
        tmp = S[end] - (S[start - 1] if start - 1>=0 else 0)
        if b[start][0] == 0:
            tmp = tmp - 1
        if b[end][1] == len(a)-1:
            tmp = tmp -1

        ans = max(ans, tmp)
        start = start + 2
        end = end + 2
    print(ans)

Solution (Python):
n, k = [int(i) for i in input().split(" ")]
s = input()
r = []

if s[0] == "0":
    r.append(0)

c = 1
for i in range(1, n):
    if s[i - 1] == s[i]:
        c += 1
    else:
        r.append(c)
        c = 1
    
if s[n - 1] == "0":
    r.append(c)
    r.append(0)
else:
    r.append(c)

if (len(r) - 1) // 2 <= k:
    print(n)
else:
    rs = [0] * (len(r) + 1)
    for i in range(1, len(r) + 1):
        rs[i] = rs[i - 1] + r[i - 1]
    s_max = 0
    m = 0
    while m + 2 * k + 1 < len(rs):
        if s_max < rs[m + 2 * k + 1] - rs[m]:
            s_max = rs[m + 2 * k + 1] - rs[m]
        m += 2
    print(s_max)

Solution (Python):
import collections
n, k = map(int, input().split())
s = input()
zero =[]
cnt = 0
d = collections.deque()
for i, j in enumerate(s):
    if j == '0':
        cnt += 1
    if j == '1' and i > 0:
        if cnt > 0:
            zero.append((cnt, i-1))
            cnt = 0
if cnt > 0:
    zero.append((cnt, n-1))
idx = n-1
one= []
while zero:
    d.append(zero.pop())
    if len(d) < k:
        continue
    if zero:    
        i, j = zero[-1]
        one.append(idx-j)
    else:
        one.append(idx +1)
    k, l = d.popleft()
    idx = l-k
if one == []:
    one.append(n)
print(max(one))

Solution (Python):

import sys
import itertools
INF = float("inf")


def solve(N: int, K: int, S: str):
    s = []
    buf = 0
    mode = S[0]
    for c in S:
        if c == mode:
            buf += 1
        else:
            s.append(buf)
            buf = 1
            mode = c
    s.append(buf)

    
    if S[0] == "0":
        s = [0]+s
    if S[-1] == "0":
        s = s+[0]
    

    tot = [0]+list(itertools.accumulate(s))
    w = 2*K+1
    hint = [tot[i+w]-tot[i] for i in range(0, len(tot)-w, 2)]
    if len(hint) == 0:
        print(len(S))
    else:
        print(max(hint))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    S = str(next(tokens))  
    solve(N, K, S)


if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int, input().split())
st = input()
num = 0
state = 0
cumsum = []
for s in st:
    if int(s) == state:
        num += 1
    else:
        cumsum.append(num)
        state = [1, 0][state]
        num = 1
cumsum.append(num)
cumsum = [0] + cumsum + [0, 0]
if (len(cumsum) % 2) == 0:
    cumsum += [0]
l = min(k * 2, len(cumsum) - 1 - (len(cumsum) % 2))
sumsum = sum(cumsum[:l + 1])
max_sum = sumsum
start_idx = 0
end_idx = l + 1
if len(cumsum) - l + 1 > 3:
    for n in range(2, len(cumsum) - l + 1, 2):
        sumsum = (
            sumsum - sum(cumsum[start_idx: start_idx + 2])
            + sum(cumsum[end_idx: end_idx + 2])
        )
        start_idx += 2
        end_idx += 2
        max_sum = max(max_sum, sumsum)

print(max_sum)

Solution (Python):
N,K=map(int,input().split(' '))
S=input()
left=[]
right=[]
for i in range(len(S)):
	
	
	
	
	
	if len(left)>len(right):
		if S[i]=='0':
			right.append(i-1)
	elif len(left)==len(right):
		if S[i]=='1':
			left.append(i)



if len(left)>len(right):
	right.append(N-1)

section=[ [left[i],right[i]] for i in range(len(left)) ]

section=[[0, 0]] + section + [[N-1, N-1]]


length=[]

if K+1>=len(section):
	print(N)
else:
	for i in range(len(section)-K):
		length.append(section[i+K][1] - section[i][0] + 1)
	print(max(length))

Solution (Python):


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

counts = [0] if S[0] == '0' else []
s = '1' if S[0] == '1' else '0'
c = 0
for i in range(N):
    if S[i] != s:
        counts.append(c)
        c = 0
        if s == '1':
            s = '0'
        else:
            s = '1'
    c += 1
counts.append(c)

ans = 0
cumsum = [0] * (len(counts) + 1)
for i in range(len(counts)):
    cumsum[i + 1] = cumsum[i] + counts[i]
for i in range(len(counts)):
    if i % 2 == 1:
        continue
    
    r = min(i + 2 * K + 1, len(counts))
    l = i
    if r == l:
        ans = max(ans, counts[i])
    else:
        ans = max(ans, cumsum[r] - cumsum[l])
    
    
print(ans)

Solution (Python):
n,k=map(int,input().split())
s=list(map(int,input()))
lis_one=[]
lis_zero=[]
if s[0]!=1:
    lis_one.append(0)
i=0
if n==1:
    print(1)
    exit()
while i<n-1:
    cnt=1
    while s[i]==s[i+1]:
        cnt+=1
        i+=1
        if i==n-1:
            break
    if s[i]==0:
        lis_zero.append(cnt)
    else:
        lis_one.append(cnt)
    i+=1
ans=0
lis_one.append(0)
lis_zero.append(0)
oone=[]
zzero=[]
oone.append(sum(lis_one[0:k+1]))
zzero.append(sum(lis_zero[0:k]))
for i in range(len(lis_one)-k-1):
    oone.append(oone[i]-lis_one[i]+lis_one[i+k+1])
    zzero.append(zzero[i]-lis_zero[i]+lis_zero[i+k])
for i in range(len(oone)):
    ans=max(ans,oone[i]+zzero[i])
print(ans)