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 collections import deque

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

cnt_01 = []
prev = s[0]
cnt = 0
for c in s:
    if c != prev:
        cnt_01.append(cnt)
        cnt = 1
    else: 
        cnt += 1
    prev = c
else:
    cnt_01.append(cnt)


if len(cnt_01) <= 2*k:
    print(n)
    exit()


if s[0] == '0':
    ans_candi = sum(cnt_01[0:2*k])
    cnt_01 = cnt_01[1:]
else:
    ans_candi = 0


first_que = cnt_01[0:2*k+1]
que = deque(first_que)
curr_sum = sum(first_que)
ans = curr_sum
for i in range(k, len(cnt_01)-1):
    break_flag = False
    poped1 = que.popleft()
    poped2 = que.popleft()
    curr_sum -= (poped1 + poped2)
    if 2*i+1 < len(cnt_01):
        que.append(cnt_01[2*i+1])
        curr_sum += cnt_01[2*i+1]
    if 2*i+2 < len(cnt_01):
        que.append(cnt_01[2*i+2])
        curr_sum += cnt_01[2*i+2]
    else:
        break_flag = True
    ans = max(curr_sum, ans)
    if break_flag: break

print(max(ans,ans_candi))

Solution (Python):
import sys

N, K = map(int, sys.stdin.readline().strip().split())
S = sys.stdin.readline().strip()

l = x = ans = 0
for r in range(N):
    if S[r] == '0' :
        if r == 0 or S[r-1] == '1':
            x += 1
    if x > K:
        while S[l] == '1':
            l += 1
        while S[l] == '0':
            l += 1
        x -= 1
    ans = max(ans, r-l+1)
print(ans)

Solution (Python):

def resolve():
    N, K = list(map(int, input().split()))
    S = input()
    seq = []
    cnt = 0
    if S[0] != "1":
        seq.append(0)
    for i in range(len(S)-1):
        if S[i] != S[i+1]:
            seq.append(cnt+1)
            cnt = 0
        else:
            cnt += 1
    seq.append(cnt+1)
    if S[-1] != "1":
        seq.append(0)
    

    cum = [0]
    cur = 0
    for c in seq:
        cur += c
        cum.append(cur)
    
    
    maxlen = len(S) if len(cum) <= (2*K+1) else 0
    for i in range(0, len(cum)-(2*K+1), 2):
        l = cum[i+(2*K+1)] - cum[i]
        maxlen = max(maxlen, l)
    print(maxlen)
    

if '__main__' == __name__:
    resolve()

Solution (Python):
def resolve():
    N, K = list(map(int, input().split()))
    S = input()
    seq = []
    cnt = 0
    for i in range(len(S)):
        if i == N-1 or S[i] != S[i+1]:
            seq.append([cnt+1, S[i]])
            cnt = 0
        else:
            cnt += 1
    
    left = 0
    right = 0
    maxlen = 0
    val = 0
    n_rev = 0
    for left in range(0, len(seq)):
        while (right < len(seq) and (n_rev < K or seq[right][1]=="1")):
            
            cnt, state = seq[right]
            val += cnt
            if state == "0":
                n_rev += 1
            right += 1
        maxlen = max(maxlen, val)
        cnt, state = seq[left]
        val -= cnt
        if state == "0":
            n_rev -= 1
        if left == right:
            right += 1
    print(maxlen)
    

if '__main__' == __name__:
    resolve()

Solution (Python):
n,k = map(int,input().split())
s = input()
l = list(s)
s_list = []
count = 1
if n >=2:
  for i in range(1,n):
    if s[i] != s[i-1]:
      s_list.append(count)
      count = 1
    else:
      count += 1
    if i == n-1:
      s_list.append(count)
  sum_s = [0,s_list[0]]
  for i in range(1,len(s_list)):
    sum_s.append(sum_s[-1] + s_list[i])
  if s[0] == "1":
    result = []
    for i in range(1,len(sum_s)):
      if i % 2 == 1:
        result.append(sum_s[min(len(sum_s)-1,i+2*k)] - sum_s[i-1])
      else:
        result.append(sum_s[min(len(sum_s)-1,i+2*k-1)] - sum_s[i-1])

  else:
    result = []
    for i in range(1,len(sum_s)):
      if i % 2 == 1:
        result.append(sum_s[min(len(sum_s)-1,i+2*k-1)] - sum_s[i-1])
      else:
        result.append(sum_s[min(len(sum_s)-1,i+2*k)] - sum_s[i-1])

