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 = input()
cnt = 0
init = (s[0]=='1')
h=[1]
h_cnt = 0

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

h_cnt+=1

zero_num = 0
ans = 0

if(init): #start with 1
    zero_num = h_cnt//2;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2+1])
        ans = sum_0
        h = h +[0,0,0]
        for j in range(0,zero_num-k): #j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

else: #start with 0
    zero_num = h_cnt//2 +1;
    if(zero_num<=k):
        ans = n
    else:
        sum_0 = sum(h[0:k*2])
        ans = sum_0
        h = [0] + h +[0,0,0]
        for j in range(0,zero_num-k):#j is 0's order
            sum_0 = sum_0 - h[j*2] - h[j*2+1] + h[(j+k)*2+1] + h[(j+k)*2+2]
            if(ans<=sum_0):
                ans = sum_0

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split(" "))
s = input()
l = []
if s[0] == "0":
    l.append((0, 0))
i = 0
while i < n:
    if s[i] == "1":
        b = i
        while i < n and s[i] == "1":
            i += 1
        l.append((b, i))
    i += 1
if s[n-1] == "0":
    l.append((n, n))
if len(l)-1 <= k:
    print(n)
else:
    maximum = 0
    for i in range(len(l)-k):
        maximum = max(maximum, l[i+k][1]-l[i][0])
    print(maximum)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
l = []
if S[0] == '0':
  l.append(0)
p = S[0]
cnt = 0
for c in S:
  if c == p:
    cnt += 1
  else:
    l.append(cnt)
    cnt = 1
  p = c
l.append(cnt)
if S[-1] == '0':
  l.append(0)

# print(l)
top = 0
ll = 2*K+1
m = min(ll, len(l))
for i in range(m):
  top += l[i]
# print(top)
t = top
for i in range(2, len(l)-(ll)+1, 2):
  t = t - l[i-2] - l[i-1] + l[i+ll-2] + l[i+ll-1]
  # print('%d: %d' % (i, t))
  if t > top:
    top = t
print(top)

Submission status: Accepted

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

if n == 1:
    print(1)
    exit(0)

l = []
if s[0] == "0":
    l.append(0)

temp = 1
for i in range(1, n):
    if s[i] == s[i - 1]:
        temp += 1
        if i == n - 1:
            l.append(temp)
    else:
        l.append(temp)
        temp = 1
        if i == n - 1:
            l.append(temp)

if s[-1] == "0":
    l.append(0)

ans = 0

b = []
b.append(l[0])
for i in range(1, len(l)):
    b.append(b[-1] + l[i])


if 2 * k + 1 > len(l) - 1:
    print(b[len(l) - 1])
    exit(0)
else:
    ans = b[2 * k]


