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.



Sample input:
5 1
00010


Sample output:
4

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
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:  # groupはイテレータ。list(group)でリスト化
            runlen.append(len(list(group)))
            cnt += 1
        if flag:
            runlen.append(0)
        if cnt == 1:
            return N

        runlen = [0] + runlen
        # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
        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()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
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 # and False
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)
#ddprint(seq)
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,K = map(int,input().split())
S = list(input())[:-1]
def rle(s):#計算量N
    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 #最大2N文字
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
cnt01 = []
for i,s in enumerate(S):
    if i == 0:
        if s == "0":
            cnt01.append([1,0])
        cnt01.append([s,1])
    else:
        if cnt01[-1][0] == s:
            cnt01[-1][1] += 1
        else:
            cnt01.append([s,1])
if len(cnt01) <= 2*K+1:
    ans = sum([cnt[1] for cnt in cnt01])
    print(ans)
    exit()
else:
    ans = [sum([cnt[1] for cnt in cnt01[0:2*K+1]])]
    pos = 2
    while True:
        temp = ans[-1] - cnt01[pos-2][1] - cnt01[pos-1][1]
        if len(cnt01)-1 >= (pos + 2*K -1):
            temp += cnt01[pos+2*K-1][1]
        else:
            break
        if len(cnt01)-1 >= (pos + 2*K):
            temp += cnt01[pos+2*K][1]
        else:
            ans.append(temp)
            break
        ans.append(temp)
        pos += 2
print(max(ans))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

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

flag = S[0]
sta = 1
lista = []
# 14 2
# 11101010110011なら
# ２回まで0の箇所を消すことができる

# 00010を['0', 1, 3], ['1', 4, 4], ['0', 5, 5]という風に整頓する
for i in range(1, N):
    if flag != S[i]:
        # flag(0か1か), sta(どこから続いているか), i(最終的にどこまで続いたか)
        lista.append([flag, sta, i])
        flag = S[i]
        sta = i + 1
lista.append([flag, sta, N])
ans = 0
np = len(lista)
for i in range(np):
    if lista[i][0] == '0':
        index = min(i + 2 * K - 1, np - 1)
        opt = lista[index][2] - lista[i][1] + 1
        ans = max(ans, opt)
    else:
        index = min(i + 2 * K, np - 1)
        opt = lista[index][2] - lista[i][1] + 1
        ans = max(ans, opt)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

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

flag = S[0]
sta = 1
lista = []
for i in range(1, N):
    if flag != S[i]:
        lista.append([flag, sta, i])
        flag = S[i]
        sta = i + 1
lista.append([flag, sta, N])
ans = 0
np = len(lista)
for i in range(np):
    if lista[i][0] == '0':
        index = min(i + 2 * K - 1, np - 1)
        opt = lista[index][2] - lista[i][1] + 1
        ans = max(ans, opt)
    else:
        index = min(i + 2 * K, np - 1)
        opt = lista[index][2] - lista[i][1] + 1
        ans = max(ans, opt)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, S: str):
    d = []  # type: List[int]
    i = 0
    while True:
        r = 0
        while i < N and S[i] == "1":
            r += 1
            i += 1
        d.append(r)
        if i >= N:
            break
        s = 0
        while i < N and S[i] == "0":
            s += 1
            i += 1
        d.append(s)
    c = 2 * K + 1
    if c > len(d):
        print(sum(d))
        return
    dl = 0
    acc = sum(d[:c])
    ans = acc
    while dl + c + 2 <= len(d):
        acc += d[dl + c] + d[dl + c + 1] - d[dl] - d[dl + 1]
        ans = max(ans, acc)
        dl += 2
    print(ans)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    S = list(input()[:-1])
    ans = 0; rtmp = 0
    cnt = K + (S[0] == '1')
    for l in range(N):
        if cnt > 0:
            for r in range(rtmp, N):
                if r == N-1:
                    break
                if S[r] > S[r+1]:
                    cnt -= 1
                if cnt <= 0:
                    break
        rtmp = r+1
        ans = max(rtmp - l, ans)
        if l == N-1:
            break
        if S[l] < S[l+1]:
            cnt += 1

    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    s = input()

    memo = [[], []]
    if s[0] == '0':
        memo[1].append(0)
    for key, g in groupby(s):
        memo[int(key)].append(len(list(g)))
    if s[-1] == '0':
        memo[1].append(0)

    accum_zero_memo = [0]
    for elm in memo[0]:
        accum_zero_memo.append(accum_zero_memo[-1] + elm)
    accum_one_memo = [0]
    for elm in memo[1]:
        accum_one_memo.append(accum_one_memo[-1] + elm)
    
    # for elm in memo:
    #     print(elm)

    if k >= len(memo[0]):
        # 全て 1 にできる
        print(len(s))
    else:
        ans = 0
        for i in range(len(memo[0]) - k + 1):
            # sum(memo[0][i:i+k]) + sum(memo[1][i:i+k+1])
            summation = (accum_zero_memo[i+k] - accum_zero_memo[i]) + (accum_one_memo[i+k+1] - accum_one_memo[i])
            ans = max(ans, summation)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