if n == 1:
  print(1)
else:
  print(max(result))

Solution (Python):

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

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

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

SUM = sum(a[0:0+2*K+1])

MAX = max(0, SUM)
for i in range(2, len(a)):
    if i % 2 == 0:
        try:
            SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1]+a[i+2*K])
        except:
            try:
                SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1])
            except:
                break
        
        MAX = max(MAX, SUM)


print(MAX)

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

cnt = []
if s[0] == '0': cnt.append(0)
i = 0
while i < n:
    j = i
    while j < n and s[j] == s[i]:
        j += 1
    cnt.append(j- i)
    i = j
if s[-1] == '0': cnt.append(0)

m = len(cnt)
cs = [0] * (m+1)
for i in range(m):
    cs[i+1] = cs[i] + cnt[i]

ans = 0
for l in range(0, m+1, 2):
    r = l + 2 * k + 1
    if r > m: r = m
    ans = max(ans, cs[r] - cs[l])

print(ans)

Solution (Python):
N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
   plus=0
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
   plus=1
max_n=sum_n
for i in range(len(ans)-end+plus):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         print(max_n)
         exit()
      now=0
   max_n=max(sum_n,max_n)
print(max_n)

Solution (Python):
from operator import add
from collections import deque
from itertools import accumulate

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

if N == 1:
  if S == "1" or K >= 1:
    print(1)
  else:
    print(0)
    
else:
  num = []
  cnt = 1
  ans = 0
  M = 2 * K + 1

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

  if S[0] == "0":
    num = [0] + num
  
  acc = list(accumulate(num,add))
  acc = [0] + acc
  A = len(acc)
  
  for left in range(0,A,2):
    right = min(A - 1,left + M)
    ans = max((acc[right] - acc[left]),ans)
    
  print(ans)

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


L = [0]
R = []
for i, (a, b) in enumerate(zip(s, s[1:])):
    if (a, b) == ('0', '1'):
        L.append(i+1)

    if (a, b) == ('1', '0'):
        R.append(i)
else:
    R.append(n-1)

ans = R[0]-L[0]+1
if s[0] == '0':
    k -= 1
k = min(k, len(R)-1)
for l, r in zip(L, R[k:]):
    x = r-l+1
    if ans < x:
        ans = x
print(ans)

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

prev_R = '1'
for R in range(n):
    if (prev_R, s[R]) == ('1', '0'):
        k -= 1
        if k < 0:
            R -= 1
            break
    prev_R = s[R]

ans = R+1
for L in range(n-1):
    if (s[L], s[L+1]) != ('0', '1'):
        continue
    R += 1
    while R < n-1 and (s[R], s[R+1]) != ('1', '0'):
        R += 1
    if ans < R-L:
        ans = R-L
print(ans)

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

if N==1:
  U=[ [T[0],1] ]
else:
  tmp=T[0]
  cnt=1
  for i in range(1,N):
    if i==N-1:
      if T[i]==T[i-1]:
        cnt+=1
        U.append([tmp,cnt] )
      else:
        U.append([tmp,cnt] )
        U.append([T[i],1])
    else:
      if T[i]==T[i-1]:
        cnt+=1
      else:
        U.append([tmp,cnt] )
        tmp=T[i]
        cnt=1

summ=0
for j in range(len(U)):
  summ += U[j][1]
  U[j][1]=summ
if U[0][0]==0:
  U.insert(0,[1,0])
  U.insert(0,[0,0])
else:
  U.insert(0,[0,0])


maxi=0
  
for p,q in enumerate(U):
  if q[0]==1:
    pass
  else:
    right=min(p+K*2+1,len(U)-1)
    diff=U[right][1]-U[p][1]
    maxi=max(diff,maxi)
    
print(maxi)

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

s=list(input())

memo = [0]

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

ans = 0

kyoukai_math = len(memo)

for i in range(kyoukai_math):
  if s[memo[i]] == '1':
    hasi = i+k*2+1
  else:
    hasi = i+k*2
    
  if hasi < kyoukai_math:
    ans = max(ans,memo[hasi]-memo[i])
  else:
    ans = max(ans,n-memo[i])
print(ans)

Solution (Python):
n,k = map(int,input().split())
s = input()
cou = 0
p = 1
nagasa = []
for i in range(n):
    if int(s[i]) == p:
        cou += 1
    elif int(s[i]) != p:
        if p == 1:
            p = 0
        elif p == 0:
            p = 1
        nagasa.append(cou)
        cou = 1