for i in range(1, len(l)):
    if i * 2 + 2 * k > len(l) - 1:
        break
    ans = max(ans, b[min(i * 2 + 2 * k, len(l) - 1)] - b[i * 2 - 1])
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate

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

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = max(
    A[min(2 * K - 1, len(A) - 1)],
    A[-1] - A[max(-(2 * K), -len(A))],
    max(
        (
            a - b
            for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
        ),
        default=0
    )
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate

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

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = (
    max(
        A[min(2 * K - 1, len(A) - 1)],
        A[-1] - A[max(-(2 * K), -len(A))],
        max(
            (
                a - b
                for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
            ),
            default=0
        )
    ) if m < len(A) else
    A[-1]
)

# 出力
print(ans)

Submission status: Accepted

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

Nums = []
now = 1#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now#０と１の切り替え
        cnt = 1#新しいのをカウントし始める
if cnt != 0:Nums.append(cnt)

#長さが２の倍数であるならば任意の数を最後に加える．ながさを奇数倍にしたい
if len(Nums) % 2 == 0:Nums.append(0)
sum = [0]*(len(Nums)+1)

for i in range(len(Nums)):
    sum[i+1] = sum[i] + Nums[i]

add = 2 * k + 1
ans = 0

for i in range(0,len(sum),2):
    tmp = 0
    left = i
    right = min(i+add,len(Nums))
    tmp = sum[right] - sum[left]
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
S = input()+'!'
A = [0]
tmp = 1
for i in range(1,n+1):
    if S[i] == S[i-1]:
        tmp += 1
    else:
        A.append(tmp)
        tmp = 1
for i in range(1,len(A)):
    A[i] += A[i-1]
#print(A)
res = 0
if S[0] == '0':
    for i in range(len(A)):
        if i%2 == 0:
            ans = A[min(i+2*k,len(A)-1)]-A[i]
        else:
            ans = A[min(i+2*k+1,len(A)-1)]-A[i]
        if res <= ans:
            res = ans
else:
    for i in range(len(A)):
        if i%2 == 0:
            ans = A[min(len(A)-1,i+2*k+1)]-A[i]
        else:
            ans = A[min(i+2*k,len(A)-1)]-A[i]
        if res <= ans:
            res = ans

print(res)

Submission status: Accepted

Solution code:
N, K = map(int, input().split(" "))
S = input()
ans = 0
count_0 = []
count_1 = []

tmp = 0
now_is_0 = True
if S[0] == "1":
    now_is_0 = False

for i, c in enumerate(S):
    if c == "0":
        if now_is_0:
            tmp += 1
        else:
            count_1.append(tmp)
            now_is_0 = True
            tmp = 1
    else:
        if now_is_0:
            count_0.append(tmp)
            now_is_0 = False
            tmp = 1
        else:
            tmp += 1
if now_is_0:
    count_0.append(tmp)
else:
    count_1.append(tmp)

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

if S[0] == "0":
    count_1 = [0, ] + count_1
if S[N-1] == "0":
    count_1 = count_1 + [0, ]

tmp_ans = sum(count_0[:K] + count_1[:K+1])
max_ans = tmp_ans

i = 0
length = len(count_1)
while K+i+1 < length:
    tmp_ans -= count_1[i]
    tmp_ans -= count_0[i]

    tmp_ans += count_0[K+i]
    tmp_ans += count_1[K+1+i]
    max_ans = max(tmp_ans, max_ans)
    i += 1
print(max_ans)

Submission status: Accepted

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

if S[N-1] == '1':
    S += '0'
else:
    S += '1'

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

n = len(memo)
for i in range(2*K+1):
    memo.append(N+1)

m = 0
l = []
if S[0] == '1':
    for i in range(n):
        if i%2 == 0:
            l.append(memo[i+2*K+1]-memo[i])
        else:
            l.append(memo[i+2*K]-memo[i])



        # if s > m:
        #     m = s
else:
    for i in range(n):
        if i%2 == 1:
            l.append(memo[i+2*K+1]-memo[i])
        else:
            l.append(memo[i+2*K]-memo[i])


        # if s > m:
        #     m = s

print(max(l))

Submission status: Accepted

Solution code:
import numpy as np

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

State = [0] * N
counter0 = 0
counter1 = 0
flag = -1
jj = 0
for i in range(N):
    if S[i] == '0':
        if flag == 1:
            State[jj] = counter1
            jj +=1
            counter1 = 0
        counter0 += 1
        flag = 0
    if S[i] == '1':
        if flag == 0:
            State[jj] = counter0
            jj += 1
            counter0 = 0
        counter1 += 1
        flag = 1
    if i == N-1:
        State[jj] = max(counter0,counter1)
        
N2 = np.count_nonzero(State)
State = int(S[0] == '0') * [0] + State[:N2] + int(S[N-1] == '0') * [0]
N2 = len(State)
ans = 0
total = 0
K2 = 2*K+1

if K2 >= N2:
    K2 = N2

for i in range(K2):
    total += State[i]
        
ans = total
for i in range(0,N2-K2,2):
    total2 = total - State[i] - State[i+1] + State[i+K2] + State[i+1+K2]
    ans = max(ans,total2)
    total = total2
    
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
new_S = []
count_S = []

cur_c = S[0]
cur_count = 0

new_S.append(cur_c)
for c in S:
    if c == cur_c:
        cur_count += 1
    else:
        new_S.append(c)
        count_S.append(cur_count)
        cur_count = 1
        cur_c = c
count_S.append(cur_count)        

new_count = []
st_ix = 0
if S[0] == '0':
    cur_sum = sum(count_S[:2*K])
    st_ix = 1
    new_count.append(cur_sum)
else:
    cur_sum = sum(count_S[:2*K+1])
    new_count.append(cur_sum)

en_ix = st_ix + 2*K + 1
cur_sum = sum(count_S[st_ix:en_ix])
new_count.append(cur_sum)

while en_ix < len(count_S):
    # shift st_ix
    st_ix = st_ix + 2
    en_ix = en_ix + 2
    if en_ix >= len(count_S):
        new_count.append(sum(count_S[st_ix:]))
    else:
        cur_sum -= (count_S[st_ix-2] + count_S[st_ix-1])
        cur_sum += (count_S[en_ix-2]
                        + count_S[en_ix-1])
    new_count.append(cur_sum)

print(max(new_count))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

nums = []
tmp = "1" #はじめに0が入ったら、0からスタートというのがわかる。
count = 0
for s in S:
    if tmp == s:
        count += 1
    else:
        nums.append(count)
        count = 1
        tmp = s
nums.append(count)
if tmp == "0":
    nums.append(0) #エッジの条件

# print(nums)
# 累積和表示にする(listって足し算できるのね)
# これによって、各文字最初の値が明らかになる
acc = [0]+list(accumulate(nums))
# print(acc)
n = len(nums)
w = 2*K + 1

if len(nums) <= w:
    print(N)
else:
    ans = 0
    for i in range(0,n-w+1,2): #2個飛ばし
        ans = max(ans,acc[i+w]-acc[i])

    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left

def main():
	N, K = map(int, input().split(" "))
	S = input()
		
	S0 = S.split("0")
	S1 = S.split("1")
	
	S0 = [x for x in S0 if x]
	S1 = [x for x in S1 if x]
	
	if K == 0:
		ans = 0
		for val in S0:
			tmp = len(val)
			if tmp > ans:
				ans = tmp
		print(ans)
		sys.exit()
		
	if K >= len(S1):
		print(len(S))
		sys.exit()
	
	fst = []
	snd = []
	guu = False
	kii = False
	if S[0] == "1":
		fst = S0
		snd = S1
		kii = True
	else:
		fst = S1
		snd = S0
		guu = True
	
	ansList = []
	while True:
		if len(fst) != 0:
			ansList.append(fst.pop(0))
		if len(snd) != 0:
			ansList.append(snd.pop(0))
		if len(fst) == 0 and len(snd) == 0:
			break
			
	total = []
	for i, val in enumerate(ansList):
		if i == 0:
			total.append(len(val))
			continue
		total.append(total[i-1] + len(val))
	
	ans = 0
	if kii == True:
		for i, val in enumerate(total):
			tmp = 0
			if i == 0:
				tmp = total[2 * K]
			elif i % 2 == 1:
				tmptmp = i+1+(K-1)*2
				if tmptmp >= len(total):
					tmptmp = len(total)-1
				tmp = total[tmptmp] - total[i-1]
			else:
				tmptmp = i+K*2
				if tmptmp >= len(total):
					tmptmp = len(total)-1
				tmp = total[tmptmp] - total[i-1]
			
			if ans < tmp:
				ans = tmp
	else:
		for i, val in enumerate(total):
			tmp = 0
			if i == 0:
				tmp = total[2 * (K-1) + 1]
			elif i % 2 == 1:
				tmptmp = i + K*2
				if tmptmp >= len(total):
					tmptmp = len(total)-1
				tmp = total[tmptmp] - total[i-1]
			else:
				tmptmp = i+1+(K-1)*2
				if tmptmp >= len(total):
					tmptmp = len(total)-1
				tmp = total[tmptmp] - total[i-1]
			
			if ans < tmp:
				ans = tmp
	
	print(ans)
		
	
if __name__ == "__main__":
	main()

Submission status: Accepted

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

for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
right = 0
left = 0
g = 0
su = 0
if A[0] == 0:
    for i in range(len(s)):
        su +=s[right]
        if right%2==0:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==0:
                  g -=1
              left +=1
        a = max(a,su)
else:
    for i in range(len(s)):
        su +=s[right]
        if right%2==1:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==1:
                  g -=1
              left +=1
        a = max(a,su)

print(a)

Submission status: Accepted

Solution code:
import collections
n, k = map(int, input().split())
s = [int(i) for i in input()]
c = []
prv = 1
cnt = 0
for i in s:
    if prv != i:
        c.append(cnt)
        cnt = 1
        prv = i
    else:
        cnt += 1
if cnt > 0:
    c.append(cnt)
if prv == 0:
    c.append(0)
que = collections.deque([c[0]])
res =c[0]
ans = c[0]
m = len(c) // 2
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: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)
if s[-1]=='0':
	m=2*k
