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())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

n = len(seq)
sum = sum(seq[:2*k + 1])
ans = sum
seq.append(0)
for i in range(0, n - 2*k - 1, 2):
    sum -= seq[i] + seq[i + 1]
    sum += seq[i + 2*k + 1] + seq[i + 2 * k + 2]
    ans = max(ans, sum)
print(ans)

Solution (Python):
N,K = map(int,input().split())
S = input()
one = [0]
zero = [0]
if S[0] == '0':
    one.append(0)
cnt = 1
for i in range(1,len(S)):
    if S[i] != S[i-1]:
        if S[i-1] == '1':
            one.append(cnt+one[-1])                
        else:
            zero.append(cnt+zero[-1])                
        cnt = 1
    else:
        cnt += 1
else:
    if S[-1] == '1':
        one.append(cnt+one[-1])                
    else:
        zero.append(cnt+zero[-1])                
        one.append(one[-1])                
window_size = min(len(zero)-1,K)
MAX = 0
for i in range(len(zero)-window_size):
    if MAX < (zero[i+window_size] - zero[i]) + (one[i+window_size+1] - one[i]):
        MAX = (zero[i+window_size] - zero[i]) + (one[i+window_size+1] - one[i])

print(MAX)

Solution (Python):



def main():
  n, k = map(int, input().split())
  s = input().strip()
  sz, ez = [], []
  i = 0
  while i < n:
    if s[i] == '0':
      sz.append(i)
      while i < n and s[i] == '0': i += 1
      ez.append(i)
    else:
      i += 1
  
  if k >= len(sz):
    print(len(s))
    return 
  max = -1
  for i in range(len(sz)-k+1):
    if i==0:
      score = sz[i+k] - 0
    elif i==len(sz)-k:
      score = n - ez[i-1]
    else:
      score = sz[i+k] - ez[i-1]
    if max < score:
      max = score
  print(max)
      

if __name__=='__main__':
  main()

Solution (Python):
n,k=map(int,input().split())
S=list(input())
A=[]
a=1
for i in range(n-1):
  if S[i]==S[i+1]:
    a=a+1
  else:
    A.append(a)
    a=1
