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

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

    return A

def main():
    N, K = map(int, input().split())
    S = input()
    lens = length(S)
    A = [0] + list(accumulate(lens))
    ans = 0
    if S[0] == '0':
        A = [0] + A
        for i in range(1,len(A)+1,2):
            right = i + 2 * K
            if right >= len(A):
                right = len(A) - 1
            tmp = A[right] - A[i-1]
            ans = max(ans, tmp)
    else:
        for i in range(1,len(A)+1,2):
            right = i + 2 * K
            if right >= len(A):
                right = len(A) - 1
            tmp = A[right] - A[i-1]
            ans = max(ans, tmp)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

run=[]
import itertools
for key,g in itertools.groupby(S):
  run.append(len(list(g)))
  
import numpy as np
run=np.cumsum(run)

ans=0
if S[0]=="0":
  left=0
  while left<len(run):
    if left==0:
      zone=min(2*K-1,len(run)-1)
      val=run[zone]
      left+=1
    else:
      zone=min(left+2*K,len(run)-1)
      val=run[zone]-run[left-1]
      left+=2
    ans=max(ans,val)
elif S[0]=="1":
  left=0
  while left<len(run):
    if left==0:
      zone=min(2*K,len(run)-1)
      val=run[zone]
      left+=2
    else:
      zone=min(left+2*K,len(run)-1)
      val=run[zone]-run[left-1]
      left+=2
    ans=max(ans,val)
print(ans)

Submission status: Accepted

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

zero = []
one = []
if S[0] == '0':
    one.append(0)
from itertools import groupby
for k, g in groupby(S):
    if k == '0':
        zero.append(len(list(g)))
    else:
        one.append(len(list(g)))
if S[-1] == '0':
    one.append(0)

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

zerob = [0]
oneb = [0]
for i in range(len(zero)):
    zerob.append(zerob[i] + zero[i])
for i in range(len(one)):
    oneb.append(oneb[i] + one[i])

ans = 0
for i in range(K, len(zerob)):
    z = zerob[i] - zerob[i-K]
    o = oneb[i+1] - oneb[i-K]
    ans = max(ans, z+o)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(str(input()))
r=[]
l=[]
c=0
d=1
for i in range(n):
	if s[i]=='1' and d==1:
		r.append(i)
		c=1
		d=0
	elif s[i]=='0' and c==1:
		l.append(i-1)
		c=0
		d=1
if c>0:
	l.append(i)
if len(r)<=k+1:
	r=[0]*(k+1-len(r))+r+[n-1]*(k+1-len(r))
	l=[0]*(k+1-len(l))+l+[n-1]*(k+1-len(l))
r=[0]+r+[n-1]
l=[0]+l+[n-1]
ans=0
for i in range(len(r)-k):
	ans=max(ans,l[i+k]-r[i]+1)
print(ans)

Submission status: Accepted

Solution code:
n,K = map(int, input().split(' '))
s = input()
ls0 = [0]
ls1 = [0]
if s[0] == "0":
    ls1[0] = -1
for i in range(n):
    if s[i] == "0":
        ls0[-1] += 1
        if ls1[-1] != 0:
            ls1.append(0)
    if s[i] == "1":
        ls1[-1] += 1
        if ls0[-1] != 0:
            ls0.append(0)
if s[0] == "0":
    ls1[0] = 0
if ls0[-1] == 0:
    del ls0[-1]
ans = []
ansmax = 0
if K>=len(ls0):
    ansmax = len(s)
else:
    ans.append(sum(ls0[0:K])+sum(ls1[0:K+1]))
    for i in range(1,len(ls0)-K+1):
        ans.append(ans[-1]+ls0[i+K-1]+ls1[i+K]-ls0[i-1]-ls1[i-1])
    else:
        ans.sort()
        ansmax = ans[-1]
print(ansmax)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
num=[0]
c=1
for i in range(1,n):

    if s[i]==s[i-1]:
        c+=1
    else:
        num.append(c)
        c=1
num.append(c)
num.append(0)
#print(num)