else:
	m=2*k+1
t=4*k+1
_max=0
i=len(a)-1
if i- m<0:
	print(n)
else:
	while i-m>=0:
		tmp=a[i]-a[i-m]
		#print('i:{} tmp:{}'.format(i,tmp))
		if tmp>_max:
			_max=tmp
		m=t-m
		i-=1
	if a[i]>_max:
		_max=a[i]
	print(_max)

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
S = input()
cnt = [0]
flag = False
for c in S:
    if c == '0':
        if flag:
            cnt.append(cnt[-1])
        else:
            flag = True
            cnt.append(cnt[-1] + 1)
    else:
        cnt.append(cnt[-1])
        flag = False
ans = 0
left, right = 0, 0
while right < N:
    while right < N:
        right += 1
        if right < N:
            if S[right - 1] == '1' and S[right] == '0':
                break
        else:
            break
    if cnt[right] - cnt[left] <= K:
        ans = max(ans, right - left)
    else:
        while left < N:
            left += 1
            if S[left - 1] == '0' and S[left] == '1':
                break
        if cnt[right] - cnt[left] <= K:
            ans = max(ans, right - left)
print(ans)

Submission status: Accepted

Solution code:
import sys
N, K = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
S = input()
cnt = [0]
flag = False
for c in S:
    if c == '0':
        if flag:
            cnt.append(cnt[-1])
        else:
            flag = True
            cnt.append(cnt[-1] + 1)
    else:
        cnt.append(cnt[-1])
        flag = False