d=[]
f=True

if "0" not in s:
  print(n)
  exit()
if s[0]=="0":
    d.append(0)
    f=False

seq=1
for i in range(1,n):
    if s[i]=="0" and not f:
        seq+=1
    elif s[i]=="0" and f:
        f=False
        d.append(seq)
        seq=1
    elif s[i]=="1" and f:
        seq+=1
    else:
        f=True
        d.append(seq)
        seq=1
    if i==n-1:
      d.append(seq)
if s[-1]=="0":
    d.append(0)
l=len(d)
res=[0]*(l+1)
res[0]=0
for i in range(1,l+1):
    res[i]=res[i-1]+d[i-1]
ans=1
for i in range(1,l+1):
    if i%2==1:
        continue
    if 2*k+i-1>l:
      a=res[l]-res[i-2]
    else:
      a=res[2*k+i-1]-res[i-2]
    if a>ans:
        ans=a
print(ans)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
s=SI()
ze=[]
on=[]

if s[0]=="0":
    state="ze"
    sq=1
    on.append(0)
else:
    state="on"
    sq=1
    
for i in range(1,n):
    u=s[i]
    if state=="ze":
        if u=="0":
            sq+=1
        else:
            ze.append(sq)
            sq=1
            state="on"
            
        
    elif state=="on":
        if u=="1":
            sq+=1
        else:
            on.append(sq)
            sq=1
            state="ze"
if state=="on":
    on.append(sq)
elif state=="ze":
    ze.append(sq)
if len(ze)<k:
    print(n)
    sys.exit()
if s[-1]=="0":
    on.append(0)
#print(on)
#print(ze)
u=len(on)

smz=[0 for i in range(u-k)]
smo=[0 for i in range(u-k)]
for i in range(k):
    smz[0]+=ze[i]
for i in range(k+1):
    smo[0]+=on[i]
#print(smo)
#print(smz)
for i in range(u-k-1):
    smz[i+1]=smz[i]-ze[i]+ze[i+k]
for i in range(u-k-1):
    smo[i+1]=smo[i]-on[i]+on[i+k+1]
#print(smo)
#print(smz)
mx=0
for i in range(u-k):
    val=smo[i]+smz[i]
    if val>mx:
        mx=val
print(mx)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
from itertools import groupby
a=[len(list(j)) for i,j in groupby(s)]
if s[0]=='0':
  a=[0]+a
if s[n-1]=='0':
  a=a+[0]
w=2*k+1
if len(a)<=w:
  print(n)
  exit()
m=sum(a[:w])
x=m
for i in range(2,len(a)-2*k,2):
  m=m-a[i-1]-a[i-2]+a[i+w-1]+a[i+w-2]
  x=max(x,m)
print(x)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s+="6"
c=0
l=[]
zcnt=0
for i in range(n):
  if s[i]!=s[i+1]:
    if s[i]=="0":zcnt+=1
    l.append((s[i],i+1-c))
    c=i+1
L=len(l)
sl=[0]*(L+1)
for i in range(L):
    sl[i+1]=sl[i]+l[i][1]
if k>=zcnt:print(n);exit()
ans=0
if s[0]=="0":
    for i in range(zcnt-k+1):
        ans=max(ans,sl[min(L,2*k+i*2)]-sl[max(0,i*2-1)])
    print(ans)
else:
    for i in range(zcnt-k+1):
        ans=max(ans,sl[min(L,2*k+i*2+1)]-sl[i*2])
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

N,K = (int(x) for x in input().split())
S = input()
count = []
d = deque(list(S))
now = d.popleft()
cum = 1
for i in range(len(S)-1):
    popped = d.popleft()
    if popped == now:
        cum += 1
    else:
        count.append(cum)
        now = popped
        cum = 1
