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):
from itertools import*
n, k = map(int, input().split())
s = input()
d = [len(list(t)) for _, t in groupby(s)]
if s[0] == "0":
    d = [0] + d
a = [0] + list(accumulate(d))
m = l = 0
while True:
  try:
    m = max(m, a[l+2*k+1] - a[l])
    l += 2
  except IndexError:
    m = max(m, a[-1] - a[l])
    break
print(m)

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

zero_index_left = []
flag = False
for i in range(N):
    if flag is False and S[i] == "0":
        zero_index_left.append(i)
        flag = True
    elif S[i] == "1":
        flag = False

if K >= len(zero_index_left):
    print(N)
    exit()
    
zero_index_right = []
S = S[:: -1]
flag = False
for i in range(N):
    if flag is False and S[i] == "0":
        zero_index_right.append(i)
        flag = True
    elif S[i] == "1":
        flag = False
        
ans = 0
for i in range(len(zero_index_left) - K):
    if i == 0:
        ans = max(ans, zero_index_left[i + K])
        ans = max(ans, zero_index_right[i + K])
    else:
        ans = max(ans, zero_index_left[i + K] - N + 1 + zero_index_right[-i] - 1)
        ans = max(ans, zero_index_right[i + K] - N + 1 + zero_index_left[-i] - 1)
print(ans)

Solution (Python):
from itertools import accumulate
def main():
    n,k = map(int, input().split())
    s = list(input())
    ls = []

    cnt = 0
    buf = '1'
    for ele in s:
        if ele != buf:
            ls.append(cnt)
            cnt = 1
            buf = ele
        else:
            cnt += 1
    ls.append(cnt)

    if buf == '0':
          ls.append(0)

    w = 2*k+1
    if w >= len(ls):
          print(n)
    else:
          acc = [0] + list(accumulate(ls))
          ans = 0
          for i in range(0,len(ls)-w+1,2):
               ans = max(ans,acc[i+w]-acc[i])
          print(ans)

main()

Solution (Python):
n,k=map(int,input().split())
s=input()
l=[]
if s[0]=="0":
  l.append(0)

from itertools import groupby,accumulate
gr=groupby(s)

for K,g in gr:
  l.append(len(list(g)))

l_sum=list(accumulate(l))
l_sum=[0]+l_sum

add=2*k+1
ans=0
for i in range(0,len(l)+1,2):
  left=i
  right=min(i+add,len(l))
  tmp=l_sum[right]-l_sum[left]
  ans=max(tmp,ans)
print(ans)

Solution (Python):
from itertools import accumulate

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

count=[0]
if S[0]=="0":
    count.append(0)

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

l=len(count)
count=list(accumulate(count))
ans=0
for i in range(0,l,2):
    ans=max(ans,count[min(l-1,i+2*K+1)]-count[i])
print(ans)

Solution (Python):
N,K=map(int,input().split())
S=list(map(int,input()))
c1=[]
c0=[]
count=0
if S[0]==0:
    c1.append(0)
for i in range(N-1):
    count=count+1
    if S[i]!=S[i+1]:
        if S[i]==1:
            c1.append(count)
        else:
            c0.append(count)
        count=0
count=count+1
if S[N-1]==1:
    c1.append(count)
else:
    c0.append(count)
    c1.append(0)
if len(c0)<=K:
    print(N)
else:
    ans0=sum(c0[:K])
    ans1=sum(c1[:K+1])
    ans=ans0+ans1
    for i in range(len(c0)-K):
        ans0=ans0-c0[i]+c0[i+K]
        ans1=ans1-c1[i]+c1[i+K+1]
        ans=max(ans,ans0+ans1)
    print(ans)

Solution (Python):
n, k = map(int, input().split())
s = input()
res = []

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

l = len(res)
su = [0] * (l + 1)
for i in range(l):
    su[i + 1] = su[i] + res[i]

mil = min(l, 2 * k + 1)