ans = 0
left, right = 0, 0
while right < N:    # right を右端まで移動させる
    while right < N:
        right += 1
        # print('right was +1. left = {}, right = {}'.format(left, right))
        if right < N:
            if S[right - 1] == '1' and S[right] == '0':
                # print('right is correct')
                break
        else:
            break
    if cnt[right] - cnt[left] <= K:
        ans = max(ans, right - left)
        # print('cnt[right] - cnt[left] = {}'.format(cnt[right] - cnt[left]))
        # print('    left - right = {}'.format(right - left))
    else:
        # print('too long')
        while left < N:
            left += 1
            # print('left was +1. left = {}, right = {}'.format(left, right))
            if S[left - 1] == '0' and S[left] == '1':
                # print('left is correct')
                break
        if cnt[right] - cnt[left] <= K:
            ans = max(ans, right - left)
            # print('cnt[right] - cnt[left] = {}'.format(cnt[right] - cnt[left]))
            # print('    left - right = {}'.format(right - left))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s = input()
#first
last = -1
ck = K
pre = ''
for i in range(N):
    c = s[i]
    if c == '0' and pre != '0':
        ck -= 1
        if ck < 0:
            last = i - 1
            break
    pre = c
else:
    last = N-1
#print('last:',last)

if last == N-1:print(len(s))
else:
    ## step by step
    cameLast = False
    ilr = 0
    g_max = 0
    while True:
        #print('calc g.:',last - ilr + 1)
        g_max = max(g_max,last - ilr + 1)
        if cameLast:break
        pre = ''
        for i in range(ilr,N):
            if s[i] == '1' and pre == '0':
                ilr = i
                break
            else:pre = s[i]
        else:#print('CANNOT REACH HERE!! - no next ilr')
            ilr = len(s) - 1
        prel = ''
        for j in range(last+1,N):
            if s[j] == '0' and prel == '1':
                last = j - 1
                break
            else:prel = s[j]
        else:#'reach last s[]'
            last = len(s) - 1
            cameLast = True
    print(g_max)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S= input()
i,j = 0,0
onenumber = [0] * (K+1)
zeronumber = [0] * K
test, answer = 0,0
infront = ''

for x in S:
    if x == '0':
        if infront == '1':
            test += onenumber[j]
            answer = max(answer,test)
            if j == K:
                j = -1
            j += 1
            if i == K:
                i = 0
            test -= onenumber[j]
            test -= zeronumber[i]
            onenumber[j],zeronumber[i] = 0, 0
        zeronumber[i] += 1
        infront = '0'
    if x == '1':
        if infront == '0':
            test += zeronumber[i]
            i += 1
        onenumber[j] += 1
        infront = '1'

if S[-1] == '0':
    test += zeronumber[i]
else:
    test += onenumber[j]
answer = max(answer,test)
print(answer)

Submission status: Accepted

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

change_flg = False
cnt = 0
ilands = []


def cumsum(array):
    value = array[0]
    results = [value] * len(array)
    for index, elm in enumerate(array[1:], 1):
        value += elm
        results[index] = value
    return results


