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 = list(map(int, input().split()))
S = input()

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

for i in range(N):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == N-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)
lk = int((len(D)-1)/2)
if K > lk:
    K = lk
ans = sum(D[:(2*K+1)])
sumd = ans
for i in range(int((len(D)-2*K-1)/2)):
    sumd += D[2*K+2*i+1]+D[2*K+2*i+2]-D[2*i]-D[2*i+1]
    if sumd > ans:
        ans = sumd

print(ans)

Solution (Python):
N , K = map(int,input().split())
S = input()
L = []
flag = int(S[0])
for x in S:
    L.append(x)
cnt = 1
C = []
for i in range(len(L)):
    try:
        if L[i] == L[i+1]:
            cnt += 1
        else:
            C.append(cnt)
            cnt = 1
    except:
        pass
C.append(cnt)
ans = 0
from itertools import accumulate
accumulated =  [0]+list(accumulate(C))
ans = 0
A = 0
if flag == 0:
    if len(C) % 2 == 0:
        k = min(K,len(C)//2)
    else:
        k = min(K,len(C)//2+1)
else:
    k = min(K,len(C)//2)
for i in range(len(C)):
    try:
        if (flag + i) % 2 == 0:
            A =max(A, accumulated[i+2*k-1] - accumulated[i])
            ans = accumulated[i+2*k] - accumulated[i]
        else:
            A =max(A, accumulated[i+2*k-1] - accumulated[i])
            A =max(A, accumulated[i+2*k] - accumulated[i])
            ans = accumulated[i+2*k+1] - accumulated[i]
        A = max(ans,A)
    except:
        pass
print(A)

Solution (Python):
N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[now]
        cnt=1

if cnt!=0:
    nums.append(cnt)

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

Add=2*K+1
ans=0

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

for i in range(0,len(nums),2):
    
    left=i
    right=min(i+Add,len(nums))

    tmp=sum[right]-sum[left]
    ans=max(ans,tmp)

print(ans)

Solution (Python):
N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[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):
    
    nextleft=i
    nextright=min(i+Add,len(nums))
    while nextleft>left:
        tmp=tmp-nums[left]
        left+=1

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

    ans=max(ans,tmp)

print(ans)

Solution (Python):
N,K = map(int,input().split())
s = list(map(int,input()))
s.append(2)
start = s[0]
number = 1
choku = []
saka = [0]
for i in range(N):
    if s[i] == s[i+1]:
        number += 1
    else:
        if s[i] == 0:
            choku.append(number)
            number = 1
        else:
            saka.append(number)
            number = 1
choku.append(0)
saka.append(0)
while(1):
    max_align = 0
    m = len(choku)
    n = len(saka)
    if m <= K:
        print(N)
        break
    if start == 0: 
        aligns = [sum(choku[0:K]) + sum(saka[0:K+1])]
        for i in range(m-K-1):
            aligns.append(aligns[i] -choku[i]-saka[i] + choku[i+K] + saka[i+K+1])
        print(max(aligns))
    else:
        aligns = [sum(choku[0:K]) + sum(saka[1:K+2])]
        for i in range(m-K-1):
            aligns.append(aligns[i] -choku[i]-saka[i+1] + choku[i+K] + saka[i+K+2])
        print(max(aligns))
    break

Solution (Python):
n,k = list(map(int, input().split()))
s = input()
if (s.find('0') < 0) or (s.find('1') < 0):
	print(len(s))
	quit()
else:
	s += '0' if s[n-1] == '1' else '1'
c = []

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

for i in range(1, len(c)):
	c[i][1] += c[i-1][1]

if 2*k >= len(c):
	print(c[-1][1])
	quit()
else:
	p = 0
	res = 0
	if c[0][0] == '0':
		res = c[1][1] if k == 1 else c[2*k-1][1]
		p += 1
	else:
		res = c[2][1] if k == 1 else c[2*k][1]
		p += 2

	while p+2*k < len(c):
		res = max(res, c[p+2*k][1] - c[p-1][1])
		p += 2

	res = max(res, c[-1][1] - c[(len(c)-1) - 2*k][1]) if c[-1][0] == '0' else max(res, c[-1][1] - c[(len(c)-1) - (2*k+1)][1])

	print(res)
	quit()

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

hm_1 = [0] * N
hm_2 = [0] * N

for i in range(N-1,-1,-1):
	if i == N-1:
		if S[i] == '1':
			hm_1[i] = 1
	else:
		if S[i] == '0':
			hm_1[i] = 0
		else:
			hm_1[i] = hm_1[i+1] + 1
		
for i in range(N-1,-1,-1):
	if i == N-1:
		if S[i] == '0':
			hm_2[i] = 1
	else:
		if S[i] == '1':
			hm_2[i] = 0
		else:
			hm_2[i] = hm_2[i+1] + 1




rl = []


i = 0
if hm_1[i] == 0:
	rl.append(0)
while i < N :
	if hm_1[i] != 0:
		rl.append(hm_1[i])
		i += hm_1[i]
	else:
		rl.append(hm_2[i])
		i += hm_2[i]





s = [0] * (len(rl) + 1)


for j in range(len(rl)):
	s[j+1] = s[j] + rl[j]


ans = 0
for ra in range(0,len(s),2):
	tmp = 0
	right = min(ra + 2 * K + 1, len(s)-1)
	tmp = s[right] - s[ra]
	ans = max(tmp,ans)

print (ans)

Solution (Python):
n, k = [int(i) for i in input().split()]
s = [0,1] + [int(i) for i in list(input())] + [1,0]
down = [i for i in range(n+3) if s[i] == 1 and s[i+1] == 0]
up = [i for i in range(n+3) if s[i] == 0 and s[i+1] == 1]



ans = 1
if k >= len(up):
  ans = n
else:
  if down[k] - up[0] - 1 > ans:
    ans = down[k] - up[0] - 1
  for i in range(1,len(up)-k-1):
    if down[i + k] - up[i] > ans:
      ans = down[i + k] - up[i]
  if down[len(up)-1] - up[len(up)-k -1] - 1 > ans:
    ans = down[len(up)-1] - up[len(up)-k -1] - 1
print(ans)

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

l = []
if s[0] == "0":
    l.append(0)
one = []
cnt_0 = 0
cnt_1 = 0

for i in s:
    if i == '0':
        if cnt_1 != 0:
            l.append(cnt_1)
            one.append((cnt_1))
            cnt_1 = 0
        cnt_0 += 1
    if i =='1':
        if cnt_0 != 0:
            l.append(cnt_0)
            cnt_0 = 0
        cnt_1 += 1

if cnt_1 != 0:
    l.append(cnt_1)
    one.append(cnt_1)
if cnt_0 != 0:
    l.append(cnt_0)
    l.append(0)


ans = 0
Sum = [0]
for i in range(len(l)):
    Sum.append(l[i]+Sum[i])


for i in range(1,len(Sum),2):
    left = i-1
    if i+k*2 > len(Sum)-1:
        right = len(Sum)-1
    else:
        right = i+k*2
    
    temp = Sum[right] - Sum[left]
    if ans < temp:
        ans = temp
print(ans)

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

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

l = p[0::2] + [0, 0]
r = p[1::2]

counter = sum(r[:k]) + sum(l[:k+1])
imax = counter
for i in range(k, len(r)):
    counter += l[i+1] + r[i]
    counter -= l[i-k] + r[i-k]
    if counter > imax:
        imax = counter

print(imax)

Solution (Python):
N,K = map(int,input().split())
S = list(map(int,input()))
tmp = 1
nums = []
cont = 0
for s in S:
    if int(s) == tmp:
        cont += 1
    else:
        nums.append(cont)
        cont = 1
        tmp = 1 - tmp
if cont != 0:
    nums.append(cont)
if len(nums) % 2 == 0:
    nums.append(0)
cml = [0]
for n in nums:
    cml.append(cml[-1]+n)
ans = []
for i in range(0,len(cml),2):
    ans.append(cml[min(len(cml)-1,i+K*2+1)]-cml[i])
print(max(ans))

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

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

seq.append(tmp+1)

seq_sum = [0 for _ in range(len(seq)+1)]

for i in range(len(seq)):
    seq_sum[i+1] = seq_sum[i] + seq[i]

res = -1
if S[0] == '0':
    for i in range(len(seq_sum)):
        if i%2 == 0:
            r = min(i + 2*K, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i]) 
        else:
            r = min(i + 2*K+1, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i])
        
else:
    for i in range(len(seq_sum)):
        if i%2 == 0:
            r = min(i + 2*K+1, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i])
        else:
            r = min(i + 2*K, len(seq_sum)-1)
            res = max(res, seq_sum[r] - seq_sum[i]) 

            