ans = 1
for i in range(0, l - mil + 1, 2):
    ans = max(ans, su[mil + i] - su[i])
print(ans)

Solution (Python):
n, k = map(int, input().split())
s = input()
lis = [0]
j = 0
if s[0] == '0':
    lis.append(0)
    j = 1

lis[j] += 1
for i in range(1,n):
    
    if s[i] != s[i-1]:
        j += 1
        lis.append(0)
    lis[j] += 1
if s[n-1] == '0':
    lis.append(0)

com = [0] * (len(lis) + 1)
for i in range(len(lis)):
    com[i+1] = com[i] + lis[i]

ans = 0
for i in range(len(lis)):
    if i % 2 == 0:
        ans = max(ans,lis[i])
l = 0
while l < len(com):
    r = l + (2 * k + 1)
    if r >= len(com):
        r = len(com) - 1
    ans = max(ans,com[r] - com[l])
    l += 2
print(ans)

Solution (Python):
from itertools import accumulate
n, k = map(int, input().split())
s = [i for i in input()]
zero_one = [0]
if s[0] == "0":
    zero_one.append(0)
s_ = s[0]
cnt = 0
for i in range(n):
    if s_ == s[i]:
        cnt += 1
    else:
        zero_one.append(cnt)
        cnt = 1
        s_ = s[i]
zero_one.append(cnt)
if s[-1] == "0":
    zero_one.append(0)
ans = 0
l = len(zero_one)
zero_one = list(accumulate(zero_one))
for i in range(0, l, 2):
    ans = max(ans, zero_one[min(l-1, i+2*k+1)] - zero_one[i])
print(ans)

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

nums = []
cnt = 1
if S[0] == "0":
  nums.append(0)
for i in range(N):
  if i == N-1 or S[i] != S[i+1]:
    nums.append(cnt)
    cnt = 1
  else:
    cnt += 1
if S[-1] == "0":
  nums.append(0)

Sum = [0]*(len(nums)+1)
for i in range(1, len(nums)+1):
  Sum[i] = Sum[i-1] + nums[i-1]

ans = 0
if len(nums) <= 2*K+1:
  ans = N
else:
  for i in range(0, len(nums) - 2*K+1, 2):
    ans = max(ans, Sum[i+2*K+1] - Sum[i])

print(ans)

Solution (Python):


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

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

tsum = [0]*(len(t)+1)
for i in range(len(t)):
    tsum[i+1] = tsum[i] + t[i]



ans = 0
for i in range(1+int(s[0])%2, len(tsum)-2*k,2):
    tmp = tsum[i+2*k] - tsum[i-1]
    
    ans = max(ans, tmp)

if ans==0:
    ans = len(s)
print(ans)

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


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

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

    cumsum = [0 for _ in range(len(counts) + 1)]
    for i in range(0, len(counts)):
        cumsum[i + 1] = cumsum[i] + counts[i]

    res = 0
    for left in range(0, len(cumsum), 2):
        right = left + 2 * K + 1
        if right >= len(cumsum):
            right = len(cumsum) - 1
        res = max(res, cumsum[right] - cumsum[left])

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
s = input()
a = []
c = 1
for i in range(n-1):
    if s[i]==s[i+1]:
        c+=1
    else:
        a.append(c)
        c = 1
a.append(c)
b = [0]
for i in range(len(a)):
    b.append(b[-1]+a[i])
b.append(b[-1])
n = len(b)
l = 2*k+1
st=int(s[0])
ans = 0
for i in range(st,n,2):
    ans = max(ans,b[i]-b[max(0,i-l)])
print(ans)

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

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

nums = []
now = 1
cnt = 0
for s in S:
    if s == str(now):
        cnt += 1
    else:
        now = 1 - now
        nums.append(cnt)
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if now == 0:
    nums.append(0)

C = [0] * (len(nums)+1)
for i in range(len(nums)):
    C[i+1] = C[i] + nums[i]