def change():
    global cnt, change_flg
    ilands.append(cnt)
    cnt = 0
    change_flg = not change_flg

for value in s:
    if value: # case 1 cnt
        if change_flg:
            change()
    else: # case 0 cnt : plus
        if not change_flg:
            change()
    cnt += 1

ilands.append(cnt)

if not len(ilands) % 2:
    ilands.append(0)

merged = list(cumsum(ilands))
section = 2 * k + 1

results = [0] * (len(ilands) // 2 - (k - 1))
if len(results) < 1 or len(merged) < section:
    print(n)
    exit()

merged.append(0)
for i in range(len(results)):
    start = i * 2 - 1
    results[i] = merged[start + section] - merged[start]

print(max(results))

Submission status: Accepted

Solution code:
import itertools

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

# list of run-length
runlen = [len(list(g)) for k, g in itertools.groupby(S)]

# runlen starts and ends with the length of a run of '1'
if S[0] == '0':
    runlen = [0] + runlen
if S[-1] == '0':
    runlen = runlen + [0]

# list of sum of runlen[i : i + k]
k = 2 * K + 1
s = sum(runlen[:k])
sublen = [s]
for i in range(2, N - k, 2):
    s -= sum(runlen[i - 2 : i])
    s += sum(runlen[i - 2 + k : i + k])
    sublen.append(s)

print(max(sublen))

Submission status: Accepted

Solution code:
# reffer https://qiita.com/hironobukawaguchi3/items/55e751ecf72bb7894a46
N, K = map(int, input().split())
S = input()
Nums = []
now = 1 # 今見ている数
cnt = 0 # nowがいくつならんでいるか

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

if cnt != 0:
  Nums.append(cnt)

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

Add = 2 * K + 1
sum = [0] * (len(Nums) + 1)
for i in range(len(Nums)):
  sum[i + 1] = sum[i] + Nums[i]
ans = 0
for i in range(0, len(Nums), 2):
  left = i
  right = min(i + Add, len(Nums))
  tmp = sum[right] - sum[left]
  ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
N,K = (int(num) for num in input().split())
S = input()
pos_10 = []
chgpos = []
if S[0] == "0":
    chgpos.append((0,0))
cur = "0"
a,b = 0,0
for i in range(N):
    if cur=="0" and S[i]=="1":
        a = i
        cur = "1"
    if cur=="1" and S[i]=="0":
        b = i
        cur = "0"
        chgpos.append((a,b))
if S[-1] == "1":
    chgpos.append((a,N))
if S[-1] == "0":
    chgpos.append((N,N))
    
l = len(chgpos)
if K>l-1:
    print(N)
else:
    ans = 0
    for i in range(l-K):
        if chgpos[i+K][1] - chgpos[i][0] > ans:
            ans = chgpos[i+K][1] - chgpos[i][0]
    print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = str(input())
Sb = []
zero = 0
for i in range(n):
  if int(s[i]):
    if len(Sb) == 0 or Sb[-1][0] == 0:
      Sb.append([1, 1])
    else:
      Sb[-1][1] += 1
  else:
    if len(Sb) == 0 or Sb[-1][0]:
      Sb.append([0, 1])
      zero += 1
    else:
      Sb[-1][1] += 1
if zero <= k:
  print(n)
else:
  if Sb[0][0] != 1:
    Sb.insert(0, [1, 0])
  if Sb[-1][0] != 1:
    Sb.append([1, 0])
  ans = sum([Sb[i][1] for i in range(2 * k + 1)])
  tmp = ans
  for i in range(zero - k):
    tmp += Sb[2 * k + 2 * (i+1)][1] + Sb[2 * k + 2 * (i+1) - 1][1] - Sb[2 * i][1] - Sb[2 * i + 1][1]
    ans = max(ans, tmp)
  print(ans)

Submission status: Accepted

Solution code:
#abc124d

n,k=map(int,raw_input().split())
s=raw_input()
l=[0]
for i in xrange(n-1):
 if s[i+1]!=s[i]:
  l.append(i+1)
l.append(n)
res=0
for i in xrange(len(l)-1):
 idx=min(i+k*2+int(s[l[i]]=='1'),len(l)-1)
 res=max(res,l[idx]-l[i])
print res

Submission status: Accepted

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

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

count = []
for i in range(len(cand_index)-1):
    index = min(i+2*k+int(s[cand_index[i]]=="1"), len(cand_index)-1)
    count.append(cand_index[index]-cand_index[i])
        
print(max(count))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
a = []
if s[0] == '0':
    a.append(0)
l = r = 0
while l < n:
    while r < n and s[l] == s[r]:
        r += 1
    a.append(r-l)
    l = r
if s[-1] == '0':
    a.append(0)
m = len(a)
if m // 2 <= k:
    print(n)
else:
    ans = 0
    asum = [0 for _ in range(m+1)]
    for i in range(m):
        asum[i+1] = asum[i] + a[i]
    for i in range(m+1-2*k):
        if i % 2:
            continue
        ans = max(ans, asum[i+2*k+1] - asum[i])
    print(ans)

Submission status: Accepted

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

a = []

before = s[0]
first = int(s[0])
count = 1
for x in s[1:]:
    if x != before:
        a.append(count)
        count = 1
    else:
        count += 1
    before = x
a.append(count)

L = 0
R = k * 2
if first == 1:
    R += 1

if R >= len(a):
    print(n)
    exit()

ans = sum(a[:R])
temp = ans

if first == 0:
    temp -= a[0]
    L += 1
    if R < len(a):
        temp += a[R]
    if R + 1 < len(a):
        temp += a[R + 1]
    R += 2
else:
    temp -= a[0] + a[1]
    L += 2
    if R < len(a):
        temp += a[R]
    if R + 1 < len(a):
        temp += a[R + 1]
    R += 2

if R >= len(a):
    ans = max(ans, temp)
    print(ans)
    exit()

ans = max(ans, temp)

while R <= len(a):
    temp -= a[L] + a[L+1]
    if R + 1 < len(a):
        temp += a[R] + a[R + 1]
    elif R < len(a):
        temp += a[R]
    ans = max(ans, temp)
    L += 2
    R += 2

print(ans)

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]