nagasa.append(cou)
if len(nagasa) % 2 == 0:
    nagasa.append(0)
h = len(nagasa)

if h // 2 <= k:
    print(n)
    exit()
lef = 0
rig = 2*k+1
now = sum(nagasa[lef:rig])
ans = now
while True:
    if rig == h:
        break
    now = now - nagasa[lef] - nagasa[lef+1] + nagasa[rig] + nagasa[rig+1]
    ans = max(ans,now)
    lef += 2
    rig += 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)

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 -= Nums[left]
        left += 1
    
    while Nextright > right:
        tmp += Nums[right]
        right += 1
    ans = max(tmp, ans)

print(ans)

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


zero_list = []
one_list = []
tmp = S[0]
count = 1
pin = 0
if tmp == '1':
    zero_list.append(0)
for i in range(1,N):
    if S[i] == tmp:
        count += 1
    else:
        if tmp == '1':
            one_list.append(count)
            count = 1
            tmp = '0'
        else:
            zero_list.append(count)
            count = 1
            tmp = '1'
if tmp == '1':
    one_list.append(count)
else:
    zero_list.append(count)
        
if K >= len(zero_list):
    pin =1
    print(N)
else:
    start = sum(zero_list[:K]) + sum(one_list[:K])
    ans = start
    if len(one_list) > K:
        tmp = start - zero_list[0] + zero_list[K] + one_list[K]
    else:
        tmp = start - zero_list[0] + zero_list[K]
    if tmp > ans:
        ans = tmp
    basyo = 1
    last = len(one_list)
    while basyo + K < last:
        tmp = tmp -zero_list[basyo] - one_list[basyo -1] + zero_list[K + basyo] + one_list[K + basyo]
        if tmp > ans:
            ans = tmp
        basyo += 1
    if len(one_list) != len(zero_list) and K + basyo <  len(zero_list):
        tmp = tmp -zero_list[basyo] - one_list[basyo -1] + zero_list[K + basyo] 
        if ans < tmp:
            ans = tmp
if pin == 0:
    print(ans)

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

s = '1' + s + '1'

cnt_1 = []
cnt_0 = []
stack_1 = 0
stack_0 = 0
for i in s:
    if i == '1':
        if stack_0 > 0:
            cnt_0.append(stack_0)
            stack_0 = 0
        stack_1 += 1
    else:
        if stack_1 > 0:
            cnt_1.append(stack_1)
            stack_1 = 0
        stack_0 += 1
if stack_1 > 0:
    cnt_1.append(stack_1)

if len(cnt_1) == 0 or len(cnt_0) == 0:
    print(n)
    exit()
cnt_1[0] -= 1
cnt_1[-1] -= 1

if k > len(cnt_0):
    k = len(cnt_0)
cum_1 = [sum(cnt_1[:k+1])]
cum_0 = [sum(cnt_0[:k])]
for i in range(1, len(cnt_1)-k):
    cum = cum_1[i-1] + cnt_1[i+k] - cnt_1[i-1]
    cum_1.append(cum)
for i in range(1, len(cnt_0)-k+1):
    cum = cum_0[i-1] + cnt_0[i+k-1] - cnt_0[i-1]
    cum_0.append(cum)
res = []

for v, w in zip(cum_1, cum_0):
    res.append(v+w)
print(max(res))

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

counts = []
tmp = []
for i in range(len(s)):
    if tmp == []:
        tmp = [s[i], 1]
    else:
        if tmp[0] == s[i]:
            tmp[1] += 1
        else:
            counts.append(tmp)
            tmp = [s[i], 1]
if tmp:
    counts.append(tmp)

zero_ints = 0
for char, count in counts:
    if char == '0':
        zero_ints += 1

if counts[0][0] == '0':
    left = 0
else:
    left = 1
right = left - 2

used = 0
l = 0
for char, count in counts:
    if char == '0':
        if used < k:
            used += 1
            right += 2
        else:
            break
    l += count

ans = l
for i in range(zero_ints):
    l = l - counts[left][1]
    if left - 1 >= 0:
        l-= counts[left - 1][1]
    if right + 2 < len(counts):
        l += counts[right + 2][1]
    if right + 3 < len(counts):
        l += counts[right + 3][1]
    ans = max(ans, l)
    left += 2
    right += 2
    
print(ans)

Solution (Python):
n, k = map(int, input().split())
s = input()
u = []
d = []
if s[0]=='0':
    d.append(0)