ans = 0
m = 2 * K + 1
for i in range(0, max(len(nums)-m+1, 1), 2):
    m = min(m, len(nums))
    ans = max(ans, C[i+m] - C[i])

if len(nums) != 1:
    print(ans)
else:
    print(nums[0])

Solution (Python):
n, k = map(int, input().split())
s = input()
l = []
c = 1
for i in range(n - 1):
    if s[i] != s[i + 1]:
        l.append(c)
        c = 0
    c += 1
l.append(c)
l += [0]
if s[0] == '0':
    l = [0] + l
tmp = sum(l[:2 * k + 1])
rslt = tmp
for i in range(0, len(l) - 2*k-2, 2):
    tmp = tmp - l[i] - l[i + 1] + l[i + 2 * k + 1] + l[i + 2 * k + 2]
    rslt = max(tmp, rslt)
print(rslt)

Solution (Python):
n,k = map(int,input().split())
s = input()
al = []

a0 = 1
    
for i in range(n-1):
    if s[i] != s[i+1]:
        al.append(a0)
        a0 = 1
    else:
        a0 += 1
        
al.append(a0)

if s[0] == "0":
    al = [0] + al
if s[-1] == "0":
    al = al + [0]
    
nn = len(al)
nagasa = min(2*k+1,nn)
r = (nn-nagasa) // 2

ans = sum(al[:nagasa])
cur = sum(al[:nagasa])
for i in range(1,r+1):
    cur = cur + (al[nagasa+i*2-1] + al[nagasa+i*2-2]) -(al[i*2-1] + al[i*2-2])
    ans = max(cur,ans)
    
print(ans)

Solution (Python):
n,k=map(int,input().strip().split())
s=input().strip()
l=r=0
c=0
while r<n and s[r]=='1': r+=1
while c<k:
 while r<n and s[r]=='0':r+=1
 while r<n and s[r]=='1':r+=1
 if r==n:print(n);exit()
 c+=1
ans=r-l
while r<n:
 while l<n and s[l]=='1':l+=1
 while l<n and s[l]=='0':l+=1 
 while r<n and s[r]=='0':r+=1
 while r<n and s[r]=='1':r+=1
 ans=max(ans,r-l)
print(ans)

Solution (Python):
N, K = map(int, input().split())
S = input()
L = []
R = []
maximum = 0
if S[0] == "0":
    L.append(0)
if S[N-1] == "0":
    R.append(N-1)
for n in range(N-1):
    if S[n] == "1" and S[n+1] == "0":
        L.append(n+1)
    if S[-n-1] == "1" and S[-n-2] == "0":
        R.append(N-n-2)
L.append(N)
R.append(-1)
R.reverse()
if len(L) <= K:
    print(N)
else:
    for n in range(len(L)-K):
        maximum = max(maximum, L[n+K]-R[n]-1)
    print(maximum)

Solution (Python):
n, k = map(int, input().split())
s = input()
tmp1 = 0
tmp1_list = []
tmp2 = 0
tmp2_list = []
cnt0 = 0
flag = 0

for i in range(n):
    if flag == 0:
        if s[i] == "0":
            cnt0 += 1
            flag = 1
            tmp1 += 1
            tmp2 += 1
        else:
            tmp1 += 1
            tmp2 += 1
    else:
        if s[i] == "1":
            tmp1_list.append(tmp1)
            tmp1 = 1
            tmp2 += 1
            flag = 0
        else:
            tmp1 += 1
            tmp2 += 1
    if cnt0 == k + 1:
        tmp2_list.append(tmp2 - 1)
        tmp2 -= tmp1_list.pop(0)
        cnt0 -= 1
    if i == n - 1:
        tmp2_list.append(tmp2)

print(max(tmp2_list))

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]

N,K = inputlist()
S = list(input())
li = []
s = S[0]
for i in range(1,N):
    if S[i] == S[i-1]:
        s += S[i]
    else:
        li.append(s)
        s = S[i]
