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:
N,K=map(int,input().split())
S=[int(i) for i in input()]
ans,r,l,k=0,0,0,K
while r<N:
  while k>0:
    while l<N and S[l]==1:
      l+=1
    while l<N and S[l]==0:
      l+=1
    k-=1
  while l<N and S[l]==1:
    l+=1
  ans=max(ans,l-r)
  while r<N and S[r]==1:
    r+=1
  while r<N and S[r]==0:
    r+=1
  k=1
print(ans)

Submission status: Accepted

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

S_zero={}
S_zero_group = 0
s_befor = ''
for s_idx,s in enumerate(S):
    if s != s_befor:
        if s == '0':
            S_zero_group += 1
            S_zero[S_zero_group] = [s_idx-1]
        elif s == '1':
            if S_zero_group in S_zero.keys():
                S_zero[S_zero_group].append(s_idx)
            
    s_befor = s
    
if S[-1] == '0':
    S_zero[S_zero_group].append(N)
    
if S_zero_group <= K:
    ans_ = N
else:   
    ans_=0
    for g_s in range(1,S_zero_group-K+2):
        g_e = g_s + K - 1
#         print('====',g_s,g_e)
        s = 0
        e = N-1

        if g_s != 1:
            s = S_zero[g_s-1][1]
        if g_e != S_zero_group:
            e = S_zero[g_e+1][0]

        ans= e-s+1
        if ans > ans_:
            ans_=ans

print(ans_)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
l=[["1",0]]
for i in s:
    if l[-1][0]==i:
        l[-1][1]+=1
    else:
        l.append([i,1])
if l[-1][0]=="0":
    l.append(["1",0])
e=[0]
for i in range(len(l)):
    e.append(e[i]+l[i][1])
ans=0 if k<len(l)//2 else e[-1]
for i in range(2*k-1,len(l),2):
    ans=max(ans,e[i+2]-e[i-2*k+1])
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
ss = []
ss.append(0)
for i in range(n-1):
  a = s[i]
  if a == s[i+1]:
    continue
  ss.append(i+1)
ss.append(n)