cnt = 1
for i in range(n-1):
    if s[i+1]=='1' and s[i]=='0':
        u.append(cnt)
        cnt = 1
    elif s[i+1]=='0' and s[i]=='1':
        d.append(cnt)
        cnt = 1
    else:
        cnt += 1
if s[-1]=='0':
    u.append(cnt)
    d.append(0)
else:
    d.append(cnt)
if len(u)<=k:
    print(n)
    exit()
tmp = sum(d[:k+1]) + sum(u[:k])
ans = tmp
for i in range(len(u)-k):
    tmp += u[i+k]+d[i+k+1]-u[i]-d[i]
    ans = max(ans, tmp)
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,K = IL()
S = S()

zero = []
one = []

prev = None
count = 1
for s in S:
  if s == prev:
    count += 1
  else:
    if prev == "0":
      zero.append(count)
    if prev == "1":
      one.append(count)
    count = 1
  prev = s
if prev == "0":
  zero.append(count)
if prev == "1":
  one.append(count)
  
if len(zero) <= K:
  print(N)
  exit()

ruiseki_zero = [0]
ruiseki_one = [0]
for i in range(len(zero)):
  ruiseki_zero.append(ruiseki_zero[-1]+zero[i])
for i in range(len(one)):
  ruiseki_one.append(ruiseki_one[-1]+one[i])

MAX = 0
if S[0] == "0":
  for i in range(len(ruiseki_zero)-K):
    MAX = max(MAX,ruiseki_zero[i+K]-ruiseki_zero[i]+ruiseki_one[min(i+K,len(ruiseki_one)-1)]-ruiseki_one[max(i-1,0)])
else:
  for i in range(len(ruiseki_zero)-K):
    MAX = max(MAX,ruiseki_zero[i+K]-ruiseki_zero[i]+ruiseki_one[min(i+K+1,len(ruiseki_one)-1)]-ruiseki_one[i])

print(MAX)

Solution (Python):
import itertools

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():

    N, K = ZZ()
    S = input()
    gr = itertools.groupby(S)
    l = []
    c = 0
    for i, j in gr:
        l.append([int(i), len(list(j))])
        if i == '0': c += 1
    if c <= K:
        print(N)
        return
    output = 0
    left = right = 0
    sum = c = 0
    while left < len(l):

        while right < len(l) and c < K:
            if l[right][0] == 0: c += 1
            sum += l[right][1]
            right += 1
        if right < len(l) and l[right][0] == 1:
            sum += l[right][1]
            right += 1
        output = max(output, sum)
        if right == left:
            right += 1
            left += 1
        else:
            if l[left][0] == 0: c -= 1
            sum -= l[left][1]
            left += 1
            while left < len(l) and c >= K:
                if l[left][0] == 0: c -= 1
                sum -= l[left][1]
                left += 1
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N, K = map(int,input().split())
S = input()
L = np.zeros(N+1, int)
flag = '1'
i = 0
for char in S:
    if char == flag:
        L[i] += 1
    else:
        i += 1
        flag = char
        L[i] += 1

W = min(2 * K + 1, N + 1)

ans = L[:W].sum()

cnt = L[:W].sum()

