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=list(map(int, list(input())))
tmp=s[0]
cnt=[]
c=0
for i in range(n):
    if tmp==s[i]:
        c+=1
    else:
        tmp=s[i]
        cnt.append( c)
        c=1
    if i==n-1:
        cnt.append( c)
ans=0
S=[0]*len(cnt)
S[0]=cnt[0]
for i in range(1, len(cnt)):
    S[i]=S[i-1]+cnt[i]
S=[0]+S

for i in range(len(cnt)):
    if i%2==s[0]:
        if i+k*2<=len(cnt):
            ans=max(ans, S[i+k*2]-S[i])
        else:
            ans=max(ans, S[len(cnt)]-S[i])
    else:
        if i+k*2+1<=len(cnt):
            ans=max(ans, S[i+k*2+1]-S[i])
        else:
            ans=max(ans,S[len(cnt)]-S[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate
n,k = li()
s = ns()

prev = '0'

zeros = []
ones = []

cur = 0
for si in s:
    if si == prev:
        cur += 1
        
    else:
        if prev == '0':
            zeros.append(cur)
            prev = '1'
        else:
            ones.append(cur)
            prev = '0'
        cur = 1
        
if prev == '0':
    zeros.append(cur)
else:
    ones.append(cur)
    zeros.append(0)

if len(ones) == 0 or len(zeros) == 0:
    ans = n

else:
    ans = 0
    zero_cum = [0] + list(accumulate(zeros))
    one_cum = [0] + list(accumulate(ones))
    
    if len(zeros) <= k:
        ans = n
    
    else:
        for i in range(len(zeros)-k+1):
            tmp = (zero_cum[i+k] - zero_cum[i])\
                    + (one_cum[min(len(ones), i+k)] - one_cum[max(0, i-1)])
            ans = max(ans, tmp)
        
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
arr = []
prev = '1'
length = 0
for c in S:
  if prev != c:
    arr.append(length)
    length = 0
  length += 1
  prev = c
arr.append(length)
if S[-1] == '0':
  arr.append(0)

sarr = [0]
for a in arr:
  sarr.append(sarr[-1] + a)

L = K * 2 + 1
if L >= len(sarr):
  print(N)
  exit()
ans = 0
for i in range(0, len(sarr)-L, 2):
  t = sarr[i+L] - sarr[i]
  ans = ans if ans > t else t
print(ans)

Submission status: Accepted

Solution code:
(N,M) = (int(i)for i in input().split(" "))
S = input()
l = [[0,0]]
ch = '0'
count = 0
for s in S:
	if s==ch:
		count += 1
	else:
		if s == '0':
			l[-1].append(count)
		else:
			l.append([count])
		ch = s
		count += 1
if len(l[-1]) == 1:
	l[-1].append(count)
elif l[-1][1] != count:
	l.append([count, count])

left = 0
right = M
if len(l) <= M:
	right = len(l) - 1

max_ans = 0
while right < len(l):
	ans = l[right][1] - l[left][0]
	if ans > max_ans:
		max_ans = ans
	right += 1
	left += 1

print(max_ans)

Submission status: Accepted

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


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

cursum = [0]*(len(li)+1)
for i in range(1,len(li)+1):
    cursum[i] = cursum[i-1]+ li[i-1]
    

ans = 0
if s[0]=="1":
  flag = True
else:
  flag = False

for i in range(1,len(cursum)):
        if flag:
            ans = max(ans,cursum[i] - cursum[max(i-2*k-1,0)])
            flag = False
        else:
            ans = max(ans,cursum[i] - cursum[max(i-2*k,0)])
            flag = True

if ans == 0:
    print(n)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

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

# print([list(g) for k, g in groupby(S)])
l = [len(list(g)) for k, g in groupby(S)]

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

# print(l)

w = K*2+1

m = sum(l[:w])
max_num = m
for i in range(len(l)-w):
    # print(w, i)
    m -= l[i]
    m += l[w+i]
    if i%2 == 1:
        # print(m)
        max_num = max(max_num, m)

print(max_num)

Submission status: Accepted

Solution code:
n, k = [int(item) for item in input().split()]
s = input()
arr = []
c = 0
if s[0] == "0":
  cur = "0"
  arr.append(0)
else:
  cur = "1"

for i in s:
  if i == cur:
   c += 1
  else:
    cur = i
    arr.append(c)
    c = 1
arr.append(c)
if s[-1]== "0":
  arr.append(0)

nk = 2 * k + 1
cusum = sum(arr[:nk])
mnum = cusum
for i in range(nk, len(arr), 2):
  cusum += -(arr[i-nk]) + arr[i] -(arr[i-nk+1]) + arr[i+1]
  mnum = max(mnum, cusum)
print(mnum)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    N, K = list(map(int, input().split()))
    lc = list(map(int, list(input())))
    l, r = 0, 0
    k = 0
    bc = 1
    ret = 0
    for i, c in enumerate(lc):
        if c == 0 and bc == 1:
            if k == K:
                ret = max(ret, i-l)
                c2 = lc[l]
                while c2 == 1 and l < N-1:
                    l += 1
                    c2 = lc[l]
                while c2 == 0 and l < N-1:
                    l += 1
                    c2 = lc[l]
            else:
                k += 1
        bc = c
    ret = max(ret, N-l)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  _, N = map(int, input().split())
  stats = list(map(int, input()))
  values = []
  prev = -1

  for s in stats:
    if s == prev:
      values[-1][1] += 1
    else:
      values.append([s, 1])
      prev = s

  values.append([1, 0])

  window = N * 2 + 1
  length = 0
  max_length = 0

  for i in range(len(values)):
    if i - window >= 0:
      length -= values[i - window][1]

    length += values[i][1]

    if values[i][0] == 1:
      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()

L = 0
r = 0
# k + 1 回目の 0 エリアの直前まで r を進める
for _ in range(k):
    while r < len(s) and s[r] == '1':
        r += 1
    while r < len(s) and s[r] == '0':
        r += 1
while r < len(s) and s[r] == '1':
    r += 1

ans = r - L
# 1つずつエリアずらす
while True:
    while L < len(s) and s[L] == '1':
        L += 1
    while L < len(s) and s[L] == '0':
        L += 1
    while r < len(s) and s[r] == '0':
        r += 1
    while r < len(s) and s[r] == '1':
        r += 1
    ans = max(ans, r - L)
    if r >= len(s):
        break

print(ans)

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]

S = input()

xs = []

i = 0

while i < N :
    l = 0
    while i < N and S[i] == '1':
        i += 1
        l += 1
    xs.append(l)
    l = 0
    while i < N and S[i] == '0':
        i += 1
        l += 1
    xs.append(l)

xs += [0] * (K * 2)

#print(xs)

result = 0

l = (K * 2) + 1
result = r = sum(xs[0:l])
#print("*", result, r)

i = 0
while i + l + 1 < len(xs):
    r = r - xs[i] - xs[i+1] + xs[i+l] + xs[i+l+1]
    result = max(result, r)
    #print(result, r)
    i += 2

print(result)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
T = '0' + S + '0'

ans = 0
k = 0
for i,(a,b) in enumerate(zip(S,S[1:])):
    if a=='0' and b=='1':
        k += 1
    elif k==K and a=='1' and b=='0':
        ans = max(ans, i+1)
        break
else:
    print(N)
    exit()

k = 0
S = S[::-1]
for i,(a,b) in enumerate(zip(S,S[1:])):
    if a=='0' and b=='1':
        k += 1
    elif k==K and a=='1' and b=='0':
        ans = max(ans, i+1)
        break
else:
    print(N)
    exit()

x = []
y = []
for i,(a,b) in enumerate(zip(T,T[1:])):
    if a==b: continue
    if a=='0':
        x.append(i)
    else:
        y.append(i)

for a,b in zip(x,y[K:]):
    ans = max(ans, b-a)
print(ans)

Submission status: Accepted

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

X = [0]
if s[0] == "0":
    X.append(0)
for i in range(N):
    if i == N-1 or s[i] != s[i+1]:
        X.append(i+1)
if s[-1] == "0":
    X.append(X[-1])

if len(X) <= K*2+1:
    print(N)
else:
    ma = 0
    for i in range(0, len(X) - K*2 - 1, 2):
        ma = max(X[i+K*2+1]-X[i], ma)
    print(ma)

Submission status: Accepted

Solution code:
import sys

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

if not ("1" in S):
    print(N)
    sys.exit()

D=[]
NOW=1
S+="!"


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

    else:
        D.append([S[i-1],NOW])
        NOW=1
    

if D[0][0]=="0":
    D=[["1",0]]+D

if D[-1][0]=="0":
    D.append(["1",0])

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

SUM=[0]
for i in range(len(D)):
    SUM.append(SUM[-1]+D[i][1])


ANS=0

for i in range(K*2+1,len(SUM),2):
    ANS=max(ANS,SUM[i]-SUM[i-K*2-1])

print(ANS)

Submission status: Accepted

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


def solve(N: int, K: int, S: int):
    group = []
    if S[0] == '0':
        group.append(0)
    tmp = 1
    for i in range(1, N):
        if S[i] == S[i - 1]:
            tmp += 1
        else:
            group.append(tmp)
            tmp = 1
    group.append(tmp)
    if S[-1] == '0':
        group.append(0)
    #print(group)
    num = K * 2 + 1
    if len(group) <= num:
        print(N)
        return

    cum = [0] * len(group)
    cum[0] = group[0]
    for i in range(1, len(group)):
        cum[i] = cum[i - 1] + group[i]
    cum = [0] + cum
    #print(group)
    #print(cum)

    ret = 0
    for i in range(0, len(group) - num + 1, 2):
        cumsum = cum[i + num] - cum[i]
        #print(i, i + num, cumsum)
        ret = max(ret, cumsum)
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

beg=[0]
end=[]

for i in range(N):
	if len(beg) != len(end):
		if S[i] == "0":
			end.append(i-1)
	else:
		if S[i] == "1":
			beg.append(i)

if len(beg) != len(end):
	end.append(N-1)

beg.append(N-1)
end.append(N-1)

ans=[1 + end[i+K] - beg[i] for i in range(len(beg)-K)]
print(max(ans) if len(ans) > 0 else N)

Submission status: Accepted

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

for i in s:
    if not sani:
        sani.append([int(i),0,0])
    elif sani[-1][0]==int(i):
        sani[-1][2]+=1
    else:
        sani.append([int(i),sani[-1][2]+1,sani[-1][2]+1])

ans=0
left,right=0,0
zeroCnt=0

while right<len(sani):
    if zeroCnt<k or sani[right][0]==1:
        nowElem=sani[right]
        zeroCnt+=1 if sani[right][0]==0 else 0
        ans=max(ans,sani[right][2]-sani[left][1]+1)
        right+=1
    else:
        zeroCnt-=1 if sani[left][0]==0 else 0
        left+=1

print(ans)

Submission status: Accepted

Solution code:


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

l = [0]
curr = '1'
for c in S:
    if c != curr:
        l.append(1)
        curr = c
    else:
        l[-1] += 1
if curr == '0':
    l.append(0)

n_group = len(l) // 2
sum_ = 0
k = min(K, n_group)
for i in range(k):
    sum_ += l[2*i] + l[2*i+1]
sum_ += l[2*k]
max_ = sum_
for i in range(k, n_group):
    sum_ -= l[2*i-2*K] + l[2*i+1-2*K]
    sum_ += l[2*i+1] + l[2*i+2]
    max_ = max(max_, sum_)
print(max_)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if a == b:
        print(2*a)
    else:
        print(2*max(a,b)-1)
    return

#B
def B():
    n = I()
    h = LI()
    m = h[0]
    ans = 1
    for i in range(1,n):
        if m <= h[i]:
            ans += 1
            m = h[i]
    print(ans)
    return

#C
def C():
    s = S()
    ans = 0
    n = len(s)
    t = ["1" if i%2 else "0" for i in range(n)]
    for i in range(n):
        if t[i] != s[i]:
            ans += 1
    ans2 = 0
    t = ["0" if i%2 else "1" for i in range(n)]
    for i in range(n):
        if t[i] != s[i]:
            ans2 += 1
    print(min(ans,ans2))
    return

#D
def D():
    n,k = LI()
    s = S()
    f = [0 for i in range(n)]
    if s[0] == "0":
        f[0] = 1
    for i in range(1,n):
        if s[i] ==  "0" and s[i-1] == "1":
            f[i] = 1
    for i in range(n-1):
        f[i+1] += f[i]
    ans = 0
    for l in range(n):
        r = bisect.bisect_right(f,k+f[l]*int(s[l]))
        ans = max(ans, r-l)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

v = []
cnt = 1
for i in range(n - 1):
	if s[i] == s[i + 1]:
		cnt = cnt + 1
	else:
		v.append(cnt)
		cnt = 1
v.append(cnt)
m = len(v)

sum = [0] * (m + 1)
for i in range(1, m + 1):
	sum[i] = sum[i - 1] + v[i - 1]

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

if __name__ == "__main__":
    N, K = map(int, input().split())
    S = input()
    T = [0]
    if(S[0] == '0') :
        T.append(0)
    T.append(1)
    for i in range(1, N):
        if(S[i] == S[i-1]):
            T[-1] += 1
        else:
            T.append(1)
    for i in range(3 * K):
        T.append(0)
    SIZE = len(T)
    S = [0] * SIZE
    for i in range(1, SIZE):
        S[i] = S[i-1] + T[i]
    #print(T)
    #print(S)
    ans = 0
    for i in range (1, SIZE, 2):
        if(i + 2 * K >= SIZE):
            break
        ans = max(ans, S[i + 2 * K] - S[i-1])
    print(ans)

Submission status: Accepted

Solution code:
from itertools import chain
N, K = map(int, input().split())
S = input()
LS = []
pre = S[0]
ctr = 0
for s in chain(S, '2'):
    if s == pre:
        ctr += 1
    else:
        LS.append(ctr)
        ctr = 1
        pre = s
if S[0] == '0':
    LS = [0] + LS
if S[-1] == '0':
    LS = LS + [0]
ans = 0
sumi = 0
for i in range(len(LS)):
    if i <= 2*K:
        sumi += LS[i]
    else:
        sumi += LS[i] - LS[i-2*K-1]
    if not i % 2:
        ans = max(ans, sumi)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
S = list(map(int,list(str(input()))))
ss = []

cnt = 0
flag1 = (S[0] == 1)
if S[0] == 0:
    ss.append(0)

for s in S:
    if flag1 and s == 0:
        ss.append(cnt)
        cnt = 1
        flag1 = False
    elif not flag1 and s==1:
        ss.append(cnt)
        cnt = 1
        flag1 = True
    else:
        cnt += 1

ss.append(cnt)
if S[-1] == 0:
    ss.append(0)

#print(ss)

l = 0
r = 2*K
tmp = sum(ss[l:r+1])
ans = tmp
while True:
    l += 2
    r += 2
    if r >= len(ss):
        break
    tmp -= ss[l-2] + ss[l-1]
    tmp += ss[r-1] + ss[r]
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

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

o = []
l = [0]

prev = '1'
for s in S:
	if s == '1':
		if prev == '0':
			l.append(1)
		else:
			l[-1] += 1
	else:
		if prev == '1':
			o.append(1)
		else:
			o[-1] += 1
	prev = s
l.append(0)

agg = sum(l[0:K+1]) + sum(o[0:K])
max_agg = agg
for i in range(1, len(o)-K+1):
	agg -= l[i-1] + o[i-1]
	agg += l[i+K] + o[i+K-1]
	max_agg = max(max_agg, agg)
print(max_agg)

Submission status: Accepted

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

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

for i in xrange(1, N):
    if S[i - 1] != S[i]:
        n.append(i)

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

if len(n) <= K * 2 + 1:
    print N
else:
    m = 0
    for i in xrange(K * 2 + 1, len(n), 2):
        m = max(m, n[i] - n[i - K * 2 - 1])
    print m

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    seq = []
    current = "1"
    cnt = 0
    for c in S:
        if c == current:
            cnt += 1
        else:
            seq.append(cnt)
            current = c
            cnt = 1
    seq.append(cnt)
    if len(seq) % 2 == 0:
        seq.append(0)
    if len(seq) <= K*2+1:
        print(sum(seq))
        return
    ans = 0
    total = 0
    j = 0
    for i in range(len(seq)-K*2):
        while j < i+K*2+1:
            total += seq[j]
            j += 1
        if i % 2 == 0:
            ans = max(ans, total)
        total -= seq[i]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

T = []
if S[0]=="0":
  T = [0]
p = 0
for i in range(1, N+1):
  if i==N or S[i]!=S[i-1]:
    T += [i-p]
    p = i
if S[-1]=="0":
  T += [0]

if len(S)<=2*K+1:
  ans = sum(T)
else:
  t = sum(T[:2*K+1])
  ans = t
  for i in range(2*K+1, len(T)):
    t -= T[i-2*K-1]
    t += T[i]
    if i%2==0:
      ans = max(ans, t)
print ans

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
L=[0]
#even:1
#odd:0
tmp="1"
for i in range(N):
    if tmp!=S[i]:
        L.append(1)
    else:
        L[-1]+=1
    tmp=S[i]
if tmp=="0":
    L.append(0)
#print(L)
M=len(L)
if M<=2*K+1:
    print(N)
    exit()
X=[0 for i in range(M+1)]
for i in range(M):
    X[i+1]=L[i]+X[i]
#print(X)
ans=0
for i in range(0,M-2*K,2):
    #print(X[i],X[i+2*K+1])
    ans=max(ans,X[i+2*K+1]-X[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

s += 'X'

i = 0
j = 0
zero = 1 if s[0] == '0' else 0
ans = 0
while j < n:
    if zero <= k:
        ans = max(ans, j - i + 1)
        if s[j] == '1' and s[j + 1] == '0':
            zero += 1
        j += 1
    else:
        if s[i] == '0' and s[i + 1] == '1':
            zero -= 1
        i += 1

print(ans)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = map(int, raw_input().split())
S = raw_input()
ls = []
cc = '1'
num = 0
for c in S:
    if cc == c:
        num += 1
    else:
        ls += [num]
        num = 1
        cc = c
ls += [num]
if cc == '0':
    ls += [0]
S = 0
for i in range(min(len(ls), 2 * K + 1)):
    S += ls[i]
ans = S
for i in range(2 * K + 1, len(ls), 2):
    S += ls[i]
    S += ls[i + 1]
    S -= ls[i - (2 * K + 1)]
    S -= ls[i - (2 * K)]
    ans = max(ans, S)
print ans

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
*S, = map(int, input())

C = []
prv = 1; cnt = 0
for c in S:
    if prv != c:
        C.append(cnt)
        cnt = 1
    else:
        cnt += 1
    prv = c
if cnt > 0:
    C.append(cnt)
if prv == 0:
    C.append(0)

M = len(C)//2
que = deque([C[0]])
res = ans = C[0]
for i in range(M):
    if len(que) == 2*K+1:
        res -= que.popleft() + que.popleft()
    que.append(C[2*i+1])
    que.append(C[2*i+2])
    res += C[2*i+1] + C[2*i+2]
    ans = max(res, ans)
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
l=list()
s = s.replace("10","1,0")
s = s.replace("01","0,1")

l = [len(i) for i in s.split(",")]
r = 0
ans = 0

if s[0] == "1":
    r = min(k, len(l) - 1)
else:
    r = k-1

t = l[r]

for j in range(1, k+1):
    #print(r,j,t,l[r-j],l[r+j])
    if r-j >= 0:
        #print("r-j >= 0:")
        t += l[r-j]
    if r+j < len(l):
        #print("r+j < len(l):")
        t += l[r+j]
ans = t
for i in range(r+2, len(l) ,2):
    for j in range(1, 3):
        if i-j-k >= 0:
            #print("l[i-j-k]", i-j-k, l[i-j-k])
            t -= l[i-j-k]
        if i+j+k-2 < len(l):
            #print("l[i+k+j]", i+j+k-2, l[i+j+k-2])
            t += l[i+j+k-2]
    ans = max(ans, t)
print(ans)

Submission status: Runtime Error

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

if N == 1:
  if S == '1':
    print(1)
  elif K > 0:
    print(1)
  else:
    print(0)
  exit()

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

if S[0] == '1':
  ans = sum(l[:2*K+1])
  tmp = sum(l[:2*K+1])
  if S[-1] == '1':
    for i in range(0, len(l)-2*K-2, 2):
      tmp += l[2*K+i+1] + l[2*K+i+2] - l[i] - l[i+1]
      ans = max(ans, tmp)
  else:
    for i in range(0, len(l)-2*K-2, 2):
      tmp += l[2*K+i+1] + l[2*K+i+2] - l[i] - l[i+1]
      ans = max(ans, tmp)
    tmp += l[2*K+i+1] - l[i] - l[i+1]
    ans = max(ans, tmp)
else:
  ans = max(sum(l[:2*K]), sum(l[1:2*K+2]))
  tmp = sum(l[1:2*K+2])
  if S[-1] == '1':
    for i in range(1, len(l)-2*K-2, 2):
      tmp += l[2*K+i+1] + l[2*K+i+2] - l[i] - l[i+1]
      ans = max(ans, tmp)
  else:
    for i in range(1, len(l)-1, 2):
      tmp += l[2*K+i+1] + l[2*K+i+2] - l[i] - l[i+1]
      ans = max(ans, tmp)
    tmp = sum(l[-2*K:])
    ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import groupby

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

grouped = groupby(s)

res = []

if s[0] == '0':
	res.append((1,0))

for l,v in grouped:
	res.append( (l,len(list(v))) )

if s[len(s)-1] == '0':
	res.append((1,0))

now = 0
ans = 0
for i in range(2*k+1):
	now += res[i][1]

ans = max(ans,now)

for i in range(2*k+1,len(res),2):
	now -= res[i-2*k-1][1]
	now -= res[i-2*k][1]

	now += res[i][1]
	now += res[i+1][1]

	ans = max(ans,now)

print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

comp = [0]
pre = S[0]
tmp = 0
for s_i in S:
    if s_i != pre:
        comp.append(tmp)
        tmp = 1
    else:
        tmp += 1
    
    pre = s_i
comp.append(tmp)
for i in range(len(comp)-1):
    comp[i+1] += comp[i]

ans = 1
if K == 1:
    w = 2
else:
    w = 2*K + 1
ans = 1
tmp = 0
c = 0
if K == 1:
    for i in range(2, len(comp)):
        tmp = comp[i] - comp[i-2]
        ans = max(ans, tmp)
else:
    start = 0 if S[0] == "1" else 1
    for i in range(start, len(comp), 2):
        tmp = comp[i] - comp[i-w-1]
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
n,k=map(int,input().split())
s=input()
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
a+=[0]*3
k*=2
for i in range(m-k):
  if s[a[i]]=='0':cnt=a[i+k]-a[i]
  elif s[a[i+k+1]]=='1':cnt=a[i+k+1]-a[i]
  else:cnt=a[i+k]-a[i]
  ans=max(ans,cnt)
print([ans,n][m<=k+1])

Submission status: Runtime Error

Solution code:
from itertools import*
def comp(s):
  n=len(s)
  cnt=1
  a=[]
  for i in range(n-1):
    if s[i+1]==s[i]:cnt+=1
    else:
      a+=[cnt]
      cnt=1
  a+=[cnt]
  return a
a=list(accumulate([0]+comp(s)))
ans=0
m=len(a)
a+=[0]*3
k*=2
for i in range(m-k):
  if s[a[i]]=='0':cnt=a[i+k]-a[i]
  else:cnt=a[i+k+1]-a[i]
  ans=max(ans,cnt)
print([ans,n][m<=k+1])

Submission status: Runtime Error

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 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: Runtime Error

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)
    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)
    # print(S)
    # print(l)

    # 1の塊をK+1個くっつけた場合の長さを調べる
    ans = 0
    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: Runtime Error

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)
    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)
    # print(S)
    # print(l)

    # 1の塊をK+1個くっつけた場合の長さを調べる
    ans = 0
    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: Runtime Error

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)
    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)
    # print(S)
    # print(l)

    # 1の塊をK+1個くっつけた場合の長さを調べる
    ans = 0
    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()