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 groupby, accumulate
N, K = map(int, input().split())
S = input()
g_cnt = [len(list(v)) for k, v in groupby(S)]
ans = 1

if S[0]=="0":
    g_cnt = [0] + g_cnt
if S[-1]=="0":
    g_cnt = g_cnt + [0]
    
accum = [0] + list(accumulate(g_cnt))
ans = 0
for i in range(0, len(accum), 2):
    r = i+2*K+1
    if r>=len(accum):
        r = len(accum)-1
    ans = max(ans , accum[r]-accum[i])
print(ans)

Solution (Python):


n,k=map(int,input().split())
s=list(input())+[None]

cnt=1
ss=[]
if s[0]=='0':ss.append(0)

i=1
while i<=n:
    if s[i]==s[i-1]:
        cnt+=1
    else:
        ss.append(cnt)
        cnt=1
        
    i+=1

if s[-2]=='0':ss.append(0)
nn=len(ss)
k=min(nn//2,k)
res=sum(ss[:k*2+1])
cnt=res
l=0
for r in range(k*2+2,nn,2):
    cnt-=(ss[l]+ss[l+1])
    cnt+=(ss[r]+ss[r-1])
    res=max(res,cnt)
    l+=2

print(res)

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

L = S.replace('01', '0,1')
L = L.replace('10', '1,0')
L = L.split(',')
L = [len(l) for l in L]

if S[0] == '0':
    L = [0] + L

R = []
for i in range(max(1, len(L) // 2 + 1 - K)):
    if i == 0:
        R.append(sum(L[2*i:2*(i+K)+1]))
    else:
        R.append(R[-1] - sum(L[2*(i-1):2*(i-1)+2]) + sum(L[2*(i+K)-1:2*(i+K)+1]))

print(max(R))

Solution (Python):

from sys import exit

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

p = '1'
count = 0
cs = []
for c in S:
    if c != p:
        cs.append(count)
        p = c
        count = 1
    else:
        count += 1
cs.append(count)
if p != '1':
    cs.append(0)

if len(cs) < 2 * K:
    print(N)
    exit()

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

result = cs[2 * K]
for i in range(2, len(cs) - 2 * K, 2):
    if cs[2 * K + i] - cs[i - 1] > result:
        result = cs[2 * K + i] - cs[i - 1]
print(result)

Solution (Python):

from sys import exit

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

p = '1'
count = 0
cs = []
for c in S:
  if c != p:
    cs.append(count)
    p = c
    count = 1
  else:
    count += 1
cs.append(count)
if p == '0':
  cs.append(0)

if len(cs) < 2 * K:
  print(N)
  exit()

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

result = cs[2 * K]
for i in range(2, len(cs) - 2 * K, 2):
  t = cs[2 * K + i] - cs[i - 1]
  if t > result:
    result = t
print(result)

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

a = []

now = S[0]
cnt = 1
for x in S[1:]:
    if x == now:
        cnt += 1
    else:
        a.append(cnt)
        now = x
        cnt = 1
a.append(cnt)


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



m = len(a)

if 2 * K + 1 >= m:
    maxsum = N
else:
    l = 0
    r = 2 * K + 1
    nowsum = sum(a[l : r])
    maxsum = nowsum
    while True:
        l += 2
        r += 2
        if r > m:
            break
        nowsum += a[r - 2] + a[r - 1] - (a[l - 2] + a[l - 1])
        maxsum = max(maxsum , nowsum)

print(maxsum)

Solution (Python):
def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

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

hoge = N*3 + 3

imos = [0]*(hoge)
imosInd = 2
cnt = 1
ind = 1
while ind < N:
    if S[ind] == S[ind-1]:
        cnt += 1
    else:
        imos[imosInd] = cnt
        cnt = 1
        imosInd += 1

    ind += 1
imos[imosInd] = cnt

for i in range(2, hoge):
    imos[i] += imos[i-1]


if S[0] == '1':
    ind = 2
else:
    ind = 1

ans = 0

while ind + K*2 < hoge:
    ans = max(ans, imos[ind + K*2] - imos[ind-1])
    ind += 2

print(ans)

Solution (Python):









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

now=S[0]
cnt=1
for c in S[1:]:
    if c==now:
        cnt+=1
    else:
        a.append(cnt)
        now=c
        cnt=1
a.append(cnt)

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



m=len(a) 



if 2*K+1>=m:
    ans=N
else:
    l=0;r=2*K+1
    nowsum=sum(a[l:r])
    
    maxsum=nowsum
    while True:
        l+=2;r+=2
        if r>m:
            break
        nowsum=nowsum-a[l-2]-a[l-1]+a[r-2]+a[r-1]  
        maxsum=max(maxsum,nowsum)
        
    ans=maxsum
print(ans)

Solution (Python):
N,K = map(int,input().split())
S = list(map(int,input()))
num = 1
T = []
if S[0] == 0:
    T.append(0)
for i in range(1,N):
    if S[i-1] != S[i]:
        T.append(num)
        num = 0
    num += 1
T.append(num)
if S[N-1] == 0:
    T.append(0)

if K >= len(T)//2:
    print(N)
else:
    x = sum(T[0:2*K+1])
    ans = x
    for i in range(1,(len(T)//2)-K+1):
        x = x-(T[2*i-2]+T[2*i-1])+(T[2*i+2*K-1]+T[2*i+2*K])
        ans = max(ans,x)
    print(ans)

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

if S[0] == "1" :
    ans = sum(A[:2*K+1])
    calc = ans
    for i in range(2*K+1, len(A)) :
        calc += A[i]
        if i % 2 == 1 :
            calc -= (A[i-1-2*K] + A[i-2*K])
        ans = max(ans, calc)
else :
    ans = sum(A[:2*K])
    calc = ans
    for i in range(2*K,len(A)) :
        calc += A[i]
        if i == 2*K :
            calc -= A[0]
        elif i % 2 == 0  :
            calc -= (A[i-1-2*K] + A[i-2*K])
        ans = max(ans, calc)

print(ans)

Solution (Python):
import itertools

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

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

    B = list(itertools.accumulate([0] + A))
    ans = 0
    if S[0] == '1':
        for i in range(1,len(B)+1,2):
            right = i + 2 * K
            if right >= len(B):
                right = len(B) - 1
            tmp = B[right]-B[i-1]
            ans = max(ans, B[right]-B[i-1])
    if S[0] == '0':
        C = [0] + B
        for i in range(1,len(C)+1,2):
            right = i + 2 * K
            if right >= len(C):
                right = len(C) - 1
            tmp = C[right]-C[i-1]
            ans = max(ans, C[right]-C[i-1])

    print(ans)

    
main()

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

L0 = []
L1 = []
temp = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == "0":
        if temp == "0":
            cnt += 1
        else:
            L1.append(cnt)
            temp = "0"
            cnt = 1
    else:
        if temp == "1":
            cnt += 1
        else:
            L0.append(cnt)
            temp = "1"
            cnt = 1
if S[-1] == "0":
    L0.append(cnt)
else:
    L1.append(cnt)

ans = 0
if S[0] == "0":
    if K >= len(L0):
        ans += N
    else:
        for i in range(K):
            ans += L0[i]+L1[i]
        i = K
        temp = ans
        while i < len(L0):
            if i-K == 0:
                temp -= L0[i-K]
            else:
                temp -= L0[i-K]+L1[i-K-1]
            if i == len(L1):
                temp += L0[i]
            else:
                temp += L0[i]+L1[i]
            if ans < temp:
                ans = temp
            i += 1
else:
    if K >= len(L0):
        ans += N
    else:
        for i in range(K):
            ans += L0[i]+L1[i]
        ans += L1[K]
        i = K
        temp = ans
        while i < len(L0):
            temp -= L0[i-K]+L1[i-K]
            if S[-1] == "0" and i == len(L1)-1:
                temp += L0[i]
            else:
                temp += L0[i]+L1[i+1]
            if ans < temp:
                ans = temp
            i += 1
            
print(ans)

Solution (Python):

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

j = 1
r = 0
t = []
for i in range(N):
    if S[i] == j:
        r += 1
    else:
        t.append(r)
        r = 1
        j ^= 1
t.append(r)
if j == 0:
    t.append(0)

if K >= (len(t) - 1) // 2:
    print(sum(t))
else:
    result = sum(t[:2 * K + 1])
    j = result
    i = 2
    while i + 2 * K < len(t):
        j += t[i + 2 * K - 1] + t[i + 2 * K] - (t[i - 2] + t[i - 1])
        result = max(result, j)
        i += 2
    print(result)

Solution (Python):
n,k = map(int,input().split())
s = list(map(int,input()))
s_list = list()
num = s[0]
temp_streak = 0


[s_list.append(0) for i in range(1+s[0])]

for i in s:
    if i == num:
        temp_streak += 1
    else:
        s_list.append(temp_streak)
        temp_streak = 1
        num = i

s_list.append(temp_streak)
[s_list.append(0) for i in range(1+s[-1])]

num_i = len(s_list) // 2 

temp_max = sum(s_list[0:min(k*2+1,len(s_list) + 1)])
temp_sum = temp_max
temp_max_debug = temp_max

for i in range(1,max(num_i+1-k,1)):
    temp_sum = temp_sum - s_list[i*2-2] - s_list[i*2-1] + s_list[i*2+k*2-1] + s_list[i*2+k*2]
    temp_max = max(temp_max,temp_sum)
    
print(temp_max)

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

if S.count('1') == N or S.count('0') == N:
  print(N)
  exit()

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



if len(L0) <= K:
  print(N)
  exit()

SL0 = [0 for _ in range(len(L0)+1)]
for i in range(1,len(L0)+1):
  SL0[i] = SL0[i-1] + L0[i-1]
SL1 = [0 for _ in range(len(L1)+1)]
for i in range(1,len(L1)+1):
  SL1[i] = SL1[i-1] + L1[i-1]

ans = 0
for i in range(len(L0)-K+1):
    
    ans = max(ans,SL0[i+K]-SL0[i] + SL1[i+K+1]-SL1[i])
print(ans)

Solution (Python):

import sys


def solve(N: int, K: int, S: str):
    seq = []
    if(S[0] == '0'): seq.append(0)
    f = S[0]
    c = 1
    for i in range(1, N):
        if(S[i] == f):
            c += 1
        else:
            seq.append(c)
            f = S[i]
            c = 1
    seq.append(c)
    
    rseq = [0] * (len(seq)+1)
    for i in range(1,len(seq)+1):
        rseq[i] = rseq[i-1] + seq[i-1]

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


    
    
    
    
    

    print(ans)

    return



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

if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
s = input()
cnt = 0
d = s[0]
ss = []
for i in range(N):
  if s[i] == d:
    cnt += 1
  else:
    ss.append(cnt)
    cnt = 1
    d = s[i]
ss.append(cnt)
ss.append(0)
ss.append(0)
ss.append(0)

cs = [0]
if s[0]=="0":
  cs.append(0)
for x in ss:
  cs.append(cs[-1]+x)

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

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

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

count=0
for si in s:
  if count==0:
    flag = si
    count=1
  elif flag == si:
    count+=1
  else:        
    sp.append(count)
    flag = si
    count=1
if count>0:
  sp.append(count)
if s[-1]=='0':
  sp.append(0)

ss=[0]
ss.append(sp[0])
count = 0
for spi in sp[1:]:
  ss.append(ss[-1]+spi)  

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

print(ans)

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

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

Add = 2 * K + 1  
sum_ = 0
sum_max = 0
sum_list = [0] * (len(Nums)+1)
for i in range(len(Nums)):  
    sum_list[i+1] = sum_list[i] + Nums[i]

for i in range(0, len(Nums), 2):
    left = i
    right = min(i + Add, len(Nums))  
    sum_ = sum_list[right] - sum_list[left]
    sum_max = max(sum_, sum_max)

print(sum_max)

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

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

Add = 2 * K + 1  
left = 0
right = 0
sum_ = 0
sum_max = 0

for i in range(0, len(Nums), 2):  
    Nextleft = i
    Nextright = min(i + Add, len(Nums))  
    while Nextleft > left:
        sum_ -= Nums[left]
        left += 1
    while Nextright > right:
        sum_ += Nums[right]
        right += 1
    sum_max = max(sum_, sum_max)

print(sum_max)

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

i = 0
count = 0
while i != len(S):
    if S[i] != S[i-1] and i != 0:
        X.append(count)
        Y.append(S[i-1])
        count = 1
    else:
        count += 1
    i += 1
X.append(count)
Y.append(S[-1])

ans = 0
zero_counter = 0
val = 0
j = 0 
for i in range(len(X)):
    if Y[i] == '0':
        zero_counter += 1
    val += X[i]
    while zero_counter > K:
        val -= X[j]
        if Y[j] == '0':
            zero_counter -= 1
        j += 1
    if ans < val:
        ans = val
print(ans)

Solution (Python):
def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, cs = 2*k, [l[0]]

    for i in range(1, len(l)):
        cs.append(cs[i-1]+l[i])
    a = cs[0]
    for i in range(0, len(l), 2):
        tmp = cs[min(i+r, len(l)-1)]-cs[i]+l[i]
        a = max(a, tmp)
    print(a)

if __name__ == "__main__":
    f_d()

Solution (Python):
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 1
00010"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """14 2
11101010110011"""
        output = """8"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 1
1"""
        output = """1"""
        self.assertIO(input, output)

def resolve():
    (N,K) = (int(i) for i in input().split())
    S=input()
    l=[]
    flg=False
    if S[0]=='0':
        l.append([0,0])
    for i in range(len(S)):
        if flg==True and S[i]=='0':
            l[-1].append(i)
            flg=False
        if flg==False and S[i]=='1':
            l.append([i])
            flg=True
    if S[-1]=='0':
        l.append([len(S),len(S)])
    else:
        l[-1].append(len(S))
    if K>=len(l)-1:
        print(len(S))
        return()

    print(max( [ l[i+K][1]-l[i][0] for i in range(len(l)-K)] ) )
       

if __name__ == "__main__":
    resolve()

Solution (Python):
def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, a = 2*k+1, 0
    li = ri = tmp = 0
    for i in range(0, len(l), 2):
        nli, nri = i, min(i+r, len(l))
        while li<nli:
            tmp -= l[li]
            li += 1
        while ri<nri:
            tmp += l[ri]
            ri += 1
        a = max(a, tmp)
    print(a)

if __name__ == "__main__":
    f_d()

Solution (Python):

from collections import deque
n,k=map(int,input().split())
s=input()
if n==1:
    print(1)
elif "1" not in s:
  	print(len(s))
else:
    a=deque([])
    if s[0]=="1":
        a.append([0])
    for i in range(1,n):
        if s[i-1:i+1]=="01":
            a.append([i])
        elif s[i-1:i+1]=="10":
            a[-1].append(i-1)
    if s[n-1]=="1":
        a[-1].append(n-1)
    if a[0][0]!=0:
        a.appendleft([0,0])
    if a[-1][1]!=n-1:
        a.append([n-1,n-1])
    if len(a)-1<=k:
        print(n)
    else:
        t=0
        for i in range(len(a)-k):
            t=max(t,a[i+k][1]-a[i][0]+1)
        print(t)

Solution (Python):
N, K = map(int,input().split(' '))
S = input()
S2=[]
key=S[0]
tmpcnt=1
if key=='0':
    S2.append(0)
S2.append(0)
S2.append(0)
for i in range(1,len(S)):
    if key!=S[i]:
        if key == '0':
            S2.append(-1*tmpcnt)
        else:
            S2.append(tmpcnt)
        key=S[i]
        tmpcnt=1
    else:
        tmpcnt+=1
if key == '0':
    S2.append(-1*tmpcnt)
    S2.append(0)
    S2.append(0)
else:
    S2.append(tmpcnt)
    S2.append(0)
    S2.append(0)

max=0
tmp=S2[0]
maxj=len(S2)-1
for j in range(1,K*2+1):
    tmp+=abs(S2[min(0+j,maxj)])
    
if tmp >= max:
    max=tmp
    

for i in range(2,len(S2),2):
    tmp-=abs(S2[i-1])
    tmp-=abs(S2[i-2])
    tmp+=abs(S2[min(i+j-1,maxj)])
    tmp+=abs(S2[min(i+j,maxj)])
    
    
    if tmp>= max:
        max=tmp
print(max)

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


human = []
humancount = []
for key, group in itertools.groupby(S):
    human.append(key)
    humancount.append(len(list(group)))

humancount_ac = [0] + list(itertools.accumulate(humancount))

ans = 0
j = 0
count = 0

for i in range(N):
    while j <= len(human)-1:
        if human[j] == "0" and count < K:
            count += 1
            j += 1
            ans = max(ans, humancount_ac[j] - humancount_ac[i])
        elif human[j] == "1":
            j += 1
            ans = max(ans, humancount_ac[j] - humancount_ac[i])
        else:
            if human[i] == "0":
                count -= 1
            break
print(ans)

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

if(s[0] == '0'):
  arr.append(0)
for i in range(n-1):
  if(s[i] != s[i+1]):
    arr.append(i+1)
arr.append(n)
if(s[-1] == '0'):
  arr.append(n)
    
width = 2*k + 1
len_arr = len(arr)

if(2*k >= len_arr):
  ans = arr[-1]
else:
  ans = arr[2*k]
  left = 2
  while True:
    if(left + width > len_arr):
      break
    tmp = arr[left + width - 1] - arr[left - 1]
    ans = max(ans, tmp)
    left += 2
print(ans)

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

bl = []
if S[0] == "0":
    bl.append(0)
bl.append(0)
for i in range(1, N):
    if S[i-1] != S[i]:
        bl.append(i)
bl.append(N)
bl.append(N)

nbl = len(bl)
m = [bl[i+2 * K+1] - bl[i] 
     for i in range(nbl - 2*K-1) if i%2 == 0]
if len(m) == 0:
    print(N)
else:
    print(max(m))

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

l = 0
r = 0
change = 0 if S[0] == '1' else 1
ans = 0
while l < N and r < N:
    
    ans = max(ans, r-l+1)
    if r == N-1:
        break
    if S[r] == '0':
        r += 1
    else:
        if S[r+1] == '0':
            if change < K:
                change += 1
                r += 1
            else:
                if S[l] == '0' and S[l+1] == '1':
                    r += 1
                l += 1
        else:
            r += 1
print(ans)

Solution (Python):
n,k = map(int,input().split())
s = input()
tmp = 1
spl = []
for i in range(1,n):
  if s[i-1] == s[i]:
    tmp += 1
  else:
    spl.append(tmp)
    tmp = 1
spl.append(tmp)

l = len(spl)
acu = [0]
for m in range(l):
  acu.append(acu[-1]+spl[m])
acu = [0] + acu + [acu[-1]]

can = []
if s[0] == '0':
  st = 0
else:
  st = 1
while True:
  try:
    can.append(acu[st+2*k+1]-acu[st])
    st += 2
  except:
    break
try:
  print(max(can))
except:
  print(n)

Solution (Python):
n,k = map(int,input().split())
s = '0'+input()+'0'
Handstands = [(1,1)]
for i in range(1,n+2):
    if s[i-1]=='0' and s[i]=='1':
        left = i
    if s[i-1]=='1' and s[i]=='0':
        right = i
        Handstands += [(left,right)]
Handstands += [(n+1,n+1)]
if k<=len(Handstands)-1:
    ans = 0
    for i in range(len(Handstands)-k):
        ans = max(ans,Handstands[i+k][1]-Handstands[i][0])
    print(ans)
else:
    print(n)

Solution (Python):
def solve(N, K, S):
    X = [0]
    for i in range(1, N):
        if S[i-1] != S[i]:
            X.append(i)
    X.append(N)

    m = None
    for i in range(len(X)-1):
        j = i + 2 * K
        if S[X[i]] == '1':
            j += 1
        j = min(j, len(X)-1)
        
        m = max(0 if m is None else m, X[j] - X[i])
    if m is None:
        return N
    return m

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

Solution (Python):
from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
t=r=sum(a[:k+1]+b[:k]) 
for w,x,y,z in zip(a,b,a[k+1:],b[k:]):
	t+=-w-x+y+z
	r=max(r,t)
print(r)

Solution (Python):
import math
N,K = map(int,input().split())
S = input()
seq = 1
v_seq = 1
down_list = []
count = 0
down_num = 0
ans = 0
chk = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        seq += 1
        v_seq += 1
    elif S[i] == "0":
        down_list.append(seq)
        seq = 1
        v_seq += 1
        count += 1
        if count == K:
            chk = 1
    else:
        if chk == 2:
            v_ans = v_ans + v_seq-down_list[v_count]
            v_count += 1
            ans = max(ans,v_ans)
        v_seq = 1
        seq += 1
        if chk == 1:
            ans = i+1
            v_ans = i+1
            v_count = 0
            chk = 2
if ans == 0:
    print(N)
else:
    v_ans = v_ans + v_seq-down_list[v_count]
    print(max(ans,v_ans))

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

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

S += '2'
count_lis = []
cnt_1 = 0
first_one = True
for n in range(N):
    if S[n] == '1':
        if first_one:
            tmp = n
            first_one = False
        cnt_1 += 1
        if S[n + 1] == '0' or n == N - 1:
            
            count_lis.append([tmp, n, cnt_1])
            cnt_1 = 0
            first_one = True

length = len(count_lis)
ans = 0

if length >= K:
    if S[0] == '0':
        ans = max(count_lis[K - 1][1] + 1, ans)
    if S[N - 1] == '0':
        ans = max(N - count_lis[len(count_lis) - K][0], ans)
    for j in range(length - K):
        tmp_ans = count_lis[j + K][1] - count_lis[j][0] + 1
        
        if ans < tmp_ans:
            ans = tmp_ans
else:
    ans = N

print(ans)

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

right = 0
res = 0
zero_area = 1 if s[0] == '0' else 0
for left in range(n):
    if left > 0:
        if s[left-1] == '0' and s[left] == '1':
            zero_area -= 1
    while right < n-1:
        if s[right] == '1' and s[right+1] == '0':
            if zero_area + 1 > k:
                break
            zero_area += 1
        right += 1
    res = max(res, right - left + 1)

print(res)

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

right = 0
res = 0
zero_area = 1 if s[0] == '0' else 0
for left in range(n):
    if left > 0:
        if s[left-1] == '0' and s[left] == '1':
            zero_area -= 1
    while right < n-1:
        if s[right] == '1' and s[right+1] == '0':
            if zero_area + 1 > k:
                break
            zero_area += 1
        right += 1
    res = max(res, right - left + 1)

print(res)

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

l = []
now = 1 
cnt = 0


for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now 
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: 
    l.append(0)


ans = 0
width = 2 * K + 1



lsum = [0 for _ in range(len(l) + 1)] 
for i in range(len(l)): 
    lsum[i + 1] = lsum[i] + l[i]


for i in range(0, len(l), 2): 
    left = i
    right = min(i + width, len(l))
    tmp = lsum[right] - lsum[left] 
    ans = max(ans, tmp)

"""



left = 0
right = 0
tmp = 0 

for i in range(0, len(l), 2):
    
    nextleft = i 
    nextright = min(i + width, len(l)) 

    
    while nextleft > left:
        tmp -= l[left]
        left += 1

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

    ans = max(ans, tmp)
"""

"""


for i in range(0, len(l), 2): 
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): 
        tmp += l[j]
    ans = max(ans, tmp)
"""

print(ans)

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

l = []
now = 1 
cnt = 0


for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now 
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: 
    l.append(0)


ans = 0
width = 2 * K + 1

left = 0
right = 0
tmp = 0 
for i in range(0, len(l), 2):
    nextleft = i 
    nextright = min(i + width, len(l)) 
    while nextleft > left:
        tmp -= l[left]
        left += 1
    while nextright > right:
        tmp += l[right]
        right += 1
    ans = max(ans, tmp)

"""

for i in range(0, len(l), 2): 
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): 
        tmp += l[j]
    ans = max(ans, tmp)
"""

print(ans)

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

change = [0] 
for i, (a, b) in enumerate(zip(S,S[1:])):
    if a != b: 
        change.append(i+1)

ans = 0
for i in range(len(change)):
    if S[change[i]] == "0":
        if i == 0:
            if 2*K >= len(change):
                print(N)
                exit()
            tmp = change[2*K]
        else:
            if i+2*K >= len(change):
                tmp = N-(change[i-1])
            else:
                tmp = (change[i+2*K] - 1) - (change[i-1] - 1)
        ans = max(ans, tmp)
    else:
        if i+2*K+1 >= len(change):
            tmp = N - change[i]
        else:
            
            
            tmp = (change[i+2*K+1]-1) - (change[i]-1)
        ans = max(ans, tmp)
    

print(ans)

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

previous = S[0]
counter = 1

new_S = []




for i in range(1,N):
    if S[i] == previous:
        counter += 1

        if i == N-1:
            if previous == '0':
                counter *= -1
            new_S.append(counter)

    else:
        if previous == '0':
            counter *= -1

        new_S.append(counter)

        previous = S[i]
        counter = 1

        if i == N-1:
            if previous == '0':
                counter *= -1
            new_S.append(counter)

if S[0] == '1' and len(S) == 1:
    new_S = [1]
elif S[0] == '0' and len(S) == 1:
    new_S = [0]


length = len(new_S)
l = 0

score = 0
ans = 0
minus = 0


for r in range(length):

    if new_S[r] < 0:
        minus += 1

    score += abs(new_S[r])

    if minus > K:
        
        for i in range(l,r+1):
            l += 1
            score -= abs(new_S[i])
        
            if new_S[i] < 0:
                minus -= 1
                break

    ans = max(score,ans)

print(ans)

Solution (Python):
N, K = map(int, input().split())
S = input()
Is = []
i = 0
while i < N:
  j = S.find("0", i)
  if j < 0: j = N
  k = S.find("1", j)
  if k < 0: k = N
  Is.append((i, j, k))
  i = k
Is.append((N, N, N))

if len(Is) <= K:
  r = N
  print(r)
  exit()
rs = []
for i in range(len(Is)-K):
  r = Is[i+K][1]-Is[i][0]
  rs.append(r)

r = max(rs)
print(r)

Solution (Python):
N, K = map(int, input().split())
s = input()
ls = []
for i in range(N):
  if i != N-1 and s[i]!=s[i+1]:
    ls += [i]
length = len(ls)
ls += [N-1]*(2*K+2)
m = 0
if s[0]=='0':
  for i in range(0,length,2):
    x = ls[i+2*K+1]-ls[i]
    if x>m:
      m = x
  x = ls[2*K-1]+1
  if x>m:
    m = x
else:
  for i in range(1, length, 2):
    x = ls[i+2*K+1]-ls[i]
    if x>m:
      m = x
  x = ls[2*K]+1
  if x>m:
    m = x
print(m)

Solution (Python):
def to_cumsum(arr):
    """
    1次元配列を累積和の1次元配列に変換する
    """
    cumsum = 0
    new = list()
    for e in arr:
        cumsum += e
        new.append(cumsum)
    return new


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




nums = list()
if S.startswith('0'):
    nums.append(0)

cnt = 0
cur = S[0]
for c in S:
    if c == cur:
        cnt += 1
    else:
        nums.append(cnt)
        cnt = 1
        cur = '1' if cur == '0' else '0'
nums.append(cnt)

if S.endswith('0'):
    nums.append(0)


cumsum = to_cumsum(nums)


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

Solution (Python):
N,K = map(int,input().split())
S = list(input())
S = list(map(int,S))
A = []
cnt1 = 0
for i in range(N):
    if S[i]==1:
        cnt1 += 1
    else:
        if cnt1>0:
            A.append(cnt1)
            cnt1 = 0
if S[N-1]==1:
    A.append(cnt1)
B = []
cnt0 = 0
for i in range(N):
    if S[i]==0:
        cnt0 += 1
    else:
        if cnt0>0:
            B.append(cnt0)
            cnt0 = 0
if S[N-1]==0:
    B.append(cnt0)
if S[0]==1:
    B.insert(0,0)
if S[-1]==1:
    B.append(0)
k = min(len(B),K)
a = sum(A[:k])+sum(B[:k])
d = a
for i in range(k,len(B)):
    if i==len(B)-1 and i-k-1>=0:
        d = d-A[i-k-1]+B[i]-B[i-k]
    elif i==len(B)-1 and i-k-1<0:
        d = d+B[i]-B[i-k]
    elif i==k:
        d = d+A[i]+B[i]-B[i-k]
    else:
        d = d+A[i]-A[i-k-1]+B[i]-B[i-k]
    a = max(a,d)
print(a)

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