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:
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))

n,k=getints()
s=input()
n=len(s)

rl = []
now, cnt = '0', 0

for i in range(n):
    if now != s[i]:
        rl.append(cnt)
        now = s[i]
        cnt = 1
    else:
        cnt += 1
if cnt > 0:
    rl.append(cnt)
acc=[0]*len(rl)
acc[0]=rl[0]
for i in range(1, len(rl)):
    acc[i] = acc[i-1]+rl[i]

# print(rl)
# print(acc)

res = 0
for i in range(len(acc)):
    if i % 2 == 0:
        i0 = i - 2
        j  = min(i + 2 * k - 1, len(acc) - 1)
    else:
        i0 = i - 1
        j  = min(i + 2 * k, len(acc) - 1)
    #print(i,i0,j)
    tmp1 = acc[i0] if i0 >= 0      else 0
    tmp2 = acc[j]  if j < len(acc) else 0
    res = max(res, tmp2-tmp1)


print(res)

Submission status: Accepted

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

right = 0
maxS = [0] * N

# 左端から順に、各点を始まりとした時の逆立ち数の最大値をしゃくとりで求める
zeroFlg = False
actCnt = 0
hsCnt = 0

# rint("action, actCnt, left, right, hsCnt")
for left in range(N):
  if left > 0 and s[left] == "1" and s[left - 1] == "0":
    actCnt -= 1
  while right < N:
    if not (actCnt < K or (actCnt == K and (s[right]=="1" or zeroFlg == True))):
      break
#    print("while", actCnt, left, right, hsCnt)
    if s[right] == "0" and zeroFlg == False:
      actCnt += 1
      zeroFlg = True
    elif s[right] == "1":
      zeroFlg = False
    hsCnt += 1
    right += 1
  right -= 1
  actCnt = min(K,actCnt)
  maxS[left] = hsCnt
  if right != N:
    hsCnt -= 1
#  print("set", actCnt, left, right, hsCnt)
  hsCnt -= 1
print(max(maxS))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(map(int,list(input())))
A = []
B = []
if S[0] == 1:
  A.append(0)
  B.append(1)
else:
  A.extend([0,1])
  B.extend([0,0])
  
for i in range(1,N):
  if S[i] == S[i-1]:
    if S[i] == 0:
      A[-1] += 1
    else:
      B[-1] += 1
  else:
    if S[i] == 0:
      A.append(1)
      B.append(0)
    else:
      A.append(0)
      B.append(1)
if B[-1] == 0:
  A.append(0)
  B.append(0)

M = len(A)
tmp = sum(A[0:2*K+1]) + sum(B[0:2*K+1])
ans = tmp
for i in range(2,M-2*K,2):
  tmp -= A[i-1] + B[i-2]
  tmp += A[i+2*K-1] + B[i+2*K]
  ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from array import array
from collections import deque
import re

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

_111_list = re.split(r'0+', S)
_000_list = re.split(r'1+', S)
if _000_list[0] == '':
    _000_list.pop(0)
if _000_list[-1] == '':
    _000_list.pop(-1)

_len_array = array('l', [0]*(len(_000_list) + len(_111_list)))
i = 0
_len_array[i] = len(_111_list.pop(0))

for _000, _111 in zip(_000_list, _111_list):
    i += 1
    _len_array[i] = len(_000)
    i += 1
    _len_array[i] = len(_111)

i_start = 0
i_end = min(len(_len_array), (K+1) + K)

_sum_max = sum(_len_array[i_start:i_end])
_sum = _sum_max

while(True):
    i_start += 2
    i_end += 2
    if i_end > len(_len_array):
        break
    _sum = _sum - _len_array[i_start-2] - _len_array[i_start-1] + _len_array[i_end-2] + _len_array[i_end-1]
    _sum_max = max(_sum_max, _sum)

print(_sum_max)

Submission status: Accepted

Solution code:

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

#N = 10 ** 5
#K = 3
#S = "01" * ((10 ** 5) // 2 )

lis = []

nowchar = -1
num = 0