s = input()

il = []

qt = 1
ilz = 0
for i in range(1,len(s)):
    if(s[i-1] == s[i]):
        qt+=1
    else:
        if(s[i-1] == '0'):
            ilz+=1
        il.append([s[i-1],qt])
        qt = 1
        
if(qt>0):
    if(s[len(s)-1] == '0'):
        ilz+=1
    il.append([s[len(s)-1],qt])

if(s.count('1') == n):
    print(n)
elif(k>=ilz):
    print(n)
else:

    l = r = 0
    so = 0
    mso = 0
    for i in range(len(il)):

        if(il[r][0] == '1'):
            so+=il[r][1]
        elif(k>0):
            so+=il[r][1]
            k-=1
        else:
            mso = max(mso,so)
            
            while l<len(il) and il[l][0]!='0':
                so -= il[l][1]
                l+=1
            if(l<len(il)):
                so -= il[l][1]
                l+=1
            
            so+=il[r][1]
            
        r+=1
    mso = max(mso,so)
    print(mso)

Submission status: Accepted

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

groups = list()
now = 1
cnt = 0

for s in S:
    if s == now:
        cnt += 1
    else:
        groups.append(cnt)
        now ^= 1
        cnt = 1

groups.append(cnt)

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

cumsum = [0] + list(accumulate(groups))

Add = 2 * K + 1

ans = 0

for i in range(0,len(groups), 2):
    left = i
    right = min(i + Add, len(groups))
    tmp = cumsum[right] - cumsum[left]

    ans = max(tmp,ans)

print(ans)

Submission status: Accepted

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

l = [0]

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

l.append(n)

ans = 0
for i in range(len(l)-1):
  index = min(i+2*k + int(s[l[i]]=="1"), len(l)-1)
  ans = max(ans, l[index] - l[i])

print(ans)

Submission status: Accepted

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

#s = "0001111011110"
#n, k = len(s), 1

s="1"+s

k_pt = 0
cur_tail = 0
for cur in range(1, len(s)):

  if  s[cur-1] == '1' and s[cur] == '0':
    k_pt+=1

  if k_pt > k:
    cur_tail+=1
    if s[cur_tail] == '0' and s[cur_tail+1] == '1':
      k_pt-=1

  #print((cur_tail, cur,k_pt))

print(cur-cur_tail)

Submission status: Accepted

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

#s = "0001111011110"
#n, k = len(s), 1

s="1"+s