ans = 0
for i in range(len(ss)):
  p = ss[i]
  if p == n:
    break
  if s[p] == "0":
    ans = max(ans, ss[min(2 * k + i, len(ss) - 1)] - ss[i])
  else:
    ans = max(ans, ss[min(2 * k + 1 + i, len(ss) - 1)] - ss[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import groupby, accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = [len(list(g)) for _, g in groupby(S)]
    keys = [k for k, _ in groupby(S)]
    csum = [0]
    csum.extend(accumulate(vec))

    ans = 0
    for i in range(len(vec)):
        if keys[i] == '0':
            if i == 0:
                n = 2 * K
            else:
                continue
        else:
            n = 2 * K + 1

        if ans < csum[min(i + n, len(csum) - 1)] - csum[i]:
            ans = csum[min(i + n, len(csum) - 1)] - csum[i]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(map(int, input()))
cnt = 0
ans = 0
start = 0
for i in range(n):
    if s[i] == 0 and (i == 0 or s[i - 1] == 1):
        cnt += 1
    
    if cnt == k + 1:
        while True:
            start += 1
            if s[start - 1] == 0 and s[start] == 1:
                break
        cnt -= 1
    ans = max(ans, i - start + 1)

print(ans)

Submission status: Accepted

Solution code:
import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    s=input()

if n==1:
    print(1)
    sys.exit()

ss=[]
if s[0]=="1" and s[1]=="1":
    zcnt=1
elif s[0]=="1" and s[1]=="0":
#    ss.append(1)
    zcnt=1
elif s[0]=="0" and s[1]=="0":
    ss.append(0)
    zcnt=1
elif s[0]=="0" and s[1]=="1":
    ss.append(0)
#    ss.append(1)
    zcnt=1

for i in range(1,n-1):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        zcnt=1
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        zcnt=1
        
for i in range(n-1,n):
    if s[i]=="0" and s[i-1]=="0":
        zcnt+=1
        ss.append(zcnt)
        ss.append(0)
    elif s[i]=="0" and s[i-1]=="1":
        ss.append(zcnt)
        ss.append(1)
        ss.append(0)
    elif s[i]=="1" and s[i-1]=="1":
        zcnt+=1
        ss.append(zcnt)
    elif s[i]=="1" and s[i-1]=="0":
        ss.append(zcnt)
        ss.append(1)

#print(ss)

if len(ss)<=2*k+1:
    print(n)
    sys.exit()

smax=0
for i in range(2*k+1):
    smax+=ss[i]
#print(smax)    
ssum=smax    
kk=2*k
for i in range(2,len(ss)-kk,2):
    ssum=ssum-ss[i-2]-ss[i-1]+ss[i+kk-1]+ss[i+kk]
    smax=max(smax,ssum)

print(smax)

Submission status: Accepted

Solution code:
from collections import *
n,k=map(int,input().split())
s=input()
q=deque()
tt=0
f=False
t=0
ans=0
tmp=0
for i in range(n):
    if f:
        if s[i]=="0":
            tmp+=1
            tt+=1
            if tmp>ans:
                ans=tmp
        else:
            q.append(tt)
            f=False
            tt=1
            tmp+=1
            if tmp>ans:
                ans=tmp

    elif f==False:
        if s[i]=="1":
            tmp+=1
            tt+=1
            if tmp>ans:
                ans=tmp
        else:
            t+=1
            f=True
            if t>k:
                d=q.popleft()
                tmp-=d
            tmp+=1
            tt+=1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input().rstrip()
s0 = S[0]
cnt = 1
d = []
for s in S[1:]+"2":
    if s == s0:
        cnt += 1
    else:
        d.append(cnt)
        cnt = 1
    s0 = s
if S[0] == "0":
    d = [0] + d
if S[-1] == "0":
    d += [0]
L = len(d)
if L//2 < K:
    print(sum(d))
else:
    S = sum(d[:2*K+1])
    res = S
    for i in range(2,L-2*K+1,2):
        S = S - d[i-2] - d[i-1] + d[2*K+i-1] + d[2*K+i]
        res = max(S,res)
    print(res)

Submission status: Accepted

Solution code:

# spent 4 hrs for this question why i am noob:(
# group all the consecutive elements and keep a count of each group and type of group whether it's one or zero
# After grouping all the same elements the string would alternate for 0 and 1
# suppose if u are current group of 1 then u need to chose next 2*k group as 0101,010101,01010101 as k is 2, 3, 4 respectively 
# u can flip every consecutive zero's in the above
# suppose if the current group start's with 0 then u need to choose next 2*k-1 groups as 101 , 10101 as k is 2 , 3 respectively
# u can flip every consecutive zero's 
def main():
	n , k = map(int , input().split())
	hd = input()
	grp=[]
	if hd[0]=='1':
		grp = [[0,0]]
	else:
		grp=[[0,0]]
	cnt =1
	for i in range(1, len(hd)):
		if hd[i]==hd[i-1]:
			cnt = cnt+1
		else:
			grp.append([cnt,i])
			cnt = 1
	grp .append([cnt , len(hd)-1])
	pre = [0 for i in range(0 , len(grp)+9)]
	pre[0]=grp[0][0]
	for i in range(1, len(grp)):
		pre[i]=pre[i-1]+grp[i][0]
	ans = 0
	for i in range(0 , len(grp)):
		if hd[grp[i][1]]=='0':
			rgt = min(i+2*k, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		else:
			rgt = min(i+2*k+1, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		if rgt==len(grp)-1:
			break
	print(ans)
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:

# spent 4 hrs for this question why i am noob:(
def main():
	n , k = map(int , input().split())
	hd = input()
	grp=[]
	if hd[0]=='1':
		grp = [[0,0]]
	else:
		grp=[[0,0]]
	cnt =1
	for i in range(1, len(hd)):
		if hd[i]==hd[i-1]:
			cnt = cnt+1
		else:
			grp.append([cnt,i])
			cnt = 1
	grp .append([cnt , len(hd)-1])
	pre = [0 for i in range(0 , len(grp)+9)]
	pre[0]=grp[0][0]
	for i in range(1, len(grp)):
		pre[i]=pre[i-1]+grp[i][0]
	ans = 0
	for i in range(0 , len(grp)):
		if hd[grp[i][1]]=='0':
			rgt = min(i+2*k, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		else:
			rgt = min(i+2*k+1, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		if rgt==len(grp)-1:
			break
	print(ans)
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
def main():
	n , k = map(int , input().split())
	hd = input()
	grp=[]
	if hd[0]=='1':
		grp = [[0,0]]
	else:
		grp=[[0,0]]
	cnt =1
	for i in range(1, len(hd)):
		if hd[i]==hd[i-1]:
			cnt = cnt+1
		else:
			grp.append([cnt,i])
			cnt = 1
	grp .append([cnt , len(hd)-1])
	pre = [0 for i in range(0 , len(grp)+9)]
	pre[0]=grp[0][0]
	for i in range(1, len(grp)):
		pre[i]=pre[i-1]+grp[i][0]
	ans = 0
	for i in range(0 , len(grp)):
		if hd[grp[i][1]]=='0':
			rgt = min(i+2*k, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		else:
			rgt = min(i+2*k+1, len(grp)-1)
			ans = max(ans, pre[rgt]-pre[i])
		if rgt==len(grp)-1:
			break
	print(ans)
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
change=[0]
for i in range(len(S)-1):
  if S[i]!=S[i+1]:
    change.append(i+1)
change.append(N)
r=len(change)
X=[]
for i in range(r-1):
  if S[change[i]]=='0':
    a=min(i+2*K,r-1)
    X.append(change[a]-change[i])
  else:
    a=min(i+2*K+1,r-1)
    X.append(change[a]-change[i])
print(max(X))

Submission status: Accepted

Solution code:

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

q = [(S[0], 0)]
cur = S[0]
for i in range(1, N):
    if S[i] != cur:
        q.append((S[i], i))
        cur = S[i]

lim = len(q)
ans = []
for i in range(lim):
    if q[i][0] == "0":
        j = i + 2 * K
    else:
        j = i + 2 * K + 1

    if j < lim:
        ans.append(q[j][1] - q[i][1])
    else:
        ans.append(N - q[i][1])

print(max(ans))

Submission status: Accepted

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

lst = []
b = S[0]
if b == '0':
  lst.append(0)
  
cnt = 1
for i in range(1, len(S)):
  if b != S[i]:
    lst.append(cnt)
    cnt = 1
  else:
    cnt += 1
  b = S[i]
lst.append(cnt)

if b == '0':
  lst.append(0)

l = len(lst)
if K >= l//2:
  print(N)
else:
  tmp = sum(lst[:2*K+1])
  rlt = tmp
  for i in range(2,l-2*K,2):
    tmp += lst[2*K+i-1] + lst[2*K+i] - lst[i-1] - lst[i-2]
    rlt = max(rlt, tmp)
  print(rlt)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
s = input()
C = []
x = s[0]
if x == '0':
    C.append(0)
cnt = 1
for i in range(1, n):
    if x != s[i]:
        C.append(cnt)
        cnt = 1
        x = s[i]
    else:
        cnt += 1
C.append(cnt)
if x != '1':
    C.append(0)
C = [0] + list(accumulate(C))
m = len(C)
if m < 2*k+1:
    print(C[-1])
else:
    ans = 0
    for i in range(2*k+1, m, 2):
        ans = max(ans, C[i] - C[i-(2*k+1)])
    print(ans)

Submission status: Accepted

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

start = []
end = []
flag = True

m = 0

for i in range(n):
    if flag and s[i] == "1":
        flag = False
        start.append(i)
    elif not flag and s[i] == "0":
        flag = True
        end.append(i-1)

if len(start) <= 0 or start[0] != 0:
    start = [0] + start
    end = [0] + end

end.append(n-1)

#print(start, end)

if len(end) <= k:
    print(n)
else:
    m = 0
    for i in range(len(end)-k):
        m = max(m, end[i+k] - start[i] + 1)
    print(m)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
a=[0]
for i in range(1,N):
  if S[i-1]!=S[i]:
    a.append(i)
a.append(N)
l=len(a)
ans=[]
for i in range(l-1):
  if S[a[i]]=='0':
    ans.append(a[min(i+2*K,l-1)]-a[i])
  else:
    ans.append(a[min(i+2*K+1,l-1)]-a[i])
print(max(ans))

Submission status: Accepted

Solution code:
def rle(string):
    _rle_str = string[0]
    _rle_cnt = 1
    _ans_l = []
    for _i in range(1, len(string)):
        if _rle_str == string[_i]:
            _rle_cnt += 1
        else:
            _ans_l.append([_rle_str, _rle_cnt])
            _rle_str = string[_i]
            _rle_cnt = 1
    _ans_l.append([_rle_str, _rle_cnt])
    return _ans_l

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

rs=rle(s)

if rs[0][0]=="0":
    cnt=1
    wa=rs[0][1]
    r=1
    l=0
else:
    cnt=0
    wa=0
    r=0
    l=0

ans=-1

if len(rs)==1:
    print(rs[0][1])
    exit()

while r<len(rs):
    if cnt==k and rs[r][0]=="0":
        if rs[l][0]=="0":
            wa-=rs[l][1]
            cnt-=1
        else:
            wa-=rs[l][1]
        l+=1

    elif cnt<=k:
        if rs[r][0]=="0":
            cnt+=1
            wa+=rs[r][1]
        else:
            wa+=rs[r][1]
        r+=1
        ans=max(ans, wa)

    else:
        if rs[l][0]=="0":
            wa-=rs[l][1]
            cnt-=1
        else:
            wa-=rs[l][1]
        l+=1

print(ans)

Submission status: Accepted

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

def rle(string):
    _rle_str = string[0]
    _rle_cnt = 1
    _ans_l = []
    for _i in range(1, len(string)):
        if _rle_str == string[_i]:
            _rle_cnt += 1
        else:
            _ans_l.append([_rle_str, _rle_cnt])
            _rle_str = string[_i]
            _rle_cnt = 1
    _ans_l.append([_rle_str, _rle_cnt])
    return _ans_l

rle_s=rle(s)

ans=-1

left=0
wa=0

if rle_s[0][0]=="0":
    cnt=1
    wa=rle_s[0][1]
    right=1
else:
    cnt=0
    right=0

if len(rle_s)==1 and k>=1:
    print(rle_s[0][1])
    exit()

while right<len(rle_s):
    # print(right, left, wa, cnt)
    if cnt==k:
        if rle_s[right][0]=="0":
            if rle_s[left][0]=="0":
                wa-=rle_s[left][1]
                cnt-=1
            else:
                wa-=rle_s[left][1]
            left+=1

        else:
            wa+=rle_s[right][1]
            right+=1
            ans=max(ans, wa)

    elif cnt<k:
        if rle_s[right][0]=="0":
            cnt+=1
            wa+=rle_s[right][1]
        else:
            wa+=rle_s[right][1]
        right+=1
        ans=max(ans, wa)

    else:
        if rle_s[left][0]=="0":
            wa-=rle_s[left][1]
            cnt-=1
        else:
            wa-=rle_s[left][1]
        left+=1

print(ans)

Submission status: Accepted

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

beforeChar = S[0]
sectionList = []
count = 0
for i in range(N):
    if S[i] == beforeChar:
        count += 1
    else:
        sectionList.append([beforeChar, count])
        count = 1
        beforeChar = S[i]
sectionList.append([beforeChar, count])

sectionNumber = len(sectionList)
zeroSectionNumber = 0
oneSectionNumber = 0
if sectionNumber % 2 == 0:
    zeroSectionNumber = sectionNumber // 2
    oneSectionNumber = sectionNumber // 2
else:
    if sectionList[0][0] == '0':
        zeroSectionNumber = sectionNumber // 2 + 1
        oneSectionNumber = sectionNumber // 2
    else:
        zeroSectionNumber = sectionNumber // 2
        oneSectionNumber = sectionNumber // 2 + 1

if zeroSectionNumber <= K:
    print(N)
    exit()

sumLengthList = []
sumLength = 0
for i in range(sectionNumber):
    sumLength += sectionList[i][1]
    sumLengthList.append(sumLength)

def sumLengthByRange(rangeStartSection, rangeEndSection):
    if rangeStartSection == 0:
        return sumLengthList[rangeEndSection]
    else:
        return sumLengthList[rangeEndSection] - sumLengthList[rangeStartSection - 1]

startSection = 0
endSection = 0
lengthList = []
if sectionList[0][0] == '1':
    endSection = K * 2
else:
    endSection = K * 2 - 1
    lengthList.append(sumLengthByRange(startSection, endSection))
    startSection = 1
    endSection += 2
while endSection < sectionNumber:
    lengthList.append(sumLengthByRange(startSection, endSection))
    startSection += 2
    endSection += 2
if sectionList[-1][0] == '0':
    endSection -= 1
    lengthList.append(sumLengthByRange(startSection, endSection))

print(max(lengthList))

Submission status: Accepted

Solution code:
#--初期の並びを圧縮表示,逆立ち、正立を目印--#
import sys,math,collections,itertools
input = sys.stdin.readline

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

stand = []
s_or_r = []

s_bf = '.'
cnt = 0
for i in range(N):
    if s_bf != S[i] and i != 0:
        stand.append(cnt)
        s_or_r.append(s_bf)
        cnt = 1
        s_bf=S[i]
    else:
        cnt += 1
        s_bf =S[i]
stand.append(cnt)
s_or_r.append(s_bf)


#--正立kまで許容して足す。maxが答え
if s_or_r.count('0')<=K:
    print(len(S))
    exit()
#--成形==#
if s_or_r[0]=='0':
    s_or_r=['1']+s_or_r
    stand = [0]+stand
if s_or_r[-1]=='0':
    s_or_r.append('1')
    stand.append(0)
#初期条件#
tmp = sum(stand[0:2*K+1])
ans = tmp
for i in range(2,len(stand)-2*K,2):
    tmp += -(stand[i-1]+stand[i-2])+stand[i+2*K-1]+stand[i+2*K]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
def RLE(s):
    rle = []
    pre = "1"
    cnt = 0
    for c in s:
        if c == pre:
            cnt += 1
        else:
            rle.append(cnt)
            pre = c
            cnt = 1
    rle.append(cnt)
    return rle

n, k = map(int, input().split())
s = input()
a = RLE(s)
n = len(a)
a.append(0)
now = sum(a[:2 * k + 1])
ans = now
for i in range(2 * k + 1, n, 2):
    now += a[i] + a[i + 1] - a[i - 2 * k - 1] - a[i - 2 * k]
    ans = max(ans, now)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    n, k = mi()
    s = input()
    a = [0]
    for i in range(1, n):
        if s[i]!= s[i-1]:
            a.append(i)
    a.append(n)
    ans = 0
    i, e = 0, 0
    m = len(a)
    for i in range(m):
        e = i+2*k
        if s[a[i]] == '1':
            e += 1
        e = min(e, m-1)
        ans = max(ans, a[e]-a[i])
        if e == m-1:
            break
    print(ans)
    



    
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(map(int,list(input())))
x = [-1]
for i in range(n-1):
    if s[i] != s[i+1]:
        x.append(i)
x.append(n-1)
t = len(x)
ans = 1

for i in range(t-1):
    if i%2 == s[0]:
        ans = max(ans,x[min(t-1,i+2*k)]-x[i])
    else:
        ans = max(ans,x[min(t-1,i+2*k+1)]-x[i])

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(v):
    return sum(1 for _ in v)


def solve():
    N, K = read_ints()
    S = input()
    counts = deque([])
    zeroes = 0
    total = 0
    max_total = 0
    for k, v in groupby(S):
        if k == '0':
            zeroes += 1
        this_count = ilen(v)
        total += this_count
        counts.append((k, this_count))
        while zeroes > K:
            k, count = counts.popleft()
            total -= count
            if k == '0':
                zeroes -= 1
        max_total = max(max_total, total)
    return max_total


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

# 1の個数, 0の個数, 1の個数, ..., 1の個数
list10 = []
head = S[0]
cnt = 0

# 左端の1の数
if S[0] == "0":
    list10.append(0)

for i in range(N):
    if S[i] == head:
        cnt += 1
    else:
        list10.append(cnt)
        cnt = 1
        head = S[i]

    if i == N - 1:
        list10.append(cnt)

# 右端の1の数
if S[-1] == "0":
    list10.append(0)

# print(list10)

ans = 0

cumsum = [0]
for li in list10:
    cumsum.append(cumsum[-1] + li)
# print(cumsum)

for j in range(1, len(cumsum), 2):
    h = j
    t = min(j + 2 * K, len(cumsum) - 1)
    ans = max(ans, cumsum[t] - cumsum[max(h - 1, 0)])
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    S = SS()

    # 1の塊の長さと位置を調べる
    l = []
    if S[0] == '1':
        l.append(0)
    # 先端0の場合、一番左に長さ0の1の塊があるとする
    else:
        l.append(0)
        l.append(0)
    for i in range(N - 1):
        if S[i] == '0' and S[i+1] == '1':
            l.append(i + 1)
        elif S[i] == '1' and S[i+1] == '0':
            l.append(i + 1)
    if S[-1] == '1':
        l.append(N)
    # 後端0の場合、一番右に長さ0の1の塊があるとする
    else:
        l.append(N)
        l.append(N)

    ans = 0
    # 0の塊がK個以下の場合
    if len(l) // 2 - 1 < K:
        ans = N
    # 1の塊をK+1個くっつけた場合の長さを調べる
    else:
        for i in range(len(l) // 2 - K):
            ans = max(l[2*i+2*K+1] - l[2*i], ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    S = SS()

    # 1の塊の長さと位置を調べる
    l = []
    if S[0] == '1':
        l.append(0)
    else:
        l.append(0)
        l.append(0)
    for i in range(N - 1):
        if S[i] == '0' and S[i+1] == '1':
            l.append(i + 1)
        elif S[i] == '1' and S[i+1] == '0':
            l.append(i + 1)
    if S[-1] == '1':
        l.append(N)
    else:
        l.append(N)
        l.append(N)
    # print(S)
    # print(l)

    # 1の塊をK+1個くっつけた場合の長さを調べる
    ans = 0
    if len(l) // 2 - 1 < K:
        ans = N
    else:
        for i in range(len(l) // 2 - K):
            ans = max(l[2*i+2*K+1] - l[2*i], ans)

    # 端の0を逆立ちさせた場合
    # if S[0] == '0':
    #     ans = max(l[2*K-1], ans)
    # if S[-1] == '0':
    #     ans = max(N - l[len(l)-2*K], ans)
    
    # 全部1だった場合(塊の間も無いし端の0もない)
    # if l == [0, N]:
    #     ans = N

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

ans, lennum = num[1], len(num)
for i in range((s[0] == '1') + 1, lennum, 2):
    r, l = max(i - 2, 0), min(i + 2 * k - 1, lennum - 1)
    ans = max(ans, num[l] - num[r])
print(ans)

Submission status: Accepted

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

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

ans, lennum = num[1], len(num)
for i in range((s[0] == '1') + 1, lennum, 2):
    r, l = max(i - 2, 0), min(i + 2 * k, lennum) - 1
    ans = max(ans, num[l] - num[r])
print(ans)

Submission status: Accepted

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

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

ans, lennum = num[1], len(num)
for i in range((s[0] == '1') + 1, lennum, 2):
    tmp = num[min(i - 1 + 2 * k, lennum - 1)] - num[max(i - 2, 0)]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        ans = 0
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                pass # ここから何か書いてね

def solve():
    n, k = getList()
    S = getS()
    ren = []
    if S.startswith("0"):
        ren.append(0)

    ctmp = ""
    ntmp = 0
    for c in S:
        if ctmp != "" and ctmp != c:
            ren.append(ntmp)
            ntmp = 1
            ctmp = c
        else:
            ntmp += 1
            ctmp = c
    ren.append(ntmp)
    if S.endswith("0"):
        ren.append(0)

    # print(ren)
    for i in range(len(ren) - 1):
        ren[i+1] += ren[i]

    if 2 * k + 1 >= len(ren):
        print(ren[-1])
        return
    # print(ren)
    off = 0
    ans = 0
    while True:
        if off == 0:
            ans = max(ans, ren[2 * (off + k)])
        else:
            ans = max(ans, ren[2 * (off + k)] - ren[2 * off - 1])

        off += 1
        if 2 * (off + k) >= len(ren):
            print(ans)
            return

def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n,k = map(int,ipt().split())
    s = input()
    nms = []
    if s[0] == "0":
        nms.append(0)
        ps = "0"
    else:
        ps = "1"
    st = 1
    for i in s[1::]:
        if i == ps:
            st += 1
        else:
            nms.append(st)
            st = 1
            ps = i
    nms.append(st)
    if s[-1] == "0":
        nms.append(0)
#    print(nms)
    ln = len(nms)
    sm = sum(nms[:min(2*k+1,ln):])
    ma = sm
    for i in range(2*k+2,ln,2):
        sm += nms[i]+nms[i-1]-nms[i-2*k-2]-nms[i-2*k-1]
        if ma < sm:
            ma = sm
    print(ma)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s=list(input())

border = [0]

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

border_count = len(border)

ans = 0

for i in range(border_count):
    if s[border[i]] == '0':
        block_1 = i+k*2
    else:
        block_1 = i+k*2+1
    #print(block_1, border)
    if block_1 < border_count:
        ans = max(ans, border[block_1]-border[i])
    else:
        ans = max(ans, n-border[i])
print(ans)

Submission status: Accepted

Solution code:
#ABC124 D-Handstand
n,k = map(int,input().split())
s = []
count = 0
last = 1
for i in input():
    if i=='1':
        if last==1:
            count+=1
        else:
            s.append(count)
            count=1
        last = 1
    else:
        if last==0:
            count+=1
        else:
            s.append(count)
            count=1
        last = 0
s.append(count)
if last==0:
    s.append(0)

k = min(k,len(s)//2)
ans = 0

for j in range(len(s)//2-k+1):
    if j==0:
        now = sum(s[:k*2+1])
        ans = now
    else:
        now = now-s[j*2-1]-s[j*2-2]+s[(j+k)*2]+s[(j+k)*2-1]
        ans = max(ans,now) 
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = input()
sento = 0
ketu = 0
tmp = '1'
zeroichi = []
cnt = 0

for i in range(n):
    if tmp == s[i]:
        cnt += 1
    else:
        zeroichi.append(cnt)
        cnt = 1
        tmp = s[i]

zeroichi.append(cnt)

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

if len(zeroichi) == 1:
    zeroichi.append(0)
    zeroichi.append(0)

i = 0
ans = 0
ans_list = []
j = 0
right = min(1+k*2,len(zeroichi))
left = 0

while i != right:
    ans += zeroichi[i]
    i += 1

ans_list.append(ans)

while right != len(zeroichi):
    ans -= zeroichi[left]
    ans -= zeroichi[left+1]
    ans += zeroichi[right]
    ans += zeroichi[right+1]
    ans_list.append(ans)
    left += 2
    right += 2

print(max(ans_list))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
a=[0]
for i in range(1,N):
  if S[i-1]!=S[i]:
    a.append(i)
a.append(N)
l=len(a)
ans=[]
for i in range(l-1):
  if S[a[i]]=='0':
    ans.append(a[min(i+2*K,l-1)]-a[i])
  else:
    ans.append(a[min(i+2*K+1,l-1)]-a[i])
print(max(ans))