count.append(cum)
cs = np.array(count).cumsum()
block = len(count)
if S[0] == '0':
    zeros = int(np.ceil(block/2))
    if K >= zeros:
        print(len(S))
    else:
        m = cs[K*2-1]
        if S[-1] == '1':
            for i in range(1,zeros-K+1):
                m = max(m,cs[2*i+2*K-1]-cs[2*(i-1)])
        else:
            for i in range(1,zeros-K):
                m = max(m,cs[2*i+2*K-1]-cs[2*(i-1)])
            m = max(m,cs[-1]-cs[-2*K-1])
        print(m)
else:
    zeros = int(np.floor(block/2))
    if K >= zeros:
        print(len(S))
    else:
        m = cs[2*K]
        if S[-1] == '1':
            for i in range(1,zeros-K+1):
                m = max(m,cs[2*i+2*K]-cs[2*i-1])
        else:
            for i in range(1,zeros-K):
                m = max(m,cs[2*i+2*K]-cs[2*i-1])
            m = max(m,cs[-1]-cs[-2*K-1])
        print(m)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    S=input()
    lis=[0]
    for i in range(1,n):
        if S[i-1]!=S[i]:
            lis.append(i)
    lis.append(n)
    len_lis=len(lis)
    ans=[]
    for i in range(len_lis-1):
        if S[lis[i]]=='0':
            ans.append(lis[min(i+2*k,len_lis-1)]-lis[i])
        else:
            ans.append(lis[min(i+2*k+1,len_lis-1)]-lis[i])
    print(max(ans))

if __name__=='__main__':
    main()

Submission status: Accepted

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

zero_list = []
for i in range(N):
    if S[i] == '0':
        if i > 0 and S[i - 1] == '0':
            zero_list[-1][0] += 1
            zero_list[-1][2] += 1
        else:
            zero_list.append([1, i, i])
            
if len(zero_list) <= K:
    ans = N
else:
    zero_c_max = zero_list[K][1]
    l = 0
    r = zero_list[K][1] - 1
    for j in range(1, len(zero_list) - K + 1):
        l = zero_list[j - 1][2] + 1
        if j + K < len(zero_list): 
            r = zero_list[j + K][1] - 1
        else:
            r = N - 1
        if (r - l) + 1 > zero_c_max:
            zero_c_max = (r - l) + 1
    
    ans = zero_c_max
    
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s+="2"
lst=[]
ruiseki=[0]
i=0;cnt=1;ans=0
while True:
    if s[i]==s[i+1]:
        i+=1
        cnt+=1
    else:
        lst.append(cnt)
        ruiseki.append(ruiseki[-1]+cnt)
        i+=1
        cnt=1 
    if i==n:
        break
if s[0]=="1":
    flag=True
    if 2*k>=len(lst)-1:
        print(ruiseki[-1])
        exit()
else:
    flag=False
    if 2*k>=len(lst):
        print(ruiseki[-1])
        exit()

for i in range(1,len(lst)):
    if flag:
        ans=max(ans,ruiseki[min(i+2*k,len(lst))]-ruiseki[i-1])
        flag=False
    else:
        ans=max(ans,ruiseki[min(i+2*k-1,len(lst))]-ruiseki[i-1])
        flag=True
print(ans)

Submission status: Accepted

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

ns = []
now_num = s[0]
cnt = 0
for i in range(n):
    if now_num == s[i]:
        cnt += 1
    else:
        ns.append((now_num, cnt))
        now_num = s[i]
        cnt = 1
ns.append((now_num, cnt))
len_ns = len(ns)
pre = [0] * (len_ns + 1)
for i in range(len_ns):
    pre[i + 1] = pre[i] + ns[i][1]

ans = 1
for i in range(len_ns - 2*k + 1):
    temp = pre[i + 2*k] - pre[i]
    if i > 0 and ns[i - 1][0] == '1':temp += ns[i - 1][1]
    if i + 2*k < len_ns and ns[i + 2*k][0] == '1':temp += ns[i + 2*k][1]
    if temp > ans:ans = temp
print(ans if len_ns - 2*k + 1 > 0 else len(s))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement, groupby
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

n, k = Is()
s = S()
A = []  # group count of 1, 0 (1, 0, 1, 0, ... , 1)
if s[0] == "0":
    A.append(0)
for key, value in groupby(s):
    A.append(len(list(value)))
if s[-1] == "0":
    A.append(0)