for i in range((N+1-W) // 2):
    cnt = cnt - L[i*2] - L[i*2+1] + L[i*2+W] + L[i*2+W+1]
    ans = max(ans, cnt)
print(ans)

Solution (Python):
N,K=map(int,input().split())
s=input()
g=[]
l=0
for i in range(1,N):
    if s[i]!=s[i-1]:
        g.append(i-l)
        l=i
g.append(N-l)

M=len(g)
ans=0
S=[0]
for h in range(M):
    S.append(S[h]+g[h])

if s[0]=="0":
    if K>M//2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>M:
                break
            elif j==0:
                ans=max(ans,S[j+2*K]-S[j])
            elif j%2==1:
                ans=max(ans,S[j+2*K+1]-S[j])
        ans=max(ans,S[M]-S[M-2*K])
        print(ans)
    
else:
    if K>=M//2+M%2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>M:
                break
            elif j%2==0:
                ans=max(ans,S[j+2*K+1]-S[j])
        ans=max(ans,S[M]-S[M-2*K])
        print(ans)

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

ttl = []
prev = S[0] 
cnt = 1
if S[0] == '0':
    ttl.append(0)
for i in range(1, N):
    if S[i] == prev:
        cnt += 1
    else:
        ttl.append(cnt)
        cnt = 1
    prev = S[i]
if cnt != 0:
    ttl.append(cnt)
if S[-1] == '0':
    ttl.append(0)
l = len(ttl)
sums = [0] * (l + 1)
for i in range(l):
    sums[i+1] = sums[i] + ttl[i]

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

Solution (Python):
from collections import deque
n,k=map(int,input().split())
s=list(map(int,list(input())))
cnt=0
q=deque()
prev=1
ans=[]
for i in s:
    if i==0 and prev==1:
        cnt+=1
    q.append(i)
    prev=i
    if cnt>k:
        
        ans.append(len(q)-1)
        prev1=1
        while len(q)>0:
            if q[0]==1 and prev1==0 and cnt<=k:
                break
            if q[0]==0 and prev1==1:
                cnt-=1
            prev1=q[0]
            q.popleft()
ans.append(len(q))
print(max(ans))

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

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

ct = 0
for s in S:
    if tmp == s:
        ct += 1
    else:
        S_lst.append(ct)
        tmp = s
        ct = 1
if ct:
    S_lst.append(ct)

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

l, r = 0, K * 2

M = sum(S_lst[:K * 2 + 1])
ans = M
while r < len(S_lst) - 2:
    M += S_lst[r + 1] + S_lst[r + 2] - S_lst[l] - S_lst[l + 1]
    ans = max(ans, M)
    l += 2
    r += 2
print(ans)

Solution (Python):
import sys

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

isOneFound = False
ruiseki = []
if S[0] == "0":
    ruiseki.append(0)

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

if S[-1] == "0":
    ruiseki.append(N)




if K >= (len(ruiseki)-1) // 2:
    print(N)
    sys.exit(0)


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

print(ans)

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

    res = []
    buf = '1' 
    cnt = 0
    for i in range(n):
        if s[i] == buf:
            cnt += 1
        else:
            res.append(cnt)
            buf = s[i]
            cnt = 1
    if cnt != 0:
        res.append(cnt)

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
 

def rle(s):
    tmp, count, ans_c,ans_n = int(s[0]),1,[] , []
    for i in range(1,len(s)):
        if tmp == int(s[i]):
            count += 1
        else:
            ans_c.append(tmp)
            ans_n.append(count)
            tmp = int(s[i])
            count = 1
    ans_c.append(tmp)
    ans_n.append(count)
    return ans_c,ans_n


import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()


a_c,a_n =rle(S)
a_len =len(a_c)
a_n +=[0]
count =[0]*a_len
ans =0


if K >= (a_len +1)//2:
    ans =N
elif a_len==2:
    ans =N
elif a_len ==3 and a_c[0]==1:
    ans=N
else:
    if a_c[0] ==1:
        i=2
        indx =i +2*K 
        count[0] =sum(a_n[:0 +2*K +1])
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2
            indx =i +2*K 
    else:
        count[0] =sum(a_n[:2*K])
        count[1] =sum(a_n[1: 1+2*K+1])
        i=3
        indx =i +2*K 
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2      
            indx =i +2*K 
    ans =max(count)
print(ans)

Solution (Python):
def burst(S):
    S += "_" 
    st,sp,ep = S[0],0,0
    S0,S1 = [],[]
    for i in range(1,len(S)):
        if st == S[i]:
            ep += 1
        else:
            if st == "0":
                S0.append((sp,ep))
            else:
                S1.append((sp,ep))
            st,sp,ep = S[i],i,i

    return [S0,S1]

def connect(S0,S1,K,len_S):
    if len(S0) == 0 or len(S1) == 0:
        return len_S
    else:
        if S1[0][0] != 0:
            S1 = [(0,0)] + S1
        if S1[len(S1)-1][1] != len_S-1:
            S1.append((len_S-1,len_S-1))
        if len(S1)-1 <= K:
            return len_S
        else:
            output = 0
            for i in range(len(S1)-K):
                output = max(output,S1[i+K][1]-S1[i][0]+1)
            return output

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

    T = burst(S)
    S0,S1 = T[0],T[1]
    print(connect(S0,S1,K,N))

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product









import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    def main():

        N, K = map(int, input().split())
        s = input()
        S = [int(c) for c in s]
        runlen = []
        if S[0] != 1:
            runlen.append(0)
        flag = False
        if S[-1] != 1:
            flag = True
        gr = groupby(S)
        cnt = 0
        for key, group in gr:  
            runlen.append(len(list(group)))
            cnt += 1
        if flag:
            runlen.append(0)
        if cnt == 1:
            return N

        runlen = [0] + runlen
        
        runlen = list(accumulate(runlen))

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

        return ans
    print(main())


resolve()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
s = ins()
seq = []
strk = 0
for i in range(n):
    if i==0 or s[i-1]==s[i]:
        strk += 1
    else:
        seq.append(strk)
        strk = 1
seq.append(strk)
if len(seq)<=2*k:
    print(n)
    exit()
seq.extend([0]*8)

if s[0]=='0':
    mx = sm = sum(seq[:2*k])
    sm += seq[2*k]+seq[2*k+1]-seq[0]
    mx = max(mx,sm)
    stt = 1
    end = 2*k+1
else:
    mx = sm = sum(seq[:2*k+1])
    stt = 0
    end = 2*k
while end<len(seq)-4:
    sm += seq[end+1]+seq[end+2]-seq[stt]-seq[stt+1]
    stt += 2
    end += 2
    mx = max(mx,sm)
print(mx)

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

one = 0
zero = 0
z = 0
flg = False
num_list = []

if a[0] == '0':
    flg = True
for i in a:
    if one >= 0 and zero == 0 and i == '1':
        one += 1
    elif one == 0 and zero >= 0 and i == '0':
        zero += 1
        z += 1
    elif zero > 0 and i == '1':
        num_list.append(zero)
        one += 1
        zero = 0
    elif one > 0 and i == '0':
        num_list.append(one)
        zero += 1
        one = 0
        z += 1
num_list.append(max(one, zero))

if a[0] == '0':
    num_list.insert(0,0)
num_list.insert(0,0)
num_list.append(0)

if z <= k:
    print(n)
    exit()

n_list = []

sum = 0
for i in range(len(num_list)):
    sum += num_list[i]
    n_list.append(sum)

width = 2*k
if width >= len(num_list):
    print(n)
    exit()

max_num = 0

for i in range(1, len(n_list)-width, 2):
    num = n_list[i+width] - n_list[i-1]
    if num > max_num:
        max_num = num

print(max_num)

Solution (Python):
from collections import deque
N, K = map(int, input().split())
S = deque(input())
T = []
P = []
pre = S[0]
cnt = 0
while S:
  s = S.popleft()
  cnt += 1
  if pre != s:
    cnt -= 1
    T += [cnt]
    P += [pre]
    pre = s
    cnt = 1
T += [cnt]
P += [pre]

cum_T = T[:]
for i in range(len(T)-1):
  cum_T[i+1] = cum_T[i] + T[i+1]

cum_T += [0]
l = len(P)
ans = 0
for i in range(l):
  if P[i] == '1':
    r = min(l-1, i+2*K)
    ans = max(ans,-cum_T[i-1]+cum_T[r] )
  else:
    r = min(l-1, i+2*K-1)
    ans = max(ans, -cum_T[i-1]+cum_T[r])
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











N,K = map(int,input().split())
S = list(input())[:-1]
def rle(s):
    n = len(s)
    tmp, count,stt,end = s[0], 1,[],[]
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            if tmp == "1":
                stt.append(i-count)
                end.append(i-1)
            tmp = s[i]
            count = 1
    if s[n-1] == "1":
        stt.append(n-count)
        end.append(n-1)
    return stt,end 
stt,end = rle(S)
n = len(stt)
if S[0] == "1" and S[N-1] == "1":
    if K >= n-1:
        print(N)
    else:
        MAX = 0
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)
elif S[0] == "0" and S[N-1] == "0":
    if K >= n+1:
        print(N)
    else:
        MAX = max(end[K-1]+1,N-stt[-K])
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)
elif S[0] == "1" and S[N-1] == "0":
    if K >= n:
        print(N)
    else:
        MAX = N-stt[-K]
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)
else:
    if K >= n:
        print(N)
    else:
        MAX = end[K-1]+1
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)

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

    one_zero = []
    target = '1'
    cnt = 0
    for i in range(N):
        if S[i] != target:
            one_zero.append(cnt)
            target = '1' if target == '0' else '0'
            cnt = 1
        else:
            cnt += 1
    else:
        one_zero.append(cnt)
        if target == '1':
            one_zero.append(0)
    
    start = 0
    end = 2*K+1
    sm = sum(one_zero[start:end])
    ans = sm
    while end < len(one_zero)*2:
        sm = sm - sum(one_zero[start:start+2]) + sum(one_zero[end:end+2])
        ans = max(ans,sm)
        start += 2
        end += 2

    print(ans)

if __name__ == '__main__':
    solve()