ans=0
#print(num)
if s[0]=="0":
    if len(num)-2*k+1<=0:
        ans=sum(num)
    else:
        asum=sum(num[0:2*k+1])
        ans=asum
        #print(asum)
        for i in range(2,len(num)-2*k,2):
            #print(asum,num[i+2*k],num[i+2*k-1],num[i-1],num[i-2])
            asum=asum+num[i+2*k]+num[i+2*k-1]-num[i-1]-num[i-2]
            ans=max(ans,asum)
if s[0]=="1":
    if len(num)-2*k+2<=0:
        ans=sum(num)
    else:
        asum=sum(num[1:2*k+2])
        ans=asum
        for i in range(3,len(num)-2*k,2):
            #print(asum,num[i+2*k],num[i+2*k-1],num[i-1],num[i-2])
            asum=asum+num[i+2*k]+num[i+2*k-1]-num[i-1]-num[i-2]
            ans=max(ans,asum)
print(ans)

Submission status: Accepted

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

T = []
for i in range(N):
  if i == 0:
    bit = S[i]
    cnt = 1
  else:
    if S[i] != S[i-1]:
      T.append([int(bit), cnt])
      bit = S[i]
      cnt = 1
    else:
      cnt += 1
T.append([int(bit), cnt])
N = len(T)
#print(T)

L,R = 0,0
rest = 1 if T[0][0] == 0 else 0
suml = T[0][1]
answer = 0

while 1:
  #print(L,R, "rest:", rest, "sum:", suml)
  if rest <= K:
    answer = max(answer, suml)
  if rest <= K:
    if R == N-1:
      break
    R += 1
    if T[R][0] == 0:
      rest += 1
    suml += T[R][1]
  else:
    L += 1
    if T[L-1][0] == 0:
      rest -= 1
    suml -= T[L-1][1]
  if rest <= K:
    answer = max(answer, suml)
print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

# ランレングス圧縮
# (後の処理がしやすいように、常に1の区間から始まって1の区間で終わる形にする)
A = []
# 番兵
if S[0] == '0':
    A.append(0)
cnt = 1
cur = S[0]
for i, s in enumerate(S[1:], 1):
    if s != cur:
        A.append(cnt)
        cnt = 1
        cur = s
    else:
        cnt += 1
A.append(cnt)

# 例外処理
if len(A) == 1:
    print(N)
    exit()

# 番兵
if S[-1] == '0':
    A.append(0)