li.append(s)
n = len(li)
dic = {}
indexa = 0
ans = 0
ksum = [0]*n
ksum[0] = len(li[0])
for i in range(1,n):
    ksum[i] = ksum[i-1]+len(li[i])
for i in range(n):
    if li[i][0] == '0':
        indexa +=1
        dic[indexa] = i
if indexa <= K:
    print(N)
    exit()
if K == 1:
    for i in range(1,indexa+1):
        j = dic[i]
        if i == 1:
            m = ksum[j+1]
            ans = max(ans,m)
            continue
        if j == n-1:
            m = ksum[j]-ksum[j-2]
            ans = max(ans,m)
            continue
        else:
            m = ksum[j+1]-ksum[j]+1
            m += ksum[j-1]-ksum[j-2]
            ans = max(m,ans)
else:
    for i in range(K,indexa+1):
        j = dic[i]
        l = dic[i-K+1]
        sup = 0
        inf = 0
        if j == n-1:
            sup = ksum[j]
        if j != n-1:
            sup = ksum[j+1]
        if l != 0:
            inf = ksum[l-2]
        m = sup-inf
        ans = max(ans,m)
print(ans)

Solution (Python):
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i //= 2
    return

def get_sum(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans += tree[s]
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans += tree[t]
            t = (t - 1) // 2
    return ans

n, k = map(int, input().split())
s = list(input())
t = []
if s[0] == "0":
    t.append(0)
u = s[0]
c = 0
for i in s:
    if i == u:
        c += 1
    else:
        t.append(c)
        u = i
        c = 1
t.append(c)
if s[n - 1] == "0":
    t.append(0)
lt = len(t)
tree = make_tree(lt)
for i in range(lt):
    update(i, t[i])
k = 2 * k + 1
ans = 0
if lt - k > 0:
    for i in range((lt - k) // 2 + 1):
        ans = max(ans, get_sum(2 * i, 2 * (i + (k - 1) // 2)))
else:
    ans = n
print(ans)

Solution (Python):
import numpy as np

N,K = map(int, input().split())
S = [int(x) for x in input()]

memo = np.zeros(10**5+1, dtype = np.int64)
W = min(2*K, 10**5)

current = 1 
p = 0

for x in S:
  if x == current:
    memo[p] += 1
  else:
    current = 1 - current
    p += 1
    memo[p] += 1

ans = memo[:W+1].sum()
x = ans
for r in range(2,10**5+1,2):
  if r+W > 10**5:
    break
  x = x-memo[r-2]-memo[r-1]+memo[r+W]+memo[r+W-1]
  if x > ans:
    ans = x

print(ans)

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

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



t = 0
S = 0
C = 0
ans = 0
for s in range(len(L)):
    while C <= k and t < len(L):
        if C == k and L[t][1] == 0:
            break
        S += L[t][0]
        if L[t][1] == 0:
            C += 1
        t += 1
    
    ans = max(ans, S)
    if s == t:
        t += 1
    else:
        S -= L[s][0]
        if L[s][1] == 0:
            C -= 1
print(ans)

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

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



t = 0
S = 0
C = 0
ans = 0
for s in range(len(L)):
    while C <= k and t < len(L):
        if C == k and L[t][1] == 0:
            break
        S += L[t][0]
        if L[t][1] == 0:
            C += 1
        t += 1
    
    ans = max(ans, S)
    if s == t:
        t += 1
    else:
        S -= L[s][0]
        if L[s][1] == 0:
            C -= 1
print(ans)

Solution (Python):
n,k=map(int,input().split())
s=input()
l=[]
c=1
for i in range(n-1):
  if not s[i]==s[i+1]:
    l.append(c)
    c=0
  c+=1
l.append(c)
l=l+[0]
if s[0]=='0':
  l=[0]+l
tmp=sum(l[:2*k+1])
ans=tmp
for i in range(2,len(l)-2*k,2):
  tmp=tmp-l[i-1]-l[i-2]+l[i+2*k-1]+l[i+2*k]
  ans=max(ans,tmp)
print(ans)

Solution (Python):
N, K = map(int,input().split())
S = input()
s = []
if S[0]=='0':s = [0]
for x in S.replace('01', '0,1').replace('10','1,0').split(','):
    s.append(len(x))
M = len(s)
ans = [0] * M
ans[0] = sum(s[:2*K+1])

for i in range(2, M, 2):
    ans[i] = ans[i-2] - s[i-2] - s[i-1] + sum(s[min(i+2*K-1,M):i+2*K+1])
print(max(ans))

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  import numpy as np
  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0.append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0.append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1.append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0.append(c0)
    chk_1.append(0)
  elif c1 != 0:
    chk_1.append(c1)
    chk_0.append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  ab = np.array([x+y for x,y in zip(chk_0,chk_1)])
  np.cumsum(ab,out=ab)

  ans = ab[k-1]
  for i in range(len(ab)-k):
    chk = ab[k+i]-ab[i]
    chk += chk_1[i]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def main():  
  import sys
  input = sys.stdin.readline
  import numpy as np

  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  chk_0_append = chk_0.append
  chk_1_append = chk_1.append
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0_append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0_append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1_append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0_append(c0)
    chk_1_append(0)
  elif c1 != 0:
    chk_1_append(c1)
    chk_0_append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  chk_1 = tuple(chk_1)
  chk_0 = tuple(chk_0)
  ab = np.array([x+y for x,y in zip(chk_0,chk_1)])
  np.cumsum(ab,out=ab)
  ab = tuple(ab)
  
  ans = ab[k-1]
  for i in range(len(ab)-k):
    chk = ab[k+i]-ab[i]
    chk += chk_1[i]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections
import bisect

input = sys.stdin.readline

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

zerocnt = collections.Counter()
zeroindex = [-1] * N
onecnt = collections.Counter()
oneindex = [-1] * N

zh = oh = None
for i, x in enumerate(S):
    if x == "0":
        if i == 0 or S[i - 1] == "1":
            zh = i
    else:
        if i == 0 or S[i - 1] == "0":
            oh = i
    if zh is not None:
        zeroindex[i] = zh
        zerocnt[zh] += x == "0"
    if oh is not None:
        oneindex[i] = oh
        onecnt[oh] += x == "1"

zerolist = sorted(zerocnt.keys()) + [N]
onelist = sorted(onecnt.keys())


def solve():
    maxval = -1
    maxrange = None
    for i, head in enumerate(zerolist):
        zstart = max(i - K, 0)
        start = zerolist[zstart]
        if start > 0:
            assert S[start - 1] == "1"
            start = oneindex[start - 1]
        val = head - start
        if maxval < val:
            maxval = val
            maxrange = (start, head)
    return maxval


if len(zerocnt) <= K:
    print(N)
else:
    print(solve())

Solution (Python):


nim,mike=map(int,input().split())
data=input()
X=[]
Y=[0]
_s='2'
for i,s in enumerate(data):
  if _s!=s:
    _s=s
    X.append(i)
    Y.append((int(s)+1)%2)
import itertools
Y=list(itertools.accumulate(Y))
ans=[]
for i,x in enumerate(X):
  if Y[-1]-Y[i]<=mike:
    ans.append(nim-x)
    break
  else:
    if data[x]=='0':
      ans.append(X[i+2*mike]-x)
    else:
      ans.append(X[i+2*mike+1]-x)
print(max(ans))

Solution (Python):
N, K = map(int, input().split())
S = input()
Nums = []
now = 1 
cnt = 0 
for i in range(N):
    if S[i] == 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)

Add = 2 * K + 1



sum = [0] * (len(Nums) + 1)
for i in range(len(Nums)):
    sum[i + 1] = sum[i] + Nums[i]
ans = 0

for i in range(0, len(Nums), 2):
    
    left = i
    right = min(i + Add, len(Nums))
    tmp = sum[right] - sum[left]
    ans = max(tmp, ans)

print(ans)

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

key = [0]
for i in range(1, n):
  if s[i] != s[i-1]:
    key.append(i)
key.append(n)

m, r = 0, len(key)-1
ans = 0
while True:
  if m == 0 and s[0] == "0":
    p = m+2*k
    if ans < key[min([p, r])] - key[m]:
      ans = key[min([p, r])] - key[m]
    m += 1
  else:
    p = m+2*k+1
    if ans < key[min([p, r])] - key[m]:
      ans = key[min([p, r])] - key[m]
    m += 2
  if p >= r:
    break

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

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

    cnt = []
    pre = S[0]
    S.append(-1)
    c = 1
    for s in S[1:]:
        if s == pre:
            c += 1
        else:
            cnt.append(c)
            pre = s
            c = 1
    
    if S[0] == 0:
        cnt = [0] + cnt
    if S[-2] == 0:
        cnt.append(0)
    
    K = K * 2 + 1
    ans = sum(cnt[:K])
    sc = ans
    for i in range(2, len(cnt)-K+1, 2):
        sc = sc - cnt[i-1] - cnt[i-2] + cnt[i+K-1] + cnt[i+K-2]
        ans = max(ans, sc)
    print(ans)

if __name__ == '__main__':
    main()

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




SS = []
if S[0] == '0':
    SS.append(0)
i = 0
while i < len(S):
    j = i
    while j < len(S) and S[j] == S[i]:
        j += 1
    SS.append(j - i)
    i = j
if S[-1] == '0':
    SS.append(0)




sums = [0 for _ in range(len(SS) + 1)]
for i in range(len(SS)):
    sums[i + 1] = sums[i] + SS[i]



ans = 0
for left in range(0, len(sums), 2):
    right = left + K * 2 + 1
    if right >= len(sums): 
        right = len(sums) - 1
    ans = max(ans, sums[right] - sums[left])
print(ans)

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

starts = [0]
ends = []

for i in range(1, n-1):
    if s[i] == '1' and s[i-1] == '0':
        starts.append(i)
    if s[i] == '1' and s[i+1] == '0' and len(starts) == len(ends) + 2:
        ends.append(i)

ends.append(n-1)

ans = 0
m = len(ends)
for i in range(m-k+1):
    ans = max(ans, ends[i+k-1] - starts[i] + 1)

if k >= m:
    ans = n

print(ans)

Solution (Python):
import sys

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



zero = []
string = s[0]
count = 0; left = 0; right = 0; num = 0
for i in range(n):
	if s[i] == string:
		count += 1
	else:
		if string == '0':
			num = count
			string = '1'
		else:
			if num != 0:
				zero.append([num,left,count])
			string = '0'
			left = count
			num = 1
		count = 1


if string == '0':
	zero.append([count,left,0])
else:
	zero.append([num,left,count])


if len(zero) <= k:
	print(len(s))
	sys.exit()



res = 0
for i in range(k):
	res += zero[i][0] + zero[i][1]
res += zero[i][2]



ans = res
for i in range(len(zero)-k):
	res -= zero[i][0] + zero[i][1]
	res += zero[i+k][0] + zero[i+k][2]
	ans = max(ans,res)

print(ans)

Solution (Python):
import sys

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

zero = []
string = s[0]
count = 0
left = 0
right = 0
num = 0
for i in range(n):
	if s[i] == string:
		count += 1
	else:
		if string == '0':
			num = count
			string = '1'
		else:
			if num != 0:
				zero.append([num,left,count])
			string = '0'
			left = count
			num = 1
		count = 1

if string == '0':
	zero.append([count,left,0])
else:
	zero.append([num,left,count])

if len(zero) <= k:
	print(len(s))
	sys.exit()
res = 0
for i in range(k):
	res += zero[i][0] + zero[i][1]
res += zero[i][2]

ans = res
for i in range(len(zero)-k):
	res -= zero[i][0] + zero[i][1]
	res += zero[i+k][0] + zero[i+k][2]
	ans = max(ans,res)

print(ans)

Solution (Python):
import sys

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

zero = []
one = []
string = s[0]
if string == '0':
	flag = True
else:
	flag = False
count = 0
left = 0
right = 0
num = 0
for i in range(n):
	if s[i] == string:
		count += 1
	else:
		if string == '0':
			num = count
			string = '1'
		else:
			one.append(count)
			if num != 0:
				zero.append([num,left,count])
			string = '0'
			left = count
			num = 1
		count = 1

if string == '0':
	zero.append([count,left,0])
else:
	zero.append([num,left,count])
	one.append(count)


if len(zero) <= k:
	print(len(s))
	sys.exit()
res = 0
for i in range(k):
	res += zero[i][0] + zero[i][1]
res += zero[i][2]

ans = res
for i in range(len(zero)-k):
	res -= zero[i][0] + zero[i][1]
	
	res += zero[i+k][0] + zero[i+k][2]
	
	ans = max(ans,res)
print(ans)

Solution (Python):
n, k = map(int, input().split())
s = "
B = []
L = []
for i in range(n):
  if s[i] != s[i+1]:
    B.append(int(s[i+1]))
    L.append(i+1)
ans = 0
for j, b in enumerate(B):
  if b == 0:
    if j+2*k >= len(L):
      ans = max(ans, n+1 - L[j])
    else:
      ans = max(ans, L[j+2*k] - L[j])
  else:
    if j+2*k+1 >= len(L):
      ans = max(ans, n+1 - L[j])
    else:
      ans = max(ans, L[j+2*k+1] - L[j])
print(ans)

Solution (Python):
n,k=map(int,input().split())
s=input()
cnt=[]
now=s[0]
p=0
for i in range(n):
	if s[i]==now:
		p+=1
	else:
		cnt.append(p)
		now=s[i]
		p=1
cnt.append(p)
ans=0
r=[]
cum_sum=0
for i in range(len(cnt)):
	cum_sum+=cnt[i]
	r.append((cnt[i],cum_sum))
for i in range(len(r)):
	if s[r[i][1]-r[i][0]]=="1":
		e=r[min(i+2*k,len(r)-1)][1]-r[i][1]+r[i][0]
	else:
		e=r[min(i+2*k-1,len(r)-1)][1]-r[i][1]+r[i][0]
	ans=max(ans,e)
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
s = readline().rstrip().decode()
cumsum = []
check = []
flag = True
for i in range(n):
    if s[i] == '0':
        if flag:
            cumsum.append(i)
        flag = False
    else:
        if not flag:
            check.append(i)
        flag = True
if not flag:
    check.append(n)
cumsum.append(n)
if len(cumsum) - 1 <= k:
    print(n)
else:
    ans = cumsum[k]
    for i in range(k, len(cumsum) - 1):
        ans = max(ans, cumsum[i + 1] - check[i - k])
    print(ans)

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

lst = [0]
for i in range(N - 1):
    if S[i] != S[i + 1]:
        lst.append(i + 1)
lst.append(N)


sub = []
for j in range(1, len(lst)):
    sub.append(S[lst[j - 1]:lst[j]])

diff = [lst[i + 1] -lst[i] for i in range(len(lst) - 1)]


if S[0] == '1' and len(lst) - 1 <= 2 * K + 1:
    print(N)
elif S[0] == '0' and len(lst) - 1 <= 2 * K:
    print(N)
else:
    candicate = []
    for i in range(len(lst) - 1 - K * 2):
        if S[lst[i]] == '1':
            candicate.append(lst[i + K * 2 + 1] - lst[i])
    if S[-1] == '0':
        candicate.append(lst[-1] - lst[-1 - K * 2])
    for i in range(len(lst) - K * 2):
        if S[lst[i]] == '0':
            candicate.append(lst[i + K * 2] - lst[i])
    
    print(max(candicate))

Solution (Python):
N,K=map(int,input().split())
S=input()
X=[]
Y=[0]
_s='2'
for i,s in enumerate(S):
  if _s!=s:
    _s=s
    X.append(i)
    Y.append((int(s)+1)%2)
import itertools
Y=list(itertools.accumulate(Y))
ans=[]
for i,x in enumerate(X):
  if Y[-1]-Y[i]<=K:
    ans.append(N-x)
    break
  else:
    if S[x]=='0':
      ans.append(X[i+2*K]-x)
    else:
      ans.append(X[i+2*K+1]-x)
print(max(ans))

Solution (Python):
from itertools import accumulate

def main():
    n, k = map(int, input().split())
    s = input()
    z = [len(i) for i in s.split("1") if i]
    o = [0] * (s[0] == "0") + [len(i) for i in s.split("0") if i] + [0]
    az = [0] + list(accumulate(z))
    ao = [0] + list(accumulate(o))
    if k < len(z):
        print(max(ao[i + k + 1] - ao[i] + az[i + k] - az[i] for i in range(len(z) - k + 1)))
    else:
        print(n)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


streak = [0, 0]
N, K = lr()
S = sr() + '2'
cur = 1
for i in range(N):
    if S[i] != S[i+1]:
        streak.append(cur)
        cur = 1
    else:
        cur += 1

streak_cum = list(itertools.accumulate(streak))
streak_cum.extend([streak_cum[-1], streak_cum[-1]])
if S[0] == '0':
    start = 0
else:
    start = 1
answer = 0

limit = len(streak_cum) - 1
for i in range(start, len(streak_cum), 2):
    result = streak_cum[min(limit, i+2*K+1)] - streak_cum[i]
    if result > answer:
        answer = result

print(answer)

Solution (Python):
from functools import reduce


def main():
    n, k = tuple(map(int, input().split()))
    s = input().strip()
    start = 0
    count_zero = {}

    for i, c in enumerate(s):
        if c == "0":
            if i == start:
                count_zero[start] = 0

            count_zero[start] += 1
        elif c == "1":
            start = i + 1

    if len(count_zero) <= k:
        print(n)
        return

    count_zero[-1] = 1
    count_zero[n] = 1

    count_zero_list = sorted(count_zero.items(), key=lambda pair: pair[0])

    print(reduce(lambda ans, i:
        max(ans, count_zero_list[i + k + 1][0] - (count_zero_list[i][0] + count_zero_list[i][1])),
        range(0, len(count_zero) - k - 1), 0))


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
S = (stdin.readline().rstrip())
zero = []
one = []
tmp = 1
S += "@"

for i in range(N):
    if S[i] == S[i+1]:
        tmp += 1
    else:
        if S[i] == "0":
            zero.append(tmp)
        else:
            one.append(tmp)
        tmp = 1
        
if K >= len(zero):
    print(N)
else:
    if S[0] == "1":
        tmp = sum(zero[:K]) + sum(one[:K+1])
        ans = sum(zero[:K]) + sum(one[:K+1])

        for i in range(0,len(zero)-K):
            tmp -= zero[i]
            tmp += zero[i+K]
            tmp -= one[i]
            if not i+K+1 >= len(one):
                tmp += one[i+K+1]
            ans = max(ans,tmp)
        print(ans)
    else:
        tmp = sum(zero[:K]) + sum(one[:K])
        ans = sum(zero[:K]) + sum(one[:K])

        for i in range(0,len(zero)-K):
            tmp -= zero[i]
            tmp += zero[i+K]
            if i != 0:
                tmp -= one[i-1]
            if not i+K >= len(one):
                tmp += one[i+K]
            ans = max(ans,tmp)
        print(ans)