A.append(a)
b=len(A)
if S[0]=="0":
  if k>=(b+1)//2:
    print(n)
  else:
    A.insert(0,0)
    ans=0
    d=0
    for i in range(2*k+1):
      d=d+A[i]
      ans=d
    for i in range((b-2*k)//2):
      d=d-A[2*i]-A[2*i+1]+A[(k+i)*2+1]+A[(k+i+1)*2]
      if d>ans:
        ans=d
    if S[-1]=="0":
      d=d-A[b-(k+1)*2+1]-A[b-(k+1)*2+2]+A[b]
      if d>ans:
        ans=d
    print(ans)  
else:
  if k>=len(A)//2:
    print(n)
  else:
    ans=0
    d=0
    for i in range(2*k+1):
      d=d+A[i]
      ans=d
    for i in range((b-2*k-1)//2):
      d=d-A[2*i]-A[2*i+1]+A[(k+i)*2+1]+A[(k+i+1)*2]
      if d>ans:
        ans=d
    if S[-1]=="0":
      d=d-A[b-(k+1)*2]-A[b-(k+1)*2+1]+A[b-1]
      if d>ans:
        ans=d
    print(ans)

Solution (Python):
N, K = map(int, input().split())
S = input()
l = [1]
for i in range(N-1):
  if S[i] == S[i+1]:
    l[-1] += 1
  else:
    l.append(1)
if S[0] == "0":
  l = [0] + l
if S[-1] == "0":
  l += [0]

n = len(l)
ans = sum(l[:min(K*2+1, n+1)])
i = 0
M = ans
while True:
  if K*2 + i+1 >= n:
    break
  M = M + l[K*2+1 + i] + l[K*2+1 + i+1] - l[i] -l[i+1]
  
  ans = max(ans, M)
  i += 2
print(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)

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

add = 2 * K + 1
ans = 0
tmp = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(i + add, len(nums))
    tmp = csum[right] - csum[left]
    ans = max(ans, tmp)
print(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
ans = 0
left = 0
right = 0
tmp = 0
for i in range(0, len(nums), 2):

    next_left = i
    next_right = min(i + add, len(nums))

    while next_left > left:
        tmp -= nums[left]
        left += 1

    while next_right > right:
        tmp += nums[right]
        right += 1

    ans = max(ans, tmp)
print(ans)

Solution (Python):
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
"""
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
"""
tmp=0
for i in range(len(S)):
    if i<tmp:
        continue
    j=tmp
    while(S[j]==S[i]):
        j+=1
        if j==len(S):
            break
    C.append(j-i)
    tmp=j
if S[-1]=="0":
    C.append(0)
if len(C)==1:
    print(sum(C))
    exit()
ans=0

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

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

Solution (Python):
import math
import copy
from copy import deepcopy
import sys
import fractions

from functools import reduce

import heapq
sys.setrecursionlimit(100001)






def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n, k = map(int, input().split())
d = str(input())
tmp = list(d)
data = [int(s) for s in tmp]

ans = 0

cnt_list = []

tmp = 1
cnt = 0
for i in range(n):
    if data[i] == tmp:
       cnt += 1
    else:
        cnt_list.append(cnt)
        cnt = 1
        tmp = 1 - tmp
if cnt != 0:
    cnt_list.append(cnt)

if len(cnt_list) % 2 == 0:
    cnt_list.append(0)

sum_list = [0]
sum_num = 0
for d in cnt_list:
    sum_num += d
    sum_list.append(sum_num)

tmp_ans = 0
for i in range(0, len(sum_list), 2):
    left = i
    right = min(i + 2*k+1, len(sum_list)-1)
    tmp_ans = sum_list[right] - sum_list[left]
    ans = max(ans, tmp_ans)

print(ans)

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

L = [0]
tmp = '1'

"""
下記をLに格納する。

0,2,4,6...番目のidxは1の値の個数
1,3,5,7,...番目のidxは0の値の個数

また、Lの最後の要素は「1の値の個数」となるようにする。
（なので、0になることもある）
これで、無理やりLの要素数を必ず奇数になるように強制する。
これで「1の値の個数」で始まって終わる配列を取得する。
"""

for s in S:
  if s == tmp:
    L[-1] += 1
  else:
    L.append(1)
  tmp = s

if tmp == '0':
  L.append(0)



M = len(L)
if M <= 2*K+1:
  ans = N
  print(ans)
  exit()




X = [0]*(M+1)
for i in range(M):
  X[i+1] = X[i] + L[i]



ans = 0
for m in range(0,M-2*K,2):
  _ = X[2*K+m+1]-X[m]
  ans = max(ans, _)


print(ans)

Solution (Python):
N,K=map(int,input().split())
S=input()
L=[0]


tmp="1"
for i in range(N):
    if tmp!=S[i]:
        L.append(1)
    else:
        L[-1]+=1
    tmp=S[i]

if tmp=="0":
    L.append(0)


M=len(L)

if M<=2*K+1:
    print(N)
    exit()


X=[0 for i in range(M+1)]
for i in range(M):
    X[i+1]=L[i]+X[i]


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

Solution (Python):

N,K=map(int,input().split())
S=input()
cnt=[]
if S[0]=='0':
    cnt.append(0)
res=1
for i in range(1,N):
    if S[i-1]==S[i]:
        res+=1
    else:
        cnt.append(res)
        res=1
cnt.append(res)
if S[-1]=='0':
    cnt.append(0)

cnt_sum=[0]
for i in range(len(cnt)):
    tmp=cnt_sum[i]+cnt[i]
    cnt_sum.append(tmp)
    
ans=1
for i in range(0,len(cnt_sum),2):
    res=cnt_sum[min(len(cnt_sum)-1,2*K+1+i)]-cnt_sum[i]
    ans=max(ans,res)
    
print(ans)

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

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

memo = [0]

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

ans = 0
for i in range(len(memo)):
    start = memo[i]
    if (s[start] == 1):
        end = i + 2*k +1
    else:
        end = i + 2*k
    if end < len(memo):
        end = memo[end]
    else:
        end = len(s)
    ans = max(ans, end-start)
print(ans)

Solution (Python):
from sys import stdin
from itertools import groupby,accumulate
n,k = map(int,stdin.readline().rstrip().split())
s = stdin.readline().rstrip()
li = []
for key, value in groupby(s):
    li.append((key,len(list(value))))

if li[0][0] != "1":
    li = [("1",0)]+li
if li[-1][0] != "1":
    li.append(("1",0))
lin = [i[1] for i in li]
if len(lin)//2 < k:
    k = len(lin)//2
lin = [0,0]+list(accumulate(lin))
ma = lin[2]
for i in range((k+1)*2,len(lin),2):
    ma = max(ma,lin[i]-lin[i-(k+1)*2+1])
print(ma)

Solution (Python):
N,K = map(int,input().split())
S = input()+"w"
A = []
if S[0]=="0":A.append(0)
a,b = 0,""
for s in S:
    if b!="" and b!=s:
        A.append(a)
        a=1
    else:a+=1
    b=s
if S[-2]=="0":A.append(0)
B = [0]
for i in range(len(A)):
    B.append(B[i]+A[i])
ans = 0
N = len(B)
for i in range(2*K+1,N):
    if i%2==0:continue
    ans = max(ans,B[i]-B[i-2*K-1])
print(ans if ans else B[N-1])

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

T='0'+S+'0'
ans,cnt=0,0
for i,(a,b) in enumerate(zip(S,S[1:])):
  if a=='0' and b=='1':
    cnt+=1
  elif cnt==k and a=='1' and b=='0':
    ans=max(ans,i+1)
    break
else:
  print(n)
  exit()
  
S,cnt=S[::-1],0
for i,(a,b) in enumerate(zip(S,S[1:])):
  if a=='0' and b=='1':
    cnt+=1
  elif cnt==k and a=='1' and b=='0':
    ans=max(ans,i+1)
    break
else:
  print(n)
  exit()
  
x,y=[],[]
for i,(a,b) in enumerate(zip(T,T[1:])):
  if a==b: continue
  if a=='0':
    x.append(i)
  else:
    y.append(i)
for a,b in zip(x,y[k:]):
  ans=max(ans,b-a)
print(ans)

Solution (Python):
import numpy as np
N,K = map(int,input().split())
S = input()
stands = []
temp = ''
first_handstand = False
for i,s in enumerate(S):
    if i == 0:
        temp += s
        continue
    if temp[-1] == s:
        temp += s
    else:
        stands.append(len(temp))
        temp = s
stands.append(len(temp)) 
if S[0] == '0':
    stands.insert(0,0)
if S[-1] == '0':
    stands.append(0)
cumsum_stands = np.cumsum(np.array(stands))
cumsum_stands = np.insert(cumsum_stands,0,0)

ans = 0

for l in range(0,len(cumsum_stands),2):
    r = min(l + 2*K+1,len(cumsum_stands)-1)
    ans = max(ans, cumsum_stands[r] - cumsum_stands[l])
print(ans)

Solution (Python):
n, k = map(int, input().split())
s = input()
b = [1]
if s[0] == "0":
    b = [0, 1]
for i in range(1, n):
    if s[i-1] != s[i]:
        b += [1]
    else:
        b[-1] += 1
if s[-1] == "0":
    b += [0]
if len(b)//2 <= k:
    print(n)
    exit()

x = a = sum(b[:k*2+1])
for i in range(k, len(b)//2):
    a += b[i*2+1]+b[(i+1)*2]
    a -= b[(i-k)*2]+b[(i-k)*2+1]
    x = max(a, x)
print(x)

Solution (Python):
n,k = map(int, input().split())
s = input()
lis=[]
z_cnt=0
o_cnt=0
for num in s:
    if num=="0":
        z_cnt+=1
        if o_cnt!=0:
            lis.append(o_cnt)
            o_cnt=0
    else:
        o_cnt+=1
        if z_cnt!=0:
            lis.append(z_cnt)
            z_cnt=0
if z_cnt!=0:
    lis.append(z_cnt)
if o_cnt!=0:
    lis.append(o_cnt)

first_zero = s[0]=="0"
if first_zero:
    ind=k*2
    low=-1
else:
    ind=1+k*2
    low=0
sm=0

if ind > len(lis):
    print(sum(lis))
    exit()
for i in range(ind):
    sm+=lis[i]
ans=sm
while True:
    if low ==-1:
        sm-=lis[0]
    else:
        sm-=lis[low+1]+lis[low]
    if ind+1>=len(lis):
        sm+=lis[ind]
    else:
        sm+=lis[ind]+lis[ind+1]
    if sm > ans:
        ans=sm
    ind+=2
    low+=2
    if ind+1>len(lis):
        break
print(ans)

Solution (Python):
from itertools import accumulate as ac

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

l = []
c = 0

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

if S[0]==0:
    l = [0]+l
if S[-1]==0:
    l.append(0)

size = len(l)
*a, = ac([0]+l)
group_size = min(2*K+1,size)

ans = 0
for i in range(group_size, size+1, 2):
    ans = max(ans, a[i]-a[i-group_size])
print(ans)

Solution (Python):
from itertools import accumulate as ac

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

l = []
c0, c1 = 0, 0

prev = 0
for i, j  in enumerate(S):
    if i==0:
        if j==0:
            c0 += 1
        else:
            c1 += 1
    else:
        if prev!=j:
            if prev==1:
                l.append(c1)
                c1 = 0
            else:
                l.append(c0)
                c0 = 0
        if j==0:
            c0 += 1
        else:
            c1 += 1
    prev = j

if c0:
    l.append(c0)
if c1:
    l.append(c1)

if S[0]==0:
    l = [0]+l
if S[-1]==0:
    l.append(0)

size = len(l)
accum = list(ac([0]+l))
start = min(2*K+1,size)

ans = 0
for i in range(start, size+1, 2):
    ans = max(ans, accum[i]-accum[i-start])
print(ans)

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

ZERO, ONE = [], []
now = "1"
count = 0
for c in s:
    if c == now:
        count += 1
    else:
        if now == "0":
            ZERO.append(count)
        else:
            ONE.append(count)
        now = c
        count = 1
ONE.append(count)
ONE[0] -= 1; ONE[-1] -= 1

m = len(ZERO)
if k >= m:
    print(n)
    exit()

answer = temporary = sum(ZERO[:k]) + sum(ONE[:k + 1])
for i in range(m - k):
    temporary += ZERO[i + k] + ONE[i + k + 1]
    temporary -= ZERO[i] + ONE[i]
    answer = max(answer, temporary)

print(answer)

Solution (Python):
from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    first=[int(S[i]) for i in range(0,N-num+1)]
    last=[int(S[i+num-1]) for i in range(0,N-num+1)]
    test=[]
    for i in range(0,num):
        test.append(int(S[i]))
    sub=groupby(test)
    count=0
    for key,group in sub:
        if key==0:
            count+=1
    if K>=count:
        flag=1
    for i in range(1,N-num+1):
        if first[i-1]==0 and first[i]==1:
            count-=1
        if last[i-1]==1 and last[i]==0:
            count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

Solution (Python):
from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    first=[int(S[i]) for i in range(0,N-num+1)]
    last=[int(S[i+num-1]) for i in range(0,N-num+1)]
    test=[]
    for i in range(0,num):
        test.append(int(S[i]))
    sub=groupby(test)
    count=0
    for key,group in sub:
        if key==0:
            count+=1
    if K>=count:
        flag=1
    for i in range(1,N-num+1):
        if first[i-1]==0 and first[i]==1:
            count-=1
        if last[i-1]==1 and last[i]==0:
            count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

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

how_many=[]
num=[]

counter=0
for i in range(1,n):
    counter+=1
    if s[i-1]!=s[i]:
        how_many.append(counter)
        num.append(int(s[i-1]))
        counter=0
how_many.append(counter+1)
num.append(int(s[-1]))


ans=0
accumulate=[0]
for i in range(len(how_many)):
    accumulate.append(accumulate[-1]+how_many[i])

for g in range(len(num)):
    l=g
    if num[l]==0:
        r=min(g+2*k,len(num))
    else:
        r=min(g+2*k+1,len(num))
    ans=max(ans,accumulate[r]-accumulate[l])
print(ans)

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

how_many=[]
num=[]

counter=0
for i in range(1,n):
    counter+=1
    if s[i-1]!=s[i]:
        how_many.append(counter)
        num.append(int(s[i-1]))
        counter=0
how_many.append(counter+1)
num.append(int(s[-1]))


ans=0
accumulate=[0]
for i in range(len(how_many)):
    accumulate.append(accumulate[-1]+how_many[i])

for g in range(len(num)):
    l=g
    if num[l]==0:
        r=min(g+2*k,len(num))
    else:
        r=min(g+2*k+1,len(num))
    ans=max(ans,accumulate[r]-accumulate[l])
print(ans)

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

offset = not (int(S[0]) ^ (K & 1))
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
answer = prev

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    if prev > answer:
        answer = prev

print(answer)

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

offset = not (int(S[0]) ^ (K & 1))
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
answer = prev

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    if prev > answer:
        answer = prev

print(answer)

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

offset = not (int(S[0]) ^ (K & 1))
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
answer = prev

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    answer = max(answer, prev)

print(answer)

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

offset = int(S[0]) == (K & 1)
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
candidates.append(prev)

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    candidates.append(prev)

print(max(candidates))

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



ans = 0
L, R = 0, 0
s.append(-1)  


counter = 0
    
while R < n:
    
    if (counter < k) or (counter == k and s[R] == 1):
        if s[R] == 0 and s[R+1] == 1:
            counter += 1
        ans = max(ans, R - L + 1)
        R += 1
    
    
    elif L < R:
        if s[L] == 0 and s[L+1] == 1:
            counter -= 1
        L += 1        
    
    
    elif L == R:  
        L += 1
        R += 1
        
print(ans)

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

def runLength(s):
  if len(s) == 0: return []
  if len(s) == 1: return [(s, 1)]
  res = []
  lc = 1
  for i in range(1, len(s)):
    if s[i-1] == s[i]:
      lc += 1
    else:
      res.append((s[i-1], lc))
      lc = 1
  res.append((s[i], lc))
  return res

S = runLength(input())
accsum = [0] * (1 + (S[0][0] == "0"))
for i in range(len(S)):
  accsum.append(accsum[-1] + S[i][1])
if S[-1][0] == "0":
  accsum.append(accsum[-1])
print(max([accsum[i] - accsum[i-2*K-1] for i in range(2*K+1, len(accsum), 2)]) if len(accsum) > 2*K+2 else N)

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

t = list(map(int, list(s)))
lt = len(t)
w = []
sumw = []
u = 0
u1 = t[0]
ans1 = []
ans = 0
for i in range(lt):
    if t[i] == u1:
        u += 1
    if t[i] != u1:
        u = u if u1 == 1 else u*-1
        w.append(u)
        ans += abs(u)
        ans1.append(ans if u > 0 else ans*-1)
        u = 1
        u1 = 1 if u1 == 0 else 0

u = u if u1 == 1 else u*-1
w.append(u)
ans += abs(u)
ans1.append(ans if u > 0 else ans*-1)

ans2 = []
for i in range(len(ans1)):
    if i == 0:
        ans2.append(ans1[i])
    elif ans1[i] > 0:
        if i - 2*k - 1 >= 0:
            ans2.append(ans1[i] + ans1[i - 2*k - 1])
        else:
            ans2.append(ans1[i])
    else:
        if i - 2*k >= 0:
            ans2.append(ans1[i]*-1 + ans1[i - 2*k])
        else:
            ans2.append(ans1[i]*-1)

print(abs(max(ans2)))

Solution (Python):

import sys
from itertools import groupby
from itertools import accumulate

def solve(N: int, K: int, S: str):
    group = groupby(S)

    one = []
    zero = []
    for key,value in group:
        if key == "1":
            one.append(len(list(value)))
        else:
            zero.append(len(list(value)))
    
    if len(zero) <= K:
        print(sum(one)+sum(zero))
        return
    
    
    if len(one) == len(zero):
        if S[0] == "1":
            one.append(0)
        else:
            one = [0]+one
    elif len(zero) > len(one):
        one = [0]+one+[0]
    

    accum_zero = [0] + list(accumulate(zero))
    accum_one = [0] + list(accumulate(one))

    answer = 0
    for i in range(len(zero)-K+1):
        total = (accum_one[i+K+1]-accum_one[i]) + accum_zero[i+K]-accum_zero[i]
        answer = max(total,answer)
    
    print(answer)
    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 = list(map(int, input().split()))
s = input()

right = -1
left = -1
now_k = 0
while right + 1 < n and s[right + 1] == '1': 
    right += 1

while now_k < k:
    now_k += 1
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1

ans = (right + 1)
while right + 1 < n:
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
    while left + 1 < n and s[left + 1] == '1':
        left += 1
    while left + 1 < n and s[left + 1] == '0':
        left += 1
    left += 1
    ans = max(ans, right - left + 1)
print(ans)

Solution (Python):
from collections import deque

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

L = deque()

l = 0 
r = 0 
n_zero = 0  
ans = 0

while r < N:
    while r < N and n_zero < K:
        if S[r] == "0": n_zero += 1
        while r < N and S[r] == "0":
            r += 1
        if 0 < r < N and S[r] == "1":
            L.append(r)
        while r < N and S[r] == "1":
            r += 1
    ans = max(ans, r - l)
    if len(L) > 0:
        l = L.popleft()
        n_zero -= 1

print(ans)

Solution (Python):
from collections import deque

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

L = deque()

n_zero = 0  
r = 0 
l = 0

while r < N and n_zero < K:
    if S[r] == "0": n_zero += 1
    while r < N and S[r] == "0":
        r += 1
    if 0 < r < N and S[r] == "1":
        L.append(r)
    while r < N and S[r] == "1":
        r += 1

ans = r

while len(L) > 0 and r < N:
    l = L.popleft()
    while r < N and S[r] == "0":
        r += 1
    if r < N and S[r] == "1":
        L.append(r)
    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()

if S[0] == '0':
    Sc = [0]
else:
    Sc = []

c = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        Sc.append(c)
        c = 1
    else:
        c += 1
Sc.append(c)

if S[-1] == '0':
    Sc.append(0)



ansp = [sum(Sc[:2*K+1])]

for i in range(2*K+1, len(Sc), 2):
    ansp.append(ansp[-1]-Sc[i-2*K-1]-Sc[i-2*K]+Sc[i]+Sc[i+1])
ans = max(ansp)
print(ans)

Solution (Python):
from itertools import accumulate

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

tmp = None
cnt = 0
for s in S:
  if tmp == None:
    cnt += 1
    tmp = s
  else:
    if s == tmp:
      cnt += 1
    else:
      L.append(cnt)
      tmp = s
      cnt = 1
else:
  L.append(cnt)
  L.insert(0,0)

if S[0] == "0":
  L.insert(0,0)

acc = list(accumulate(L))

ans = 0
last = len(acc)

for i in range(0, last, 2):
  right = 2 * K + i + 1
  left = i
  ans = max(ans, acc[min(last-1, right)] - acc[left])

print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']



show_flg = False


def main():
    N, K = MI()
    s = S()
    a = [0]
    first_zero = s[0] == '0'
    cur = s[0]

    for i in range(len(s)):
        if cur == s[i]:
            a[-1] += 1
        else:
            cur = s[i]
            a.append(1)

    
    
    ans = 0
    cur = 0
    right = 0
    for left in range(len(a)):
        if first_zero:
            if left % 2 == 0:
                limit = 2 * K
            else:
                limit = 2 * K + 1
        else:
            if left % 2 == 0:
                limit = 2 * K + 1
            else:
                limit = 2 * K
        

        while right < len(a) and right - left < limit:
            cur += a[right]
            right += 1

        ans = max(cur, ans)
        cur -= a[left]
        

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, K = map(int, input().split())
    S = input()
    lz = []
    lo = []
    o = z = 0
    for i in S:
        if i == '1':
            o += 1
            if z > 0:
                lz.append(z)
                z = 0
        else:
            z += 1
            if o > 0:
                lo.append(o)
                o = 0
    lo.append(o)
    if z > 0:
        lz.append(z)
    if len(lz) <= K:
        return N
    if S[0] == '1':
        lz[0] += lo[0]
        lo = lo[1:]
    lo.append(0)
    m = t = sum(lz[:K]) + sum(lo[:K])
    for i in range(len(lz) - K):
        if i == 0:
            t -= lz[i]
        else:
            t -= (lz[i] + lo[i-1])
        t += (lz[i + K] + lo[i + K])
        m = max(m, t)
    return m
print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    S = input()
    lz = []
    lo = []
    o = 0
    z = 0
    for i in S:
        if i == '1':
            o += 1
            if z > 0:
                lz.append(z)
                z = 0
        if i == '0':
            z += 1
            if o > 0:
                lo.append(o)
                o = 0
    if o > 0:
        lo.append(o)
    if z > 0:
        lz.append(z)
    if len(lz) <= K:
        return N
    if S[0] == '0':
        m = t = sum(lz[:K]) + sum(lo[:K])
        for i in range(len(lz) - K):
            if i == 0:
                t -= lz[i]
            else:
                t -= (lz[i] + lo[i-1])
            if len(lo) == (i + K):
                t += lz[i + K]
            else:
                t += (lz[i + K] + lo[i + K])
            m = max(m, t)
        return m
    if S[0] == '1':
        m = t = sum(lz[:K]) + sum(lo[:K+1])
        for i in range(len(lz) - K):
            t -= (lz[i] + lo[i])
            if len(lo) == (i + K + 1):
                t += lz[i + K]
            else:
                t += (lz[i + K] + lo[i + K + 1])
            m = max(m, t)
        return m
print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    S = input()
    class LL:
        def __init__(self, v, p, n):
            self.v = v
            self.p = p
            self.n = n
    T = []
    m = 0
    for s in S:
        if s == '0':
            if m >= 0:
                T.append(m)
                m = 0
            m -= 1
        else:
            if m < 0:
                T.append(-m)
                m = 0
            m += 1
    T.append(abs(m))
    if m < 0:
        T.append(0)
    m = t = sum(T[:K * 2 + 1])
    L = K * 2 + 1
    for i in range(0, len(T) - L, 2):
        t = t + T[L + i] + T[L + i + 1] - T[i] - T[i + 1]
        m = max(m, t)
    print(m)
main()