M = len(A)
ans = sm = sum(A[:K*2+1])
# 常に1の区間まで取った方が得なので、indexを2ずつ進める
for i in range(K*2+2, M, 2):
    # 前の0の区間と1の区間を増やす
    sm += A[i-1] + A[i]
    # 後ろの0の区間と1の区間を減らす
    if i-K*2-2 >= 0:
        sm -= A[i-K*2-2]
    if i-K*2-1 >= 0:
        sm -= A[i-K*2-1]
    ans = max(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

# ランレングス圧縮
A = []
# 番兵
if S[0] == '0':
    A.append(0)
cur = S[0]
cnt = 1
for i, s in enumerate(S[1:], 1):
    if s != cur:
        A.append(cnt)
        cnt = 1
        cur = s
    else:
        cnt += 1
A.append(cnt)

# 例外処理
if len(A) == 1:
    print(N)
    exit()

# 番兵
if S[-1] == '0':
    A.append(0)

M = len(A)
ans = sm = sum(A[:K*2+1])
for i in range(K*2+1, M):
    sm += A[i]
    # 今回増やすのが0の区間なら、後ろ2つ減る
    if i % 2 == 1:
        if i-K*2 >= 0:
            sm -= A[i-K*2]
        if i-K*2-1 >= 0:
            sm -= A[i-K*2-1]
    ans = max(ans, sm)
print(ans)

Submission status: Accepted

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

memo = []
for i, s in enumerate(S):
    if i == 0:
        now = s
        cnt = 1
        continue
    if s == now:
        cnt += 1
    else:
        memo.append(cnt)
        now = s
        cnt = 1
memo.append(cnt)

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

if len(S) <= 2 * k + 1:
    ans = sum(memo)
else:
    k = 2*k+1
    stand = sum(memo[0:k])
    cnt = (len(memo) - k) // 2

    ans = stand
    for i in range(cnt):
        stand -= memo[i * 2]
        stand -= memo[i * 2 + 1]
        stand += memo[k + i * 2]
        stand += memo[k + i * 2 + 1]
        ans = max(ans, stand)

print(ans)

Submission status: Accepted

Solution code:
import sys
input =  sys.stdin.readline

n, k = map(int, input().split())
s = input()+'-1'

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

# print(cnt_list)


l = 0
r = 2*k
ma = 0
su = 0
if s[0] == '0':
    r = 2*k
else:
    r = 2*k+1
su = sum(cnt_list[l:r])
while l < r:
    if ma < su:
        ma = su
    if l == 0 and r == 2*k:
        l += 1
        su -= cnt_list[l-1]
    else:
        l += 2
        su -= sum(cnt_list[l-2:l])
    r += 2
    su += sum(cnt_list[r-2:r])
    if r >= len(cnt_list):
        r = len(cnt_list)
    
print(ma)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
S = list(map(int, S))
s = []
tmp = 0

for i in range(N):
    if S[i] == 1:
        if tmp != 0:
            s.append((tmp, i-1))
        tmp = 0
    else:
        tmp += 1
        if i == N-1:
            s.append((tmp, i))
if len(s) <= K:
    print(N)
    exit(0)
ans = 0
for i in range(len(s)-K+1):
    tmp = 0
    if i+K == len(s):
        tmp = N-1
    else:
        tmp = s[i+K][1]-s[i+K][0]

    if i != 0:
        tmp -= s[i-1][1]
    else:
        tmp += 1
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

def renzoku(s):
    n=len(s)
    lis=[]
    c=1
    if len(s)==1:
        return [1]
    for i in range(n-1):
        if s[i+1]==s[i]:
            c+=1
        else:
            lis.append(c)
            c=1
        if i==n-2:
            lis.append(c)
    return lis


r=renzoku(s)
i=0
if s[0]=="0":
    r=[0]+r
if s[-1]=="0":
    r=r+[0]

cand = sum(r[:min(2*k+1,len(r))])
ans=cand
while 2*k+3 + 2*i<=len(r):
    cand += r[2*k+1+2*i]+r[2*k+2+2*i]-r[2*i]-r[2*i+1]
    if cand>ans:
        ans=cand
    i+=1
print(ans)

Submission status: Accepted

Solution code:
def p_d():
    n, k = map(int, input().split())
    *s, = map(int, input())
    ans = 0
    l, r = 0, 0
    count = 0
    while r < n:
        while r < n and count < k:
            if s[r] == 0:
                count += 1
                while r < n and s[r] == 0:
                    r += 1
            else:
                while r < n and s[r] == 1:
                    r += 1
        while r < n and s[r] == 1:
            r += 1
        ans = max(ans, r - l)
        while l < r and s[l] == 1:
            l += 1
        while l < r and s[l] == 0:
            l += 1
        count -= 1

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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

# In[9]:


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


# In[10]:


last = S[0]
if last == '0':
    A = [0]
else:
    A = []
renzoku = 1
for i in range(1, N):
    if S[i] == last:
        renzoku += 1
    else:
        A.append(renzoku)
        renzoku = 1
        last = S[i]
A.append(renzoku)
if S[-1] == '0':
    A.append(0)


# In[11]:


A


# In[14]:


l = 0
r = l + 2 * M + 1
if r > len(A):
    t = sum(A)
else:
    t = sum(A[l:r])
ret = t
l = 2
while True:
    r = l + 2 * M + 1
    if r > len(A):
        break
    t = t + A[r - 2] + A[r - 1] - A[l - 2] - A[l - 1]
    ret = max(t, ret)
    l += 2
print(ret)


# In[ ]:





# In[ ]:





# In[ ]:

Submission status: Accepted

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

    t = []
    cont = 0
    p = '1'
    for c in s:
        if c == p:
            cont += 1
        else:
            t.append(cont)  # * (1 if p == '0' else -1))
            p = c
            cont = 1
    t.append(cont)  # * (1 if p == '0' else -1))
    t.extend([0] * 2)
    if len(t) % 2 == 1:
        t.append(0)
    # [直立,逆立,...直立,逆立]

    st = t[::2]  # 直立
    acc = [0]  # 直立,逆立の累積和

    p = 0
    j = 0
    while j < len(t) - 1:
        p += sum(t[j:j + 2])
        j += 2
        acc.append(p)

    ret = 0
    for j, (x, acc_) in enumerate(zip(st, acc)):
        ret = max(ret, (x + acc_) - acc[max(0, j - k)])
    return ret


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, k = LI()
s = S()
X = []
if s[0] == '0':
    X += [0]

cnt = 1
for i in range(n - 1):
    if s[i] != s[i + 1]:
        X += [cnt]
        cnt = 1
    else:
        cnt += 1
X += [cnt]
if s[n - 1] == '0':
    X += [0]

if len(X) <= 2 * k + 1:
    print(n)
else:
    ans = 0
    acc = list(accumulate([0] + X))
    for j in range(2 * k + 1, len(acc), 2):
        ans = max(acc[j] - acc[j - (2 * k + 1)], ans)
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 1
before_s = S[0]
for s in S[1:]:
    count += 1
    if before_s != s:
        S_list.append(count-1)
        count = 1
    before_s = s

if S[-2] == "0":
    S_list.append(0)

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    ans_list = []
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        if i == 0:
            ans = sum(S_list[left:right+1])
            ans_list.append(ans)
        else:
            # print(S_list[left-2:left], S_list[right-1:right+1])
            ans = ans - sum(S_list[left-2:left]) + sum(S_list[right-1:right+1])
            ans_list.append(ans)
    print(max(ans_list))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(map(int, list(str(input()))))
c = 0
ran = [0,0]
for i in range(n):
    if s[c] == s[i]:
        ran[-1] += 1
    else:
        ran.append(i+1)
        c = i
result = []
for i in range(1, len(ran)):
    if s[ran[i-1]] == 1:
        result.append(ran[min(i+2*k,len(ran)-1)]-ran[i-1])
    else:
        result.append(ran[min(i+2*k-1, len(ran)-1)]-ran[i-1])
print(max(result))

Submission status: Accepted

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

rec = []
for i in range(n):
  if i == 0:
    last = s[0]
    combo = 1
  elif s[i] == last:
    combo += 1
  else:
    last = s[i]
    rec.append(combo)
    combo = 1
rec.append(combo)
if s[0] == '0':
  rec = [0] + rec
if s[-1] == '0':
  rec = rec + [0]
#print(rec)
rec = [0] * (2*n) + rec + [0] * (2*n)

for j in range(len(rec)):
  if j == 0:
    cum = [rec[0]]
  else:
    cum.append(cum[-1] + rec[j])
#print(cum)

can = []
st = 1
while True:
  try:
    can.append(cum[st+2*k+1]-cum[st])
    st += 2
  except:
    break
#print(can)
print(max(can))

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
s = input()
now = s[0]
start = []
end = []
if k != 0 or s[0] == "1":
  start.append(0)
for i,v in enumerate(s):
  if now == "0" and v == "1":
    start.append(i)
  elif now == "1" and v == "0":
    end.append(i)
  now = v
end.append(len(s))
ans = 0
for st,en in zip(start,end[k+int(s[0])-1:]):
  ans = max(ans,en-st)
if ans == 0:
  if not (all([i == "0" for i in s]) and k == 0):
    ans = len(s)    
print(ans)

Submission status: Accepted

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

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

if S[0] == "1" and S[-1] == "0":
	A = A + [0]
	N += 1
elif S[0] == "0" and S[-1] == "1":
	A = A[::-1] + [0]
	N += 1
elif S[0] == "0" and S[-1] == "0":
	   A = [0] + A + [0]
	   N += 2

ans = sum(A[:2*K+1])
tmp = ans
tK = 2*K
for i in range((N-1)//2-K):
	ind = 2*i
	tmp = tmp - sum(A[ind:ind+2]) + sum(A[ind+tK+1:ind+tK+3])
	ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input() + '#'
D = []
b = s[0]
cnt = 0
for c in s:
    if c == b:
        cnt += 1
    else:
        D.append((b, cnt))
        cnt = 1
        b = c

zero_start = False
if D[0][0] == '0':
    zero_start = True
    D.insert(0,(1, 1)) #indexが複雑になるので1スタートに無理やりする。

lend = len(D)
l = lend // 2 #0集団の個数
ans = -1
if K >= l:
    ans = N
else:
    sm = sum([x[1] for x in D[:2 * K + 1]])
    ans = sm
    if zero_start :
        ans -= 1 #本来存在しない最初の1を減らしておく

    for i in range(2 * K + 1, lend, 2): #最初に加える0集団をスタートとする
        sm += D[i][1]
        if i + 1 < lend:
            sm += D[i + 1][1]
        sm -= D[i - 2 * K][1]
        sm -= D[i - 2 * K - 1][1]

        ans = max(ans, sm)

print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import accumulate

INF = float("inf")


def main():
    N, K = map(int, input().split())
    S = input()
    zero_list = []
    A = []
    one = 0
    zero = 0

    for i in range(N):
        if S[i] == '1':
            one += 1
            if zero != 0:
                A.append(zero)
                zero_list.append(zero)
                zero = 0
        else:
            zero += 1
            if one != 0:
                A.append(one)
                one = 0

    if one != 0:
        A.append(one)
    elif zero != 0:
        A.append(zero)
        zero_list.append(zero)

    if len(zero_list) <= K:
        print(N)
        return

    section = 0
    if S[0] == '1':
        section = 3 + (K-1) * 2
    else:
        section = 2 + (K-1) * 2

    B = list(accumulate([0] + A))
    # print(B)
    if S[0] == '1':
        # print(*A, section)
        m = 0
        i = 0
        while True:
            if i % 2 == 0:
                section = 3 + (K-1) * 2
                end = min(i+section, len(B) - 1)
                # print(B[end] - B[i])
                # print(end)
                m = max(m, B[end] - B[i])
                if len(B) - 1 <= end:
                    break
            else:
                section = 2 + (K-1) * 2
                end = min(i+section, len(B) - 1)
                # print(B[end] - B[i])
                # print(end)
                m = max(m, B[end] - B[i])
                if len(B) - 1 <= end:
                    break
            i += 1
        print(m)
    else:
        m = 0
        i = 0
        while True:
            if i % 2 == 0:
                section = 2 + (K-1) * 2
                end = min(i+section, len(B) - 1)
                # print(B[end] - B[i])
                # print(end, len(B) <= end - 1)
                m = max(m, B[end] - B[i])
                if len(B) - 1 <= end:
                    break
            else:
                section = 3 + (K-1) * 2
                end = min(i+section, len(B) - 1)
                # print(B[end] - B[i])
                # print(end, len(B) <= end - 1)
                m = max(m, B[end] - B[i])
                if len(B) - 1 <= end:
                    break
            i += 1
        print(m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


n,k = [int(_) for _ in input().split()]
s = input()

all_0 = True
for i in range(len(s)):
    if s[i] == '1':
        all_0 = False
        break
if all_0:
    if k == 0:
        print(0)
    else:
        print(n)
    sys.exit()

c0 = 0
c1 = 0
a = [0]
b = []
v = 0
while s[v] == '0':
    c0 += 1
    s = s[1:]
b.append(c0)
c0 = 0
for i in range(len(s)):
    if s[i] == '1':
        c1 += 1
        if c0 != 0:
            b.append(c0)
        c0 = 0
    else:
        c0 += 1
        if c1 != 0:
            a.append(c1)
        c1 = 0
if c0 != 0:
    b.append(c0)
else:
    a.append(c1)
    b.append(0)
a.append(0)
# print(a)
# print(b)

s_a = [0]
s_b = [0]
for i in range(len(a)):
    s_a.append(s_a[i]+a[i])
for i in range(len(b)):
    s_b.append(s_b[i]+b[i])
# print(s_a)
# print(s_b)

ans = 0
if len(b) <= k:
    ans = n
else:
    for i in range(len(a)-k):
        # print(s_a[i+k+1] - s_a[i] + s_b[i+k] - s_b[i])
        ans = max(ans, s_a[i+k+1] - s_a[i] + s_b[i+k] - s_b[i])  
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s = input()
s += 'A'
k = 0
con = []
if s[0] == '0':
    con.append(0)
c = 1
for i in range(N):
    if s[i] == s[i+1]:
        c += 1
    else:
        con.append(c)
        c = 1
if s[N-1] == '0':
    con.append(0)
k = len(con)
l = 0
r = 2*K
ans = 0
if k < r:
    ans = sum(con) 
else:
    for i in range(l,r+1):
        ans += con[i]
now = ans        
while(k > r + 1):
    now = now - con[l] - con[l+1] + con[r+1] + con[r+2]
    ans = max(ans,now)
    l += 2
    r += 2
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
 
l0 = []
l1 = []
pred = s[0]
if s[0] == "0":
    l0.append(1)
    l1.append(0)
else:
    l1.append(1)
 
for i in range(1,n):
    if pred == s[i]:
        if s[i] == "0":
            l0[-1] += 1
        else:
            l1[-1] += 1
    else:
        if s[i] == "0":
            l0.append(1)
        else:
            l1.append(1)
    pred = s[i]
if s[-1] == "0":    
    l1.append(0)
 
ans = sum(l0[:k])+sum(l1[:k+1])
tmp = ans
for i in range(k,(len(l0))):
    tmp -= l0[i-k]
    tmp -= l1[i-k]
    tmp += l0[i]
    tmp += l1[i+1]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
 
l0 = []
l1 = []
pred = s[0]
if s[0] == "0":
    l0.append(1)
    l1.append(0)
else:
    l1.append(1)
 
for i in range(1,n):
    if pred == s[i]:
        if s[i] == "0":
            l0[-1] += 1
        else:
            l1[-1] += 1
    else:
        if s[i] == "0":
            l0.append(1)
        else:
            l1.append(1)
    pred = s[i]
if s[-1] == "0":    
    l1.append(0)
 
ans = sum(l0[:k])+sum(l1[:k+1])
tmp = ans
for i in range(k,min(len(l0),len(l1))):
    tmp -= l0[i-k]
    tmp -= l1[i-k]
    tmp += l0[i]
    tmp += l1[i+1]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
#末端の処理や場合分けに困る
n,k = map(int, input().split( ))
s = input()
c0 = 0
c1 = 0
L0 = []
 
L1 = []
if s[0]=="0":
    L1 = [0]
for i in range(n):
    if s[i]=="0":
        c0+=1
        if c1!=0:
            L1.append(c1)
            c1 = 0
    else:
        c1+=1
        if c0!=0:
            L0.append(c0)
            c0 = 0
if c0:
    L0.append(c0)
if c1:
    L1.append(c1)

L1.append(0)
#print(L0,L1)
ans = sum(L0[:k])+sum(L1[:k+1])
tmp = ans
for i in range(k,min(len(L0),len(L1))):
    tmp -= L0[i-k]
    tmp -= L1[i-k]
    tmp += L0[i]
    tmp += L1[i+1]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

l = 0
alt = 0; cnt = 0

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

Submission status: Accepted

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

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

add=2*k+1
ans=0
s=[0]*(len(wa)+1)
for i in range(len(s)-1):
    s[i+1]=s[i]+wa[i]




for i in range(0,len(wa),2):
    left=i
    right=min(i+add, len(wa))
    tmp=s[right]-s[left]

    ans=max(tmp,ans)
print(ans)

Submission status: Accepted

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

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

add=2*k+1
ans=0

left=0
right=0
tmp=0
for i in range(0,len(wa),2):
    nextleft=i
    nextright=min(i+add, len(wa))

    while nextleft > left:
        tmp-=wa[left]
        left+=1
    while nextright > right:
        tmp+=wa[right]
        right+=1

    ans=max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

if len(c) <= 2*k+1:
    ans = sum(c)
else:
    ans = total = sum(c[:2*k+1])
    for i in range(0, len(c)-2*k-2, 2):
        total = total + c[i+2*k+1] + c[i+2*k+2] - c[i] - c[i+1]
        ans = max(ans, total)

print(ans)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []
ans = 0

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

# kが十分大きいなら
if len(c) <= 2*k+1:
    print(sum(c))
    sys.exit()
# TLEしたから尺取りにしたい
# for i in range(0, len(c)-2*k, 2):
#     ans = max(ans, sum(c[i:i+2*k+1]))
ans = total = sum(c[:2*k+1])
for i in range(0, len(c)-2*k-2, 2):
    total = total + c[i+2*k+1] + c[i+2*k+2] - c[i] - c[i+1]
    ans = max(ans, total)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
t = 0
tc = s[0]
s0 = s[0]
l=[]
if s0 == "0":
    l.append(0)
for c in s:
    if c ==tc:
        t+= 1
    else:
        l.append(t)
        t = 1
        tc = c
l.append(t)
if tc == "0":
    l.append(0)
res = 0
if len(l) < 2*k+1:
    print(sum(l))
else:
    suml = [0]
    for i in range(len(l)):
        suml.append(suml[i]+l[i])
    for i in range(0,len(suml)-(2*k+1),2):
        res = max(res,suml[2*k+1+i]-suml[i])
    print(res)

Submission status: Accepted

Solution code:
tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]
s = list(map(int, list(input())))

fl = []
rl = []

cnt0 = 0
cnt1 = 0
for i in range(n):
  if s[i] == 0:
    if cnt0 == 0:
      rl.append(cnt1)
      cnt1 = 0
    cnt0 += 1
  elif s[i] == 1:
    if cnt1 == 0 and i != 0:
      fl.append(cnt0)
      cnt0 = 0
    cnt1  += 1

if cnt0 != 0:
  fl.append(cnt0)
  rl.append(0)
elif cnt1 != 0:
  rl.append(cnt1)

rllen = rl[0]
for i in range(min(k, len(fl))):
  rllen += fl[i] + rl[i+1]

maxr = rllen
for i in range(max(0, len(fl)-k)):
  rllen += (fl[i+k] + rl[i+k+1])
  rllen -= (fl[i] + rl[i])
  if maxr < rllen:
    maxr = rllen 

print(maxr)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
r = 1
ans = 0
cnt = 0

for l in range(0, n):
    if l == 0:
        if s[l] == '0':
            cnt += 1

    if l > 0 and s[l] == '1' and s[l-1] == '0':
        cnt -= 1

    #while True:
    while r <= n - 1:        
        # print('\n', l, r)
        # print('count:', cnt)
        # if r > n - 1:
        #     length = r - l
        #     ans = max(ans, length)
        #     break

        if s[r] == '0' and s[r-1] == '1':
            if cnt < k:
                cnt += 1
            else:
                # print('over!')
                # length = r - l
                # ans = max(ans, length)
                break
        r += 1
    
    length = r - l
    ans = max(ans, length)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
r = 1
ans = 0
cnt = 0

for l in range(0, n):
    if l == 0:
        if s[l] == '0':
            cnt += 1

    if l > 0 and s[l] == '1' and s[l-1] == '0':
        cnt -= 1

    while True:
        # print('\n', l, r)
        # print('count:', cnt)
        if r > n - 1:
            length = r - l
            ans = max(ans, length)
            break

        if s[r] == '0' and s[r-1] == '1':
            if cnt < k:
                cnt += 1
            else:
                # print('over!')
                length = r - l
                ans = max(ans, length)
                break
        r += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import groupby
    n,k=map(int,input().split())
    s=input()
    G=groupby(s)
    A=[]
    cnt=0
    if(s[0]=='0'): A.append(0)
    for key,iter in G:
        cnt+=key=='0'
        A.append(len(list(iter)))
    if(s[-1]=='0'): A.append(0)
    if(cnt<=k):
        print(n)
        return

    n=len(A)
    now=sum(A[:2*k+1])
    score=now
    for i in range(2*k+2,n,2):
        now+=A[i]+A[i-1]-A[i-2*k-2]-A[i-2*k-1]
        score=max(score,now)
    print(score)
resolve()