# print(A)
ans = 0
w = 2*k+1
tmp = sum(A[:w])
ans = max(ans, tmp)
for i in range(w+1, len(A)+1, 2):
    tmp -= A[i-1-w] + A[i-w]
    tmp += A[i-1] + A[i]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
hand_list = []
for i in range(n):
    if i == 0:
        hand_list.append(i)
    else:
        if s[i] != s[i - 1]:
            hand_list.append(i)
hand_list.append(n)

ans_list = []
if len(hand_list) > 2 * k:
    for i in range(len(hand_list) - 2 * k):
        if s[hand_list[i]] == '1':
            ans = hand_list[min(i + 2 * k + 1, len(hand_list)-1)] - hand_list[i]
        else:
            ans = hand_list[i + 2 * k] - hand_list[i]
        ans_list.append(ans)
else:
    ans_list.append(n)
print(max(ans_list))

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split(' '))
S = input()
arr = []
idx = 0

while idx < N:
    start = idx
    while idx + 1 < N and S[idx] == S[idx + 1]:
        idx += 1
    if S[start] == '0':
        arr.append(-(idx - start + 1))
    else:
        arr.append(idx - start + 1)
    idx += 1

if arr[0] < 0:
    arr = [0] + arr
if arr[-1] > 0:
    arr.append(0)

l, r = 0, 0     # [l, r)
ans, tmp = max(arr), 0
while l < len(arr) and r < len(arr):
    tmp += abs(arr[r])
    r += 1

    if r - l > 2 * K + 1:
        tmp -= arr[l] - arr[l + 1]
        l += 2

    if r - l <= 2 * K + 1:
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else [0,0]
cnt,num=0,S[0]
for i in range(n+1):
    if num==S[i]:
        cnt +=1
    else:
        A.append(cnt)
        cnt=1
        num=S[i]

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

Submission status: Accepted

Solution code:
def main():
    N, K = list(map(int, input().split(' ')))
    S = input()
    # Find 0->1 / 1->0 patterns
    zero_one_indices = [0]
    one_zero_indices = [0] if S[0] == '0' else []
    before_c = None
    for i, c in enumerate(S):
        if (before_c, c) == ('0', '1'):
            zero_one_indices.append(i)
        elif (before_c, c) == ('1', '0'):
            one_zero_indices.append(i)
        before_c = c
    max_length = 0
    for k in range(len(zero_one_indices)):
        if k + K < len(one_zero_indices):
            # 1_seq + [0_seq, 1_seq] * K
            length = one_zero_indices[k + K] - zero_one_indices[k]
        else:
            length = N - zero_one_indices[k]
        max_length = max([length, max_length])
    print(max_length)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
row = []
count = 1
flag = S[0]
for i in range(1,N):
    if S[i] != flag:
        row.append([count,flag])
        count = 1
        flag = S[i]
    else:
        count += 1
row.append([count,flag])
inst = 0
ans,temp = 0,0
left,right = 0,0
for i in range(len(row)):
    if row[i][1] == "1":
        temp += row[i][0]
    else:
        inst += 1
        if inst <= K:
            temp += row[i][0]
        else:
            temp -= row[left][0]
            if row[left][1] == "1":
                temp -=row[left+1][0]
                left += 1
            temp += row[i][0]
            left += 1
    ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
def ranlength(A):
    num = list(A)
    count = 1
    result = ''
    table = []
    for i in range(len(num)):
        try:
            if num[i] == num[i+1]:
               count = count + 1
            else:
                result += str(num[i]) + str(count)
                table.append(count)
                count = 1
        except:
            result += str(num[i]) + str(count)
            table.append(count)
    return(table)
    
N,K=map(int,input().split())
S=input()

RL=ranlength(S)
if S[0]=='0':
    RL=[0]+RL
if S[-1]=='0':
    RL.append(0)

#しゃくとり法
cnt=RL[0]
ans=RL[0]
for i in range(len(RL)):
    if i%2==0 and i>=2:
        cnt+=RL[i]
        cnt+=RL[i-1]
        if i>=K*2+2:
            cnt-=RL[i-(K*2+1)]
            cnt-=RL[i-(K*2+2)]
        ans=max(ans,cnt)
        #print(cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    S = input()

    # 1の個数と0の個数を交互に記録
    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
    nums.append(0) if S[-1] == "0" else None

    # 累積和
    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)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=input()+"*"
A=[0,0] if S[0]=="0" else [0]
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

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