for i in range(N):

        if nowchar == S[i]:

            num += 1

        elif nowchar != -1:

            lis.append([nowchar,num])

            nowchar = S[i]
            num = 1

        else:

            nowchar = S[i]
            num = 1

lis.append([nowchar,num])


nlis = []
lisst = 0
lisla = -1
zeronum = 0
summ = 0
ans = 0


while True:

    if zeronum <= K:

        ans = max(ans,summ)

        if lisla == len(lis)-1:
            break

        new = lis[lisla+1]
        lisla += 1
        #nlis.append(new)

        if new[0] == "0":
            zeronum += 1

        summ += new[1]

    else:

        old = lis[lisst]
        lisst += 1

        if old[0] == "0":
            zeronum -= 1

        summ -= old[1]

print (ans)

Submission status: Accepted

Solution code:
def solve(string):
    n, k, s = string.split()
    n, k = map(int, [n, k])
    flip = [0] + [i for i, (s0, s1) in enumerate(zip(s, s[1:]), start=1) if s0 != s1] + [n]
    start = int(s[0])
    l = len(flip) - 1
    return str(max([flip[min(l, i + 2 * k + (i % 2 ^ start))] - flip[i] for i in range(l + 1)]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, k, s = string.split()
    n, k = map(int, [n, k])
    flip = [0]
    for i, (s0, s1) in enumerate(zip(s, s[1:]), start=1):
        if s0 != s1:
            flip.append(i)
    flip += [n]
    start = int(s[0])
    l = len(flip) - 1
    return str(max([flip[min(l, i + 2 * k + (i % 2 ^ start))] - flip[i] for i in range(l + 1)]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
def solve(string):
    n, k, s = string.split()
    n, k = map(int, [n, k])
    flip = [0]
    for i, (s0, s1) in enumerate(zip(s, s[1:]), start=1):
        if s0 != s1:
            flip.append(i)
    flip += [n]
    return str(
        max([
            flip[min(len(flip) - 1, i + 2 * k + (i % 2 ^ int(s[0])))] - flip[i]
            for i in range(len(flip))
        ]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(map(int,str(input())))
if s[0]==1:
  one_st=[0]+[i+1 for i in range(n-1) if s[i]==0 and s[i+1]==1]
  zero_st=[i+1 for i in range(n-1) if s[i]==1 and s[i+1]==0]
else:
  one_st=[i+1 for i in range(n-1) if s[i]==0 and s[i+1]==1]
  zero_st=[0]+[i+1 for i in range(n-1) if s[i]==1 and s[i+1]==0]
if s[n-1]==1:
  one_en=[i for i in range(n-1) if s[i]==1 and s[i+1]==0]+[n-1]
  zero_en=[i for i in range(n-1) if s[i]==0 and s[i+1]==1]
else:
  one_en=[i for i in range(n-1) if s[i]==1 and s[i+1]==0]
  zero_en=[i for i in range(n-1) if s[i]==0 and s[i+1]==1]+[n-1]
if len(zero_st) <= k:
  x=n
else:
  y=[one_en[i+k]-one_st[i]+1 for i in range(len(zero_st)-k+1) if i+k+1<=len(one_en)]
  y=y+[one_en[k-1]+1,n-one_st[len(one_st)-k]]
  x=max(y)
print(x)

Submission status: Accepted

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

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


ans = cand = 0
for i in range(len(a)):
    cand += b[i]

    if i > 2 * k and i % 2 == 0:
        cand -= b[i-2*k-1] + b[i-2*k-2]

    if i % 2 == 0:
        ans = max(ans, cand)

print(ans)

Submission status: Accepted

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

c = 0
A = []
if S[0] == '0':
    A.append(0)
for i in range(len(S)-1):
    c += 1
    if S[i] != S[i+1]:
        if S[i] == '0':
            A.append(-c)
        else:
            A.append(c)
        c = 0
if S[-1] == '0':
    A.append(-c-1)
    A.append(0)
else:
    A.append(c+1)


if len(A)//2 <= K:
    print(sum([abs(i) for i in A]))
else:

    d = 2*K+1

    s = sum([abs(i) for i in A[:d]])
    ans = s
    for i in range(0, len(A)-d, 2):
        s = s-A[i]-abs(A[i+1])+abs(A[i+d])+A[i+d+1]
        ans = max(ans, s)
    print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

S = input()
renketu = [0]
renketu_sum = [0,0]

mozi = '1'
num = 0
for i in range(N):
	if mozi == S[i]:
		renketu[-1] += 1
		renketu_sum[-1] += 1
	else:
		renketu_sum.append(renketu_sum[-1]+1)
		renketu.append(1)
	mozi = S[i]
if len(renketu) % 2 == 0:
	renketu.append(0)
	renketu_sum.append(renketu_sum[-1])


length = 2*K + 1
if length >= len(renketu_sum):
	print(renketu_sum[-1])
else:
	max_num = 0
	for i in range(len(renketu_sum) - length):
		if i % 2 == 0:
			max_num = max(max_num, renketu_sum[i + length] - renketu_sum[i])
			#print(max_num, i, renketu,renketu_sum, length)
	print(max_num)

Submission status: Accepted

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

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

    f = '1'
    count = 0
    counts = []
    for st in s:
        if st == f:
            count += 1
        else:
            counts.append(count)
            f = str(int(f) ^ 1)
            count = 1

    counts.append(count)
    num = k*2+1

    ss = sum(counts[0:k*2+1])
    ans = ss
    for i in range(num, len(counts), 2):
        if ss > ans:
            ans = ss
        ss -= counts[i-num] + counts[i-num+1]
        ss += counts[i]
        if i+1 < len(counts):
            ss += counts[i+1]
    if ss > ans:
        ans = ss
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

count = 0
count_list = []
check = S[0]

for i in range(N):
    if S[i] == check:
         count += 1
    else:
        count_list.append(count)
        count = 1
        check = S[i]
    if i == N-1:
        count_list.append(count)

if S[0] == '0':
    count_list.insert(0, 0)
if S[-1] == '0':
    count_list.append(0)

k = min((len(count_list)-1)//2, K)

ans_list = []
for i in range((len(count_list)+1)//2 - k):
    if i == 0:
        tmp = sum(count_list[0:2*k+1])
    else:
        tmp = tmp - count_list[2*(i-1)] - count_list[(2*(i-1)+1)] 
        tmp = tmp + count_list[2*(k+i)-1] + count_list[2*(k+i)]
    ans_list.append(tmp)

print(max(ans_list))

Submission status: Accepted

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

    countlist = [0]
    if S[0] == "0":
        countlist.append(0)
    last_char = S[0]
    for s in S:
        if s == last_char:
            countlist[-1] += 1
        else:
            countlist.append(1)
            last_char = s

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

    l, r = 0, K * 2 + 1
    maxhito = last_count = sum(countlist[l:r])
    while True:
        l, r = l + 2, r + 2
        if len(countlist) < r:
            break
        count = last_count - (countlist[l - 1] + countlist[l - 2]) + (countlist[r - 1] + countlist[r - 2])
        maxhito = max(maxhito, count)
        last_count = count
    print(maxhito)


main()

Submission status: Accepted

Solution code:
import numpy as np

n,k = map(int,input().split())
comp = []
s = input()
f = s[0]
b = f
temp = 0
for c in s:
    if c == b:
        temp += 1
    else:
        comp.append(temp)
        temp = 1
        b = c
comp.append(temp)

if s[0] == "0":
    comp.insert(0,0)

if s[-1] == "0":
    comp.append(0)
# print(comp)


if 2*k+1 >= len(comp):
    print(sum(comp))
else:
    first = sum(comp[:2*k+1])
    ans = first
    # print((len(comp)-2*k+1)//2)
    # print(first)
    for i in range((len(comp)-2*k+1)//2-1):
        # print(i)
        first -= comp[i*2]
        first -= comp[i*2+1]
        first += comp[i*2+2*k+1]
        first += comp[i*2+2*k+2]
        if ans < first:
            ans = first
    print(ans)

Submission status: Accepted

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

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

ans = []
LEN = len(que)
for i in range(LEN):
    if que[i][0] == '0':
        if i + 2 * K < LEN:
            ans.append(que[i + 2 * K][1] - que[i][1])
        else:
            ans.append(N - que[i][1])
    else:
        if i + 2 * K + 1 < LEN:
            ans.append(que[i + 2 * K + 1][1] - que[i][1])
        else:
            ans.append(N - que[i][1])
            
print(max(ans))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
 
counts = [0]
if S[0] == "0":
	counts.append(0)
last_char = S[0]
for s in S:
	if s == last_char:
		counts[-1] += 1
	else:
		counts.append(1)
		last_char = s
if S[-1] == "0":
	counts.append(0)
l, r = 0, K * 2 + 1
max_count = last_count = sum(counts[l:r])
while True:
	l, r = l + 2, r + 2
	if len(counts) < r:
		break
	count = last_count - (counts[l - 1] + counts[l - 2]) + (counts[r - 1] + counts[r - 2])
	max_count = max(max_count, count)
	last_count = count
print(max_count)

Submission status: Accepted

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

tp = [0, 0]
for i in range(1, N):
  if S[i] != S[i - 1]:
    tp.append(i)
tp.extend([N, N])
    
ranges = []
if S[0] == '1':
  l = 1
else:
  l = 0

r = l + 2 * K + 1
while r < len(tp):
  ranges.append(tp[r] - tp[l])
  l += 2
  r += 2
  
if len(ranges) == 0:
  ranges.append(N)
  
print(max(ranges))

Submission status: Accepted

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

	counts = [0]
	if S[0] == "0":
		counts.append(0)
	last_char = S[0]
	for s in S:
		if s == last_char:
			counts[-1] += 1
		else:
			counts.append(1)
			last_char = s
	if S[-1] == "0":
		counts.append(0)
	# print(counts)
	l, r = 0, K * 2 + 1
	max_count = last_count = sum(counts[l:r])
	while True:
		l, r = l + 2, r + 2
		if len(counts) < r:
			break
		count = last_count - (counts[l - 1] + counts[l - 2]) + (counts[r - 1] + counts[r - 2])
		max_count = max(max_count, count)
		last_count = count
	print(max_count)

main()

Submission status: Accepted

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

before = S[0]
cnt = 0
same_nums = []
if S[0] == '0':
  same_nums.append(0)
for i in range(N):
  if S[i] == before:
    cnt += 1
  else:
    same_nums.append(cnt)
    before = S[i]
    cnt = 1
same_nums.append(cnt)
if S[-1] == '0':
  same_nums.append(0)
  
sum_nums = sum(same_nums[:2*K+1])
ans = sum_nums
for i in range(0, len(same_nums)-2*K, 2):
  sum_nums = sum_nums - sum(same_nums[i:i+2]) + sum(same_nums[i+2*K+1:i+2*K+3])
  ans = max(ans, sum_nums)
print(ans)

Submission status: Accepted

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

T = []
c = 1
for i in range(1, len(S)) :
    if S[i] == S[i-1] :
        c += 1
    else :
        T.append(c)
        c = 1
        
for i in range(1, len(T)) :
    T[i] += T[i-1]

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

ret = 0
for i in range(0 if S[0] == '1' else 1, len(T), 2) :
    if i - 2*K - 1 < 0 :
        ret = max(ret, T[i])
    else :
        ret = max(ret, T[i] - T[i-2*K-1])
    
print(ret)

Submission status: Accepted

Solution code:
import re

N,K = map(int, input().split())
S = str(input())
s1 = list(S)
right = 0
count_0 = 0
ans = 0

for left in range(N):
  while right<N and count_0 <=K:
    if s1[0] == "0" and right == 0:
      count_0 += 1
    elif s1[right] == "0" and s1[right-1] == "1":
      count_0 += 1
    right += 1
    
    if count_0 <= K:
      #print(right,left,count_0)
      ans = max(ans, right-left)
  if left != N-1:
    if s1[left] == "0" and s1[left+1] =="1":
      count_0 -= 1
    
print(ans)

Submission status: Accepted

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

n = 1
c = []
if S[0]=='0': c.append(0)
for i in range(1,N):
    if S[i]!=S[i-1]:
        c.append(n)
        n=1
    else:
        n+=1
c.append(n)
if S[-1]=='0': c.append(0)

t = sum(c[:2*K+1])
m = t
for i in range(2*K+1, len(c), 2):
    t += c[i] + c[i+1] - c[i-(2*K+1)] - c[i+1-(2*K+1)]
    m = max(m,t)

print(m)

Submission status: Accepted

Solution code:
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

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

A = []
Aa = A.append
c = 0
b = 1
for s in S:
    if s!=b:Aa(c);b=s;c=0
    c+=1
Aa(c)
if len(A)%2==0:Aa(0)

SA = cumulative_sum(A)

ans = 0
ul = len(A)
for i in range(N):
    r = min(2*(i+K)+1,ul)
    ans = max(ans,SA.get(2*i,r))
    if r==ul:break
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
l,tmpl,cnt0,tmp,flag1,flag2=[],0,0,s[0],0,0
if tmp=="0":cnt0+=1;flag1=1
for i in s:
    if i==tmp:tmpl+=1
    else:
        if i=="0":cnt0+=1
        tmp=i
        l.append(tmpl)
        tmpl=1
if tmp=="0":flag2=1
l.append(tmpl)
if cnt0<=k:print(n);exit()
ans=max(sum(l[:2*k]),sum(l[::-1][:2*k]))
suml,tmp=[0],0
if flag1==1:l=l[1:]
if flag2==1:l=l[:len(l)-1]
for i in l:
    tmp+=i
    suml.append(tmp)
for i in range((len(suml)-2*k-1)//2+1):
    tmp=suml[2*k+2*i+1]-suml[2*i]
    if tmp>ans:ans=tmp
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
pre = S[0]
partl = [0]
for i, s in enumerate(S[1:], 1):
    if pre != s:
        partl.append(i)
    pre = s
partl.append(N)

ans = 0
for i in range(len(partl)):
    if partl[i] == N:
        break
    elif S[partl[i]] == '1':
      ans = max(ans, partl[min(i+K*2+1, len(partl)-1)] - partl[i])
    else:
      ans = max(ans, partl[min(i+K*2, len(partl)-1)] - partl[max(0, i-1)])

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S_list = ['0'] + list(input()) + ['-1']

s_count_list =[]

cnt = 1
for i in range(1,N+2) :
    if S_list[i] == S_list[i-1] :
        cnt +=1
    else:
        s_count_list.append(cnt)
        cnt = 1
if S_list[1] == '0':
    s_count_list[0] = s_count_list[0] -1
    s_count_list.insert(0,0)
else:
    s_count_list.pop(0)

ruisekiwa = [0]
for i,s in enumerate(s_count_list):
    ruisekiwa.append(ruisekiwa[i] + s)

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

answer =  1
#print(s_count_list)
#Jjkprint(ruisekiwa)
for i in range(0,len(s_count_list),2):
    left = i
    right = min((i + (2 * K) + 1),len(s_count_list))
    #print(left,right)
    #print(ruisekiwa[right])
    tmp = ruisekiwa[right] - ruisekiwa[left]
    answer = max(tmp,answer)

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,K=map(int,input().split())
S=input()
Snumber=[]
count=0
 
for i in range(N):
    if i==0 or S[i-1]==S[i]:
        count=count+1
    else:
        Snumber.append(count)
        count=1
Snumber.append(count)
 
ans=0
C=0
 
if 1+2*K>len(Snumber):
    ans=len(S)
elif S[0]=="0":
    temporary=sum(Snumber[1:2+2*K])
    j=1
    while 1+2*K+j*2<=len(Snumber)-1:
        temporary=temporary-Snumber[2*j-1]-Snumber[2*j]+Snumber[2*K+2*j]+Snumber[1+2*K+2*j]
        if temporary>ans:
            ans=temporary
        j=j+1
    if len(Snumber)%2==1:
        C=sum(Snumber[len(Snumber)-2*K:])
    ans=max(ans,sum(Snumber[:2*K]),C)
elif S[0]=="1":
    temporary=sum(Snumber[0:1+2*K])
    j=1
    while 2*K+j*2<=len(Snumber)-1:
        temporary=temporary-Snumber[2*j-2]-Snumber[2*j-1]+Snumber[2*K+2*j-1]+Snumber[2*K+2*j]
        if temporary>ans:
            ans=temporary
        j=j+1
    if len(Snumber)%2==0:
        C=sum(Snumber[len(Snumber)-2*K:])
    ans=max(ans,C)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
s = s + '#'
left = 0
right =0
l = []
while left < n:
    if s[right] == s[right+1]:
        right += 1
    else:
        l.append(right-left+1)
        right += 1
        left = right
if s[0] == '0':
    l.insert(0,0)
if s[n-1] == '0':
    l.append(0)
n = len(l)
l_sum = [0]*(n)
l_sum[0] = l[0]
for i in range(1,n):
    l_sum[i] = l[i] + l_sum[i-1]
if n <= 2*k + 1:
    print(l_sum[n-1])
else:
    res = l_sum[2*k]
    for i in range(2,n-2*k,2):
        res = max(res,l_sum[i+2*k]-l_sum[i-1])
    print(res)

Submission status: Accepted

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

ans = L = R = 0

while R < N:
    if S[R] == '0':
        while R < N and S[R] == '0':
            R += 1
        while S[R] == '1':
            R += 1
        K -= 1
        if K <= 0:
            ans = max(ans, R-L)

            while L < N and S[L] == '1':
                L += 1
            while L < N and S[L] == '0':
                L += 1
    else:
        R += 1
    ans = max(ans, R-L)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC124 D
from itertools import accumulate
import bisect
n,k = map(int,input().split())
s = list(map(int,list(input())))
#0→1 または 1→0 の切り替わるときに連続する数を入れるlist
L = [0] if s[0] == 1 else [0,0]
cnt = 1
for i in range(1,n):
    if s[i-1] != s[i]:
        L += [cnt]
        cnt = 0
    cnt += 1
L += [cnt,0]
L = list(accumulate(L))
ans = 0
if len(L) - 2*k - 1 < 1:
    print(L[-1])
    quit()
for i in range(0,len(L)-2*k-1,2):
    ans = max(ans,L[i+2*k+1] - L[i])
print(ans)

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = input()
d = []
e = 0
for i in range(1, a):
    e += 1
    if c[i] != c[i-1]:
        if c[i] == "0":
            d.append(e)
        else:
            d.append(-e)
        e = 0
    if i == (a-1):
        e += 1
        if c[i] == "1":
            d.append(e)
        else:
            d.append(-e)
        e = 0
f = 0
g = 0
h = 0
for i in range(len(d)):
    g += abs(d[i])
    if d[i] > 0 and f >= b:
        h = max(h, g)
        if i-2*b >= 0:
            g -= abs(d[i-2*b])
    if d[i] < 0 and f >= b:
        g -= abs(d[i-2*b])
    if d[i] < 0 and f < b:
        f += 1
h = max(h, g)
print(h if h != 0 else a)

Submission status: Accepted

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

slid = []
for i in range(n):
    if i == 0:
        slid.append(0)
        continue
    if s[i] != s[i-1]:
        slid.append(i-1)
        slid.append(i)
slid.append(n-1)

zone = []
for j in range(len(slid)//2):
    zone.append([slid[j*2], slid[j*2+1]])

front = s[0]
n_zone = len(zone)
if n_zone%2 == 0:
    n_zone0 = n_zone//2
elif front == "0":
    n_zone0 = (n_zone+1)//2
else:
    n_zone0 = (n_zone-1)//2

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

ans = 0
if front == "1":
    now = 0
else:
    ans = zone[k*2-1][1]+1
    now = 1

while True:
    if now+k*2-1 >= n_zone:
        break
    ans = max(ans, zone[now+k*2-1][1]-zone[now][0]+1)

    if now+k*2 >= n_zone:
        break
    ans = max(ans, zone[now+k*2][1]-zone[now][0]+1)
    now += 2

print(ans)

Submission status: Accepted

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

blk_num = []
blk_sum = []
for i in range(len(s)):
  if i == 0 or s[i-1]!=s[i]:
    if i!= 0:
      blk_sum.append(n)
    blk_num.append(s[i])
    n = 0
  n += 1

blk_sum.append(n)

def cumsum(x):
    y = []
    current = 0
    for i in x:
        y.append(current + i)
        current += i
    return y

blk_csum = cumsum(blk_sum)
# iblkの始点を1が連続する箇所の始点とするときの数を見る

mx = 0
for i, n in enumerate(blk_num):
  if n == '0':
    endi = i + 2*k - 1
    endi = min(len(blk_num)-1, endi)
    if i == 0:
      sm = blk_csum[endi]
    else:
      continue
  else:
    endi = i + 2*k
    endi = min(len(blk_num)-1, endi)
    if i == 0:
      sm = blk_csum[endi]
    else:
      sm = blk_csum[endi] - blk_csum[i-1]
  if sm > mx:
    mx = sm
print(mx)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input()
I = []
for j in range(len(s)):
    if j == 0:
        I.append(0)
    else:
        if s[j-1] != s[j]:
            I.append(j)
r = len(I)
I = I + [N] * (3*K)
x = []
for k in range(r):
    if s[I[k]] == '0':
        x.append(I[k+2*K] - I[k])
    else:
        x.append(I[k + 2 * K + 1] - I[k])
print(max(x))

Submission status: Accepted

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

t = []
if s[0] == '0':
    t.append(0)

c0 = 0
c1 = 0
for ss in s:
    if ss == '0':
        if c1 > 0:
            t.append(c1)
            c1 = 0
        c0 += 1
    else:
        if c0 > 0:
            t.append(c0)
            c0 = 0
        c1 += 1

if c1 > 0:
    t.append(c1)
if c0 > 0:
    t.append(c0)

if s[-1] == '0':
    t.append(0)

c_t = [0]
for tt in t:
    c_t.append(c_t[-1] + tt)

k2 = min(k, len(t) // 2)
ans = 0
j = 0
for i in range(k2 * 2 + 1, len(c_t), 2):
    ans = max(ans, c_t[i] - c_t[j])
    j += 2

# print(c_t)
print(ans)

Submission status: Accepted

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

t = []
if s[0] == '0':
    t.append(0)

c0 = 0
c1 = 0
for ss in s:
    if ss == '0':
        if c1 > 0:
            t.append(c1)
            c1 = 0
        c0 += 1
    else:
        if c0 > 0:
            t.append(c0)
            c0 = 0
        c1 += 1

if c1 > 0:
    t.append(c1)
if c0 > 0:
    t.append(c0)

if s[-1] == '0':
    t.append(0)

c_t = [0]
for tt in t:
    c_t.append(c_t[-1] + tt)

k2 = min(k, len(t) // 2)
ans = 0
for i in range(1, len(c_t), 2):
    j = i - k2 * 2 - 1
    if j < 0:
        continue
    ans = max(ans, c_t[i] - c_t[j])

# print(c_t)
print(ans)

Submission status: Accepted

Solution code:
def cumsum(a):
    res = [0] * (len(a) + 1)
    for i in range(len(a)):
        res[i + 1] += res[i] + a[i]
    return res


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

t = []
x = 1
x_repeats = 0
i = 0
while i < n:
    if s[i] == x:
        x_repeats += 1
    else:
        t.append(x_repeats)
        x ^= 1
        x_repeats = 1
    i += 1
t.append(x_repeats)


cumsum_t = cumsum(t)

ans = 0
for left in range(0, len(cumsum_t), 2):
    right = min(2 * k + left + 1, len(cumsum_t) - 1)
    ans = max(ans, cumsum_t[right] - cumsum_t[left])

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
X=[]
j="1"
num=0
for i in S:
    if j!=i:
        X.append(num)
        j=i
        num=1
    else:
        num+=1
X.append(num)

if j=="0":
    X.append(0)
Y=[0]
for i in X:
    Y.append(Y[-1]+i)
ans=0
for i in range(1,len(Y),2):
    t=min(i+2*K,len(Y)-1)
    ans=max(ans,Y[t]-Y[i-1])
print(ans)

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y: return x
	return y

N, K = map(int, input().split())
S = input()
cnt = 1
standlist = []
for i in range(1, N):
	if S[i-1] != S[i]:
		standlist.append(cnt)
		cnt = 1
	else:
		cnt += 1
standlist.append(cnt)
if S[0] == '0':
	standlist = [0] + standlist
if S[-1] == '0':
	standlist.append(0)
sumlist = [standlist[0]]
for i in range(1, len(standlist)):
	sumlist.append(sumlist[-1]+standlist[i])
srchlen = 2 * K + 1
max = 0
if srchlen > len(sumlist):
	max = sumlist[-1]
else:
	index = 0
	while index + srchlen - 1 < len(sumlist):
		sum = sumlist[index+srchlen-1]
		if index != 0:
			sum -= sumlist[index-1]
		max = larger(sum, max)
		index += 2
print(max)

Submission status: Accepted

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

if s[0] == "0":
    s_num = [0]
else:
    s_num = []
pre = s[0]
num = 0

for i in s:
    if pre == i:
        num += 1
    else:
        s_num.append(num)
        num = 1
        pre = "1" if pre == "0" else "0"
else:
    s_num.append(num)

sums = [0]

for i,e in enumerate(s_num):
    sums.append(sums[i] + e)

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

Submission status: Accepted

Solution code:
def compress(list01):
    newList=[]
    n=len(list01)
    now=1
    count0=0
    count1=0
    list01.append((list01[-1]+1)%2)
    for i in range(n+1):
        nex=list01[i]
        if now==0:
            if nex==0:
                count0+=1
            if nex==1:
                count1+=1
                newList.append(count0)
                count0=0
        if now==1:
            if nex==0:
                count0+=1
                newList.append(count1)
                count1=0
            if nex==1:
                count1+=1
        now=nex
    if list01[-2]==0:
        newList.append(0)
    return newList

def measure_insect(mixed_list,k):
    n=(len(mixed_list)-1)//2
    now=sum(mixed_list[:2*k+1])
    maximum=now
    for i in range(n-k):
        now-=mixed_list[2*i]
        now-=mixed_list[2*i+1]
        now+=mixed_list[2*i+2*k+1]
        now+=mixed_list[2*i+2*k+2]
        if now>maximum:
            maximum=now
    return maximum

N,K=map(int,input().split())
S=[int(_) for _ in input()]

print(measure_insect(compress(S),K))

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, K = i2nn()
    S = i2s()
    # 圧縮
    d = []
    t = S[0]
    n = 1
    for i in range(1, N):
        s = S[i]
        if s == t:
            n += 1
        else:
            d.append((t, n))
            t = s
            n = 1
    d.append((t, n))
    # 場合分けの統一
    if d[0][0] == '0':
        d = [('1', 0)] + d
    if d[-1][0] == '0':
        d.append(('1', 0))
    # 累積和
    r = [0] * (len(d) + 1)
    for i, (s, t) in enumerate(d):
        r[i+1] = r[i] + t
    # 答え
    w = K * 2 + 1
    n = -1
    #print(w, len(r))
    for i in range(w, len(r), 2):
        t = r[i] - r[i-w]
        #print(t)
        if t > n:
            n = t
    if n == -1:
        #print('n = -1')
        n = r[-1]
    #print(d)
    #print(r)
    print(n)

main()