print(res)

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

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

if S2[0][0] == 0:
    S2 = [[1,0]] + S2
if S2[-1][0] == 0:
    S2.append([1,0])    
    
SUM = [0]
for i in range(len(S2)):
    SUM.append(SUM[i] + S2[i][1])
T = []
for i in range(0,max(1,len(SUM)//2-K),1):
    T.append(SUM[min(len(SUM)-1,2*(K+i)+1)]-SUM[2*i])
print(max(T))

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

if s[0]=='1':
    l = [1]
else:
    l = [0,1]

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

prev = sum(l[0:2*k+1])
ans = prev
for i in range(len(l)//2+1):
    prev = prev-sum(l[2*i:2*i+2]) + sum(l[2*i+2*k+1:2*i+2*k+3])
    ans = max(ans, prev)

print(ans)

Solution (Python):
n,k = map(int,input().split())
s = list(input())
a = []
switch = 0
tmp = 0
for i in range(n):
    if switch == 0:
        if s[i] == "1":
            tmp += 1
        else:
            a.append(tmp)
            tmp = 1
            switch = 1
    else:
        if s[i] == "0":
            tmp += 1
        else:
            a.append(tmp)
            tmp = 1
            switch = 0
a.append(tmp)

tmp = 0
if k*2 <= len(a):
    tmp = k
else:
    if len(a)%2 == 0:
        tmp = int(len(a)/2)
    else:
        tmp = len(a)//2 


ans = sum(a[0:tmp*2+1])
tmpans = sum(a[0:tmp*2+1])
i = 2
while i+tmp*2<=len(a):
    tmpans -= a[i-2]+a[i-1]
    if i+tmp*2 == len(a):
        tmpans += a[i+tmp*2-1]
    else:
        tmpans += a[i+tmp*2-1]+a[i+tmp*2] 
    ans = max(ans,tmpans)
    i+=2
print(ans)

Solution (Python):
n, k = map(int, input().split())
s = input()
if set(list(s)) == 1:
    print(n)
    exit

s = '0' + s + '0'
list_ones = []
for i in range(1, n+1):
    if s[i-1] == '0' and s[i] == '1':
        i_start = i
    if s[i] == '1' and s[i+1] == '0':
        i_end = i
        list_ones.append((i_start, i_end))
list_ones = [(1, 1)] + list_ones + [(n, n)]


ans = 0
for j, (i_start, _) in enumerate(list_ones):
    j_end = min(len(list_ones)-1, j+k)
    _, i_end = list_ones[j_end]
    ans = max(ans, i_end-i_start+1)
print(ans)

Solution (Python):
n,k = map(int,input().split())
if(n == 1):
    print("1")
    exit()
s = input()
zero = []
one = []
sp = [-1]
for i in range(len(s)-1):
    if(s[i] != s[i+1]):
        sp.append(i)
sp.append(len(s)-1)
spp =[]
if(s[0] == "0"):spp.append(0)
for i in range(1,len(sp)):
    spp.append(sp[i]-sp[i-1])

if(s[-1] == "0"):spp.append(0)

if((len(spp)-1)//2 <= k): 
    print(n)
    exit()

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

print(ans)

Solution (Python):


import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def grouping(N, S):
    group = []
    s = S[0]
    c = 1
    for i in range(1, N):
        if S[i] == s:
            c += 1
        else:
            group.append((s, c))
            s = S[i]
            c = 1
    group.append((s, c))
    return group

def main(N, K, S):
    g = grouping(N, S)
    glen = len(g)
    
    cs = [0] * (glen + 1)
    for i in range(glen):
        cs[i+1] = cs[i] + g[i][1]
    nm = 0
    for i in range(glen):
        if g[i][0] == '0':
            n = cs[min(i + 2*K, glen)] - cs[i]
        else:
            n = cs[min(i + 2*K+1, glen)] - cs[i]
        if n > nm:
            nm = n
    print(nm)

N, K = i2nn()
S = i2s()
main(N, K, S)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator



inf = float('inf')
N, K = 0, 0
S = ""
M = 300000


def set_inputs():
    global N, K, S
    N, K = get_li()
    S = get_str()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    cont = []
    cur = S[0]
    count = 1
    for s in S[1:]:
        if cur == s:
            count += 1
        else:
            cont.append(count)
            cur = s
            count = 1
    cont.append(count)
    
    lc = len(cont)
    if lc == 1:
        print(len(S))
        return
    cont = cont + ([0] * M)
    if S[0] == "0":
        cont = [0] + cont
    ans = 0
    tmp = sum(cont[:2*K+1])
    ans = tmp
    i = 2
    while i < lc + 1:
        tmp = tmp - cont[i-2] - cont[i-1] + cont[i+2*K-1] + cont[i+2*K]
        ans = max(ans, tmp)
        i += 2
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


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


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator



inf = float('inf')
N, K = 0, 0
S = ""
M = 300000


def set_inputs():
    global N, K, S
    N, K = get_li()
    S = get_str()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    cont = []
    cur = S[0]
    count = 1
    for s in S[1:]:
        if cur == s:
            count += 1
        else:
            cont.append((count, cur == "1"))
            cur = s
            count = 1
    cont.append((count, cur == "1"))
    
    lc = len(cont)
    if lc == 1:
        print(len(S))
        return
    cont = cont + ([(0, None)] * M)
    if cont[0][1] == False:
        cont = [(0, None)] + cont
    ans = 0
    tmp = sum(map(operator.itemgetter(0), cont[:2*K+1]))
    ans = tmp
    i = 2
    while i < lc + 1:
        tmp = tmp - cont[i-2][0] - cont[i-1][0] + cont[i+2*K-1][0] + cont[i+2*K][0]
        ans = max(ans, tmp)
        i += 2
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


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


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
k = int(input().split(" ")[1])
s = input()

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

sums = [0]
for i in range(len(arr)):
  sums.append(sums[i] + arr[i])
t = 2*k+1
m = 0
for i in range(0,len(arr),2):
  m = max(m,sums[min(len(sums)-1,i+t)]-sums[i])
print(m)

Solution (Python):
l = input().split(" ")
n = int(l[0])
k = int(l[1])
s = input()

nums = []
now = 1
count = 0

for i in range(n):
    if s[i] == str(now):
        count = count + 1
    else:
        nums.append(count)
        now = 1 - now
        count = 1

if count != 0:
    nums.append(count)


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

add = 2 * k + 1

sums = list((0, ))
for i in range(len(nums)):
    sums.append(sums[i] + nums[i])

ans = 0

for i in range(len(nums))[::2]:
    left = i
    right = min(i + add, len(nums))
    tmp = sums[right] - sums[left]

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

Solution (Python):
N, K = map(int, input().split())
S = input()
A = []
if S[0] == '0':
  A.append(0)
i = 0
while i < len(S):
  j = i
  while j < len(S) and S[i] == S[j]:
    j += 1
  A.append(j - i)
  i = j
ans = 0
tot = 0
r = 0
for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if r == l:
    r += 1
  else:
    tot -= A[l]
print(ans)

Solution (Python):
n,k=map(int,input().split())
s=list(map(int,input()))
sp_list=[]
sum=0
sum_0=0
for i in range(n):
  if s[i]==1:
    sum+=1
    if sum_0>0:
      sp_list.append(sum_0)
    sum_0=0
    if i==(n-1):
      sp_list.append(sum)
  else:
    if i==0:
      sp_list.append(0)
    if i>0 and sum>0:
      sp_list.append(sum)
    sum_0+=1
    sum=0
    if i==(n-1):
      sp_list.append(sum_0)
      sp_list.append(0)
sum_list=[0]
sum=0
for i in range(len(sp_list)):
  sum+=sp_list[i]
  sum_list.append(sum)
length=min(k,len(sum_list))
if 2*k+1>=len(sum_list):
  print(sum_list[-1])
else:
  temp=0
  for i in range((len(sum_list)-2*k)//2):
    if temp<(sum_list[2*i+2*k+1]-sum_list[2*i]):
      temp=(sum_list[2*i+2*k+1]-sum_list[i*2])
  print(temp)

Solution (Python):
import sys
def main():
  if 'get_ipython' not in globals():  
    
    N,K = map(int, input().split())
    S = sys.stdin.readline()
  else:
    
    
    
    
    
    
    
    
    
    
    N = 5
    K = 1
    S = "11111"
    
  SC = []
  i = 0
  if S[0] == "0":SC.append(0)
  while i < N :
    if S[i] == "0":
      j = S.find("1",i)
    else:
      j = S.find("0",i)
    if j == -1: j = N 
    cnt = j - i
    i = j
    SC.append(cnt)
    
  if 'get_ipython' in globals(): print(SC)
    
  SH = []
  cnt = 0
  for i in range(len(SC)):
    cnt += SC[i]
    SH.append(cnt)
  
  if 'get_ipython' in globals(): print(SH)
  
  lenSC = len(SC) - 1
  ans = 0
  for i in range(0,lenSC+1,2):
    k = i + K * 2
    if k > lenSC:
      k = lenSC
    if i != 0:
      cnt = SH[k] - SH[i-1]
    elif k == i:
      cnt = SH[k]
    else:
      cnt = SH[k] - SH[i]
    if ans < cnt: ans = cnt

  print(ans)

main()

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

A = []
if S[0] == '0':
  A.append(0)

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

ans = 0
tot = 0
r = 0

for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if l == r:
    r += 1
  else:
    tot -= A[l]

print(ans)

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

A = []
if S[0] == '0':
  A.append(0)

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

ans = 0
tot = 0
r = 0

for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if l == r:
    r += 1
  else:
    tot -= A[l]

print(ans)

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

l = [0]

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

t = len(l)

for x in range(0,2*k+1):
    l.append(n)



can = []

for j in range(0,t):
    if s[l[j]] == 0:
        can.append(l[j+2*k]-l[j])
    elif s[l[j]] == 1:
        can.append(l[j+2*k+1]-l[j])
    else:
        break


print(max(can))

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(input())

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

if S[0]>=0:
    if len(S)<=(2*K+1):
        ans=0
        for i in range(len(S)):
            ans+=abs(S[i])
        print(ans)
        
    else:
        ans=0
        SUM=0
        for i in range(2*K+1):
            SUM+=abs(S[i])
            ans=SUM
        
        for i in range(1,len(S)):
            if (2*i+2*K)>(len(S)-1):
                
                break
            else:
                
                SUM=SUM+abs(S[2*i+2*K-1])+abs(S[2*i+2*K])-abs(S[2*i-1])-abs(S[2*i-2])
                if SUM>ans:
                    ans=SUM
        print(ans)

Solution (Python):
import numpy as np

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

nums = np.array([len(s) for s in S.replace('10', '1,0').replace('01', '0,1').split(',')])

if S[0] == '0':
    nums = np.insert(nums, 0, 0)

if len(nums) % 2 == 0:
    nums = np.insert(nums, len(nums), 0)

csm = np.insert(nums.cumsum(), 0, 0)

res = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(2*K+1 + i, len(nums))
    res = max(res, csm[right] - csm[left])
print(res)

Solution (Python):
lftIdx, rgtIdx, ans = 0, 0, 0
lftFlg, rgtFlg = False, False
n, k = map(int, input().split())
s = input()


def move(lr, idx, flg):
    
    
    global s
    if flg and idx < n-1:
        idx += 1
    contains_zero = False
    while True:
        if idx == n-1:
            return idx
        if s[idx] == "0":
            contains_zero = True
        if contains_zero and s[idx] != s[idx+1] and s[idx+1] == lr:
            return idx
        idx += 1


def solv():
    global lftIdx, rgtIdx, ans, lftFlg, rgtFlg, n, k, s
    for i in range(k):
        rgtIdx = move("0", rgtIdx, rgtFlg)
        rgtFlg = True
    ans = max(ans, rgtIdx + 1)
    while n-1 > rgtIdx:
        rgtIdx = move("0", rgtIdx, rgtFlg)
        lftIdx = move("1", lftIdx, lftFlg)
        lftFlg = True
        ans = max(ans, rgtIdx - lftIdx)  
    return


solv()
print(ans)

Solution (Python):
def shaktori(n, tmp=0, l_s=0, r_s=0, l=0, r=0):
    while l_s > l:
        tmp -= n[l]
        l += 1
    while r_s > r:
        tmp += n[r] 
        r += 1 
    return (tmp, l, r)

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

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


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

s = 2 * K + 1
a = 0
tmp = 0
l, r = 0, 0
for i in range(0, len(n), 2):
    l_s = i 
    r_s = min(i + s, len(n))
    tmp, l, r = shaktori(n, tmp, l_s, r_s, l, r)

    a = max(a, tmp)

print(a)

Solution (Python):
n, k = map(int, input().split(' '))
s = input()
if k >= n:
  print(n)
  exit()
  
s10 = []
cnt = 0
s_prev = '1'
for si in s+'x':
  if si == s_prev:
    cnt += 1
  else:
    s10.append(cnt)
    cnt = 1
  s_prev = si
if s[-1] == '0':
  s10.append(0)
if len(s10) < 2*k + 1:
  print(n)
  exit()

sum_i = sum(s10[:2*k+1])
sum_max= sum_i

for i in range(len(s10)//2-k):
  sum_i += (s10[2*i + 2*k + 1] + s10[2*i + 2*k + 2] - s10[2*i] - s10[2*i+1])
  sum_max = max(sum_i, sum_max)
  
print(sum_max)

Solution (Python):
from itertools import accumulate

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

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

serial_cumsum = [0]+list(accumulate(serial))
ans = 0
for l in range(0, len(serial_cumsum), 2):
    r = min(len(serial_cumsum) - 1, l + 2*K + 1)
    temp = serial_cumsum[r] - serial_cumsum[l]
    if ans < temp:
        ans = temp
print(ans)

Solution (Python):
n,k = map(int,input().split())
s = list(input())
if s[0] == "1":
    cnt_list = []
else:
    cnt_list = [0]
cnt = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        cnt_list.append(cnt)
        cnt = 1
cnt_list.append(cnt)
if s[-1] == '0':
    cnt_list.append(0)

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

Solution (Python):


from itertools import accumulate


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

    
    
    
    s = s.replace('01', '0,1').replace('10', '1,0')
    len_list = [len(string) for string in s.split(',')]
    if s[0] == '0':
        len_list = [0] + len_list
    if s[-1] == '0':
        len_list = len_list + [0]

    if 2 * k + 1 >= len(len_list):
        print(n)
        return

    sum_list = [0] + list(accumulate(len_list))
    max_len = 0
    for i in range(0, len(len_list) - (2 * k + 1) + 1, 2):
        handstand_len = sum_list[i + (2 * k + 1)] - sum_list[i]
        if max_len < handstand_len:
            max_len = handstand_len
    print(max_len)


if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == '__main__':
	N,K = map(int, input().split())
	S = input()
	nums = []
	if(S[0]=='0') : 
		nums.append(0)
	i=0
	while i < N:
		j = i
		while j<N and S[j]==S[i] :
			j+=1
		nums.append(j-i)
		i=j


	if(S[N-1]=='0') :
		nums.append(0)
	
	sums=[0] * (len(nums)+1)
	for i in range(len(nums)):
		sums[i+1] = sums[i] + nums[i]

	window_size = 2*K + 1
	ans=0
	l = 0
	while l < len(sums):
		r = l + window_size
		if(r>=len(sums)):
			r = len(sums)-1
		ans = max(ans,sums[r] - sums[l])
		l+=2

	print(ans)

Solution (Python):
import sys

N, K = map(int, input().split())
s = input() + "

pre, cons, comp = '
for i in range(len(s)):
    if pre != '
        if cons > 0:
            print(cons, s[i-1], file=sys.stderr)
            comp.append((cons, s[i-1]))
            cons = 1
    else:
        cons += 1

    pre = s[i]

acc = [0 for _ in range(len(comp))]
for i in range(1, len(comp)):
    acc[i] = acc[i-1] + comp[i][0]

ans = 0
for i in range(len(comp) - 1):
    lim = len(comp) - 1
    if comp[i+1][1] == '1':
        lim = min(lim, i + 2*K + 1)
    else:
        lim = min(lim, i + 2*K)
    print("i = {}, lim = {}".format(i, lim), file=sys.stderr)
    ans = max(ans, acc[lim] - acc[i])

print(ans)

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

pre, cons, comp = '
for i in range(len(s)):
    if pre != '
        if cons > 0:
            
            comp.append((cons, s[i-1]))
            cons = 1
    else:
        cons += 1

    pre = s[i]

acc = [0 for _ in range(len(comp))]
for i in range(1, len(comp)):
    acc[i] = acc[i-1] + comp[i][0]

ans = 0
for i in range(len(comp) - 1):
    lim = len(comp) - 1
    if comp[i+1][1] == '1':
        lim = min(lim, i + 2*K + 1)
    else:
        lim = min(lim, i + 2*K)
    
    ans = max(ans, acc[lim] - acc[i])

print(ans)

Solution (Python):
N,K=map(int,input().split())
S=input()
nums=[]
if S[0]=="0":
    nums.append(0)
i=0
while(i<len(S)):
    j=i
    while(j<len(S) and S[j]==S[i]):
        j+=1
    nums.append(j-i)
    i=j
if S[-1]=="0":
    nums.append(0)
sums=[0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1]=sums[i]+nums[i]
res=0
for left in range(0,len(sums),2):
    right=left+K*2+1
    if right>=len(sums):
        right=len(sums)-1
    res=max(res,sums[right]-sums[left])
print(res)

Solution (Python):


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


i=[0]
for j in range(1,len(S)):
    if S[j]!=S[j-1]:
        i.append(j)





X=[]
for m in range(len(i)):
    if S[i[m]]=='1':
        
        if 2*K+1+m >= len(i):
            X.append(N-i[m])
        else:
            X.append(i[2*K+1+m]-i[m])

    elif S[i[m]]=='0':
        
        if 2*K+m >= len(i):
            X.append(N-i[m])
        else:
            X.append(i[2*K+m]-i[m])

print(max(X))

Solution (Python):


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

Sl = [0] + [i for i in range(N + 1) if S[i:(i + 2)] == "01"] + [N]
Sr = [0] + [i for i in range(N + 1) if S[i:(i + 2)] == "10"] + [N]

if len(Sl) - K >= 1:
    print(max([Sr[i + K] - Sl[i] for i in range(len(Sl) - K)]))
else:
    print(N)

Solution (Python):
n,k = map(int,input().split())
s = input()
befores = '1'
cnt = 0
snum = []
for S in s:
	if S == befores:
		cnt += 1
	else:
		snum.append(cnt)
		cnt = 1
		befores = S
snum.append(cnt)
if s[-1] == '0':
    snum.append(0)
kazu = sum(snum[0:k * 2  + 1])
kaisuu = sum(snum[0:k * 2  + 1])
time = int((len(snum) - k * 2 - 1) / 2 )
one = 0
zero = 1
k = k * 2
for i in range(time):
	kazu = kazu - snum[one] - snum[zero] + snum[one + k + 2] + snum[zero + k]
	kaisuu = max(kaisuu,kazu)
	one += 2
	zero += 2
print(kaisuu)

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

now = 1
cnt = 0
x = []

for i in range(n):
    if sss[i] == str(now):
        cnt += 1
    else:
        x.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    x.append(cnt)
if sss[-1] == 0:
    x.append(0)

Add = 2 * k + 1
ans = 0

y = [0]
for i in range(len(x)):
    y.append(y[i] + x[i])

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

print(ans)