k_pt = 0
cur_tail = 0
for cur in range(1, len(s)):
  cur_tail+=1

  if  s[cur-1] == '1' and s[cur] == '0':
    k_pt+=1

  if k_pt <= k:
      cur_tail-=1
  elif  s[cur_tail] == '0' and s[cur_tail+1] == '1':
    k_pt-=1

print(cur-cur_tail)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate


def main(N, K, S):
    cnts = []
    now = '1'
    cnt = 0
    for n in S:
        if now == n:
            cnt += 1
        else:
            cnts.append(cnt)
            cnt = 1
            now = n
    cnts.append(cnt)

    if now == '0': cnts.append(0)
    
    ans = 0
    Add = 2 * K + 1

    sums = [0] + list(accumulate(cnts))

    for i in range(0,len(cnts),2):
        left = i
        right = min(i + Add, len(cnts))
        tmp = sums[right] - sums[left]

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

if __name__ == "__main__":
    n, k = list(map(int, input().split()))
    s = input()
    main(n, k, s)

Submission status: Accepted

Solution code:
_, k = (map(int, input().split()))
n = [int(i) for i in list(input())]
rem = n[0]
s = [1]
for i in range(1, len(n)):
    if n[i] == rem:
        s[-1] += 1
    else:
        s.append(1)
        rem = n[i]

imax = 0
sum_ = 0
r = 0
if n[0] == 0:
    s.insert(0, 0)

for l in range(len(s)):
    sum_ += s[l]
    if l % 2 == 1 and l - r > k * 2:
        r += 2
        sum_ -= s[r-2] + s[r-1]
    if sum_ > imax:
        imax = sum_

print(imax)

Submission status: Accepted

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


def main(N, K, S):
    cnts = []
    now = 1
    cnt = 0
    for n in S:
        if now == int(n): 
            cnt += 1
        else:
            cnts.append(cnt)
            cnt = 1
            now = 1 - now
    if cnt != 0: cnts.append(cnt)

    if len(cnts) % 2 == 0: cnts.append(0)
    
    ans = 0
    Add = 2 * K + 1

    sums = [0]
    for c in cnts:
        sums.append(sums[-1] + c)

    for i in range(0,len(cnts),2):
        left = i
        right = min(i + Add, len(cnts))
        tmp = sums[right] - sums[left]

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

if __name__ == "__main__":
    n, k = list(map(int, input().split()))
    s = input()
    main(n, k, s)

Submission status: Accepted

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

ans = 0
for i in range(len(l)-1):
    ind = min(i+2*k + int(s[l[i]]=="1"), len(l) - 1)
    ans = max(ans, l[ind] - l[i])

print(ans)

Submission status: Accepted

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

prev = s[0]
cnt = 0
l = []
for c in s:
    if c == prev:
        cnt += 1
    else:
        l.append(cnt)
        prev = c
        cnt = 1
l.append(cnt)

if s[0] == "0":
    l = [0] + l
if s[-1] == "0":
    l.append(0)

cumsum = [0]
for i in l:
    cumsum.append(cumsum[-1]+i)


k = min(len(l), 2*k+1)
ans = max(l[::2])
for i in range(len(l) - k + 1):
    if i % 2 == 1:
        continue
    ans = max(ans, cumsum[i+k]- cumsum[i])
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
s=input()
l=[]
index=0
pre='1'
for i in range(len(s)):
    if s[i]!=pre:
        l.append(i-index)
        pre=s[i]
        index=i
else:
    l.append(i-index+1 if i!=index else 1)
    if s[-1]=='0':
        l.append(0)
Max=sum(l[:min(2*K+1,len(l))])
cur=Max
for i in range(2*K+1,len(l)):
    cur=cur+l[i]-l[i-2*K-1]-l[i-2*K] if i%2 else cur+l[i]
    if cur > Max:
        Max=cur
print(Max)

Submission status: Accepted

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

x=[]
tmp=0
for i in range(N):
    if s[i]=="1":
        if tmp!=0: x.append([tmp,i-1]) 
        tmp=0
    
    else: tmp+=1
if tmp!=0: x.append([tmp,i]) 

l=len(x)
if l<=K: print(N),sys.exit()

y=[ [0, x[1][1]-x[1][0] ] ]
for i in range(1,l-1):
    y.append([x[i-1][1]+1, x[i+1][1]-x[i+1][0] ])

y.append([x[l-2][1]+1 ,N-1])
ans=0
for i in range(l-K+1):
    ans=max(ans,y[i+K-1][1]-y[i][0]+1 )
print(ans)