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:
def shaktori(n, tmp=0, l_s=0, r_s=0, l=0, r=0):
    while l_s > l:
        tmp -= n[l]
        l += 1
    while r_s > r:
        tmp += n[r] 
        r += 1 
    return (tmp, l, r)

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

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

# 1で始まって1で終わるように調節
if len(n) % 2 == 0:
    n.append(0)   

s = 2 * K + 1
a = 0
tmp = 0
l, r = 0, 0
for i in range(0, len(n), 2):
    l_s = i 
    r_s = min(i + s, len(n))
    tmp, l, r = shaktori(n, tmp, l_s, r_s, l, r)

    a = max(a, tmp)

print(a)

Submission status: Accepted

Solution code:
n, k = map(int, input().split(' '))
s = input()
if k >= n:
  print(n)
  exit()
  
s10 = []
cnt = 0
s_prev = '1'
for si in s+'x':
  if si == s_prev:
    cnt += 1
  else:
    s10.append(cnt)
    cnt = 1
  s_prev = si
if s[-1] == '0':
  s10.append(0)
if len(s10) < 2*k + 1:
  print(n)
  exit()

sum_i = sum(s10[:2*k+1])
sum_max= sum_i

for i in range(len(s10)//2-k):
  sum_i += (s10[2*i + 2*k + 1] + s10[2*i + 2*k + 2] - s10[2*i] - s10[2*i+1])
  sum_max = max(sum_i, sum_max)
  
print(sum_max)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

serial = []
if S[0] == '0':
    serial.append(0)
i = 0
while i < N:
    j = i
    while j < N and S[j] == S[i]:
        j += 1
    serial.append(j - i)
    i = j
if S[-1] == '0':
    serial.append(0)

serial_cumsum = [0]+list(accumulate(serial))
ans = 0
for l in range(0, len(serial_cumsum), 2):
    r = min(len(serial_cumsum) - 1, l + 2*K + 1)
    temp = serial_cumsum[r] - serial_cumsum[l]
    if ans < temp:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
if s[0] == "1":
    cnt_list = []
else:
    cnt_list = [0]
cnt = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        cnt_list.append(cnt)
        cnt = 1
cnt_list.append(cnt)
if s[-1] == '0':
    cnt_list.append(0)
#print(cnt_list)
sum_list = [0]
for i in range(len(cnt_list)):
    sum_list.append(sum_list[i] + cnt_list[i])
ans = 0
for i in range(0,len(sum_list),2):
    right = min(i+2*k+1,len(sum_list)-1)
    ans = max(ans,sum_list[right]-sum_list[i])
print(ans)

Submission status: Accepted

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

from itertools import accumulate


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

    # 配列を下記で変換
    # '11000' = [2, 3, 0]
    # '1'の長さで始まり、'1'の長さで終わるようにする
    s = s.replace('01', '0,1').replace('10', '1,0')
    len_list = [len(string) for string in s.split(',')]
    if s[0] == '0':
        len_list = [0] + len_list
    if s[-1] == '0':
        len_list = len_list + [0]

    if 2 * k + 1 >= len(len_list):
        print(n)
        return

    sum_list = [0] + list(accumulate(len_list))
    max_len = 0
    for i in range(0, len(len_list) - (2 * k + 1) + 1, 2):
        handstand_len = sum_list[i + (2 * k + 1)] - sum_list[i]
        if max_len < handstand_len:
            max_len = handstand_len
    print(max_len)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	N,K = map(int, input().split())
	S = input()
	nums = []
	if(S[0]=='0') : 
		nums.append(0)
	i=0
	while i < N:
		j = i
		while j<N and S[j]==S[i] :
			j+=1
		nums.append(j-i)
		i=j


	if(S[N-1]=='0') :
		nums.append(0)
	
	sums=[0] * (len(nums)+1)
	for i in range(len(nums)):
		sums[i+1] = sums[i] + nums[i]

	window_size = 2*K + 1
	ans=0
	l = 0
	while l < len(sums):
		r = l + window_size
		if(r>=len(sums)):
			r = len(sums)-1
		ans = max(ans,sums[r] - sums[l])
		l+=2

	print(ans)

Submission status: Accepted

Solution code:
import sys

N, K = map(int, input().split())
s = input() + "#"

pre, cons, comp = '#', 0, [(0, -1)]
for i in range(len(s)):
    if pre != '#' and pre != s[i]:
        if cons > 0:
            print(cons, s[i-1], file=sys.stderr)
            comp.append((cons, s[i-1]))
            cons = 1
    else:
        cons += 1

    pre = s[i]

acc = [0 for _ in range(len(comp))]
for i in range(1, len(comp)):
    acc[i] = acc[i-1] + comp[i][0]

ans = 0
for i in range(len(comp) - 1):
    lim = len(comp) - 1
    if comp[i+1][1] == '1':
        lim = min(lim, i + 2*K + 1)
    else:
        lim = min(lim, i + 2*K)
    print("i = {}, lim = {}".format(i, lim), file=sys.stderr)
    ans = max(ans, acc[lim] - acc[i])

print(ans)

Submission status: Accepted

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

pre, cons, comp = '#', 0, [(0, -1)]
for i in range(len(s)):
    if pre != '#' and pre != s[i]:
        if cons > 0:
            # print(cons, s[i-1])
            comp.append((cons, s[i-1]))
            cons = 1
    else:
        cons += 1

    pre = s[i]

acc = [0 for _ in range(len(comp))]
for i in range(1, len(comp)):
    acc[i] = acc[i-1] + comp[i][0]

ans = 0
for i in range(len(comp) - 1):
    lim = len(comp) - 1
    if comp[i+1][1] == '1':
        lim = min(lim, i + 2*K + 1)
    else:
        lim = min(lim, i + 2*K)
    # print("i = {}, lim = {}".format(i, lim))
    ans = max(ans, acc[lim] - acc[i])

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
nums=[]
if S[0]=="0":
    nums.append(0)
i=0
while(i<len(S)):
    j=i
    while(j<len(S) and S[j]==S[i]):
        j+=1
    nums.append(j-i)
    i=j
if S[-1]=="0":
    nums.append(0)
sums=[0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1]=sums[i]+nums[i]
res=0
for left in range(0,len(sums),2):
    right=left+K*2+1
    if right>=len(sums):
        right=len(sums)-1
    res=max(res,sums[right]-sums[left])
print(res)

Submission status: Accepted

Solution code:

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

#s[j-1]=0,s[j]=1もしくはs[j-1]=1,s[j]=0になっているjをリストにしたものをiとする（スタート地点かつエンド地点候補）
i=[0]
for j in range(1,len(S)):
    if S[j]!=S[j-1]:
        i.append(j)

#スタート地点候補iに対して、
#s[i[m]]==1の場合、変更可能な変化点は2K個なので,その次の変化点までが求める文字数となり,X=i[2K+1+m]-i[m]
#s[i[m]]==0の場合、変更可能な変化点は2K-1個なので,その次の変化点までが求める文字数となり,X=i[2K+m]-i[m]

X=[]
for m in range(len(i)):
    if S[i[m]]=='1':
        #はみ出している->右方向は全て置換可能
        if 2*K+1+m >= len(i):
            X.append(N-i[m])
        else:
            X.append(i[2*K+1+m]-i[m])

    elif S[i[m]]=='0':
        #はみ出している->右方向は全て置換可能
        if 2*K+m >= len(i):
            X.append(N-i[m])
        else:
            X.append(i[2*K+m]-i[m])

print(max(X))

Submission status: Accepted

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

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

Sl = [0] + [i for i in range(N + 1) if S[i:(i + 2)] == "01"] + [N]
Sr = [0] + [i for i in range(N + 1) if S[i:(i + 2)] == "10"] + [N]

if len(Sl) - K >= 1:
    print(max([Sr[i + K] - Sl[i] for i in range(len(Sl) - K)]))
else:
    print(N)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
befores = '1'
cnt = 0
snum = []
for S in s:
	if S == befores:
		cnt += 1
	else:
		snum.append(cnt)
		cnt = 1
		befores = S
snum.append(cnt)
if s[-1] == '0':
    snum.append(0)
kazu = sum(snum[0:k * 2  + 1])
kaisuu = sum(snum[0:k * 2  + 1])
time = int((len(snum) - k * 2 - 1) / 2 )
one = 0
zero = 1
k = k * 2
for i in range(time):
	kazu = kazu - snum[one] - snum[zero] + snum[one + k + 2] + snum[zero + k]
	kaisuu = max(kaisuu,kazu)
	one += 2
	zero += 2
print(kaisuu)

Submission status: Accepted

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

now = 1
cnt = 0
x = []

for i in range(n):
    if sss[i] == str(now):
        cnt += 1
    else:
        x.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    x.append(cnt)
if sss[-1] == 0:
    x.append(0)

Add = 2 * k + 1
ans = 0

y = [0]
for i in range(len(x)):
    y.append(y[i] + x[i])

for i in range(len(x))[::2]:
    left = i
    right = min(i + Add, len(x))
    tmp = y[right] - y[left]
    
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
S = input()
memo =[]
now = '1'
cnt = 0
for s in S:
    if s==now:
        cnt+=1
    else:
        memo.append(cnt)
        cnt=1
        now = '1' if now=='0' else '0'
else:
    memo.append(cnt)
if S[-1] == '0':
    memo.append(0)
ans = 0
add = K*2+1

ruiwa = [0]*(len(memo)+1)
for i in range(len(memo)):
    ruiwa[i+1]=ruiwa[i]+memo[i]

for i in range(N)[::2]:
    if i < N:
        tmp = ruiwa[min(i+add, len(ruiwa)-1)] - ruiwa[min(i, len(ruiwa)-1)]
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
inp=[i.strip() for i in sys.stdin.readlines()]
if len(inp)==1:
    if len(inp[0].split())==2:
        A,B=map(int,inp[0].split())
        print(max(2*A-1,2*B-1,A+B))
    else:
        S=inp[0]
        N=len(S)
        X=""
        Y=""
        for i in range(N):
            if i%2==0:
                X=X+"0"
                Y=Y+"1"
            else:
                X=X+"1"
                Y=Y+"0"
        A=0
        B=0
        for i in range(N):
            if X[i]!=S[i]:
                A+=1
            if Y[i]!=S[i]:
                B+=1
        print(min(A,B))
else:
    if len(inp[0].split())==1:
        N=int(inp[0])
        H=[int(i) for i in inp[1].split()]
        ans=1
        for i in range(1,N):
            flag=1
            for j in range(i):
                if H[j]>H[i]:
                    flag=0
                    break
            if flag==1:
                ans+=1
        print(ans)
    else:
        N,K=map(int,inp[0].split())
        S=inp[1]
        L=[0]
        tmp="1"
        for i in range(N):
            if tmp!=S[i]:
                L.append(1)
            else:
                L[-1]+=1
            tmp=S[i]
        if tmp=="0":
            L.append(0)
        M=len(L)
        if M<=2*K+1:
            print(N)
            exit()
        X=[0 for i in range(M+1)]
        for i in range(M):
            X[i+1]=L[i]+X[i]
        ans=0
        for i in range(0,M-2*K,2):
            ans=max(ans,X[i+2*K+1]-X[i])
        print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return POW(x, y // 2) ** 2 % MOD
    else:
        return POW(x, y // 2) ** 2 * x % MOD
def mod_factorial(x, y): return x * POW(y, MOD - 2) % MOD
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter
from itertools import accumulate

def main():
    N, K = LI()
    S = SI()
    cnts = []
    pre = '1'
    cnt = 0
    # 0 start bin
    for s in S:
        if s != pre:
            cnts.append(cnt)
            cnt = 0
            pre = s
        cnt += 1
    cnts.append(cnt)
    acc = [0] + list(accumulate(cnts))
    ans = 0
    for i in range(0, len(acc) - 1, 2):
        tmp = acc[min(len(acc) - 1, i + 2 * K + 1)] - acc[i]
        ans = max(tmp, ans)
        if len(acc) < i + 2 * K + 1:
            break

    return ans

print(main())

Submission status: Accepted

Solution code:
import sys

n, k = [int(x) for x in input().split()]
s = input()
l = [0]
a = '1'
for i in range(n):
  if s[i] != a:
    l.append(i)
    a = s[i]
l.append(n)
if s[-1] == '0':
  l.append(n)
if len(l) < 2 * k + 2:
  print(n)
  sys.exit()
a, ans = 0, 0
while a + 2 * k + 1 < len(l):
  b = l[a+2*k+1] - l[a]
  if ans < b:
    ans = b
  a += 2
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(map(int, list(input())))
now = 1
cnt = 0
Nums = []
for i in range(N):
    if S[i] == 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
ans = 0
left, right = 0, 0
tmp = 0  # sum of [left, right)
for i in range(len(Nums))[::2]:
    next_left = i
    next_right = min(i + add, len(Nums))
    while next_left > left:
        tmp -= Nums[left]
        left += 1
    while next_right > right:
        tmp += Nums[right]
        right += 1

    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
S = input()
tmp = S[0]
count = 0
num_count = []
f = int(S[0])
for s in S:
    if tmp == s:
        count += 1
    else:
        num_count.append(count)
        count = 1
    tmp = s
num_count.append(count)
if S[0] == '0':
    num_count.insert(0, 0)
if S[-1] == '0':
    num_count.insert(-1, 0)
sum = [0]
for i in num_count:
    sum.append(sum[-1] + i)
a = 0
for i, num in enumerate(sum[::2]):
    left = i * 2
    right = min(i * 2 + 2 * k + 1, len(num_count))
    t = sum[right] - sum[left]
    a = max(a, t)
print(a)

Submission status: Accepted

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

now = 1
cnt = 0
x = []

for i in range(n):
    if sss[i] == str(now):
        cnt += 1
    else:
        x.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    x.append(cnt)
if sss[-1] == 0:
    x.append(0)

Add = 2 * k + 1
ans = 0

y = [0]
for i in range(len(x)):
    y.append(y[i] + x[i])

for i in range(len(x))[::2]:
    left = i
    right = min(i + Add, len(x))
    tmp = y[right] - y[left]    
    
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

now = 1
cnt = 0
x = []

for i in range(n):
    if sss[i] == str(now):
        cnt += 1
    else:
        x.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    x.append(cnt)
if len(x) % 2 == 0:
    x.append(0)

Add = 2 * k + 1
ans = 0

y = [0]
for i in range(len(x)):
    y.append(y[i] + x[i])

for i in range(len(x))[::2]:
    left = i
    right = min(i + Add, len(x))
    tmp = y[right] - y[left]    
    
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

now = 1
cnt = 0
x = []

for i in range(n):
    if sss[i] == str(now):
        cnt += 1
    else:
        x.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    x.append(cnt)
if len(x) % 2 == 0:
    x.append(0)

Add = 2 * k + 1
ans = 0

left = 0
right = 0
tmp = 0

for i in range(len(x))[::2]:
    nextleft = i
    nextright = min(i + Add, len(x))
    while nextleft > left:
        tmp -= x[left]
        left += 1
    while nextright > right:
        tmp += x[right]
        right += 1
    
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

count = 0
flag = True

la = deque([])
for c in S:
    if int(flag) == c:
        count += 1
    else:
        la.append(count)
        count = 1
        flag = not flag

la.append(count)

if K >= (len(la) / 2):
    print(N)
    exit()

ltmp = deque([])
sum_la = 0
for _ in range((K-1)*2 + 1):
    tmp = la.popleft()
    sum_la += tmp
    ltmp.append(tmp)

last_a = [sum_la]
while len(la) > 0 :
    tmp = la.popleft()
    sum_la += tmp
    ltmp.append(tmp)
    if len(la) > 0:
        tmp = la.popleft()
        sum_la += tmp
        ltmp.append(tmp)

    last_a.append(sum_la)

    if len(ltmp) > 0:
        tmp = ltmp.popleft()
        sum_la -= tmp
    if len(ltmp) > 0:
        tmp = ltmp.popleft()
        sum_la -= tmp
    last_a.append(sum_la)

print(max(last_a))

Submission status: Accepted

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

cnt = 0
state = sss[0]
x = []
if sss[0] == "0":
    x.append(0)
for s in sss:
    if s == state:
        cnt += 1
    else:
        state = s
        x.append(cnt)
        cnt = 1
x.append(cnt)
if sss[-1] == "0":
    x.append(0)
#11101010110011
#1:3 1 1 2 2
#0: 1 1 1 2

#1
#1

y = [0]
for i in range(len(x)):
    y.append(y[i] + x[i])
#:0,1,2,3,4,5,6 7, 8 ,9
#:0,3,4,5,6,7,8,10,12,14

#0,1

z = []
for i in range(k*2+1,len(y))[::2]:
    z.append(y[i] - y[i - (k*2+1)])
#print(x)
#print(y)
#print(z)
if len(x) <= k*2-1:
    print(sum(x))
else:
    print(max(z))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

nums = []
now, cnt = 1, 0
for s in S:
    if s == now:
        cnt += 1
    else:
        nums.append(cnt)
        now, cnt = 1 - now, 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

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

ans = 0
add = 2 * K + 1
for i in range(0, len(nums), 2):
    left = i
    right = min(i + add, len(nums))
    ans = max(ans, sums[right] - sums[left])
print(ans)

Submission status: Accepted

Solution code:

#input
#N = list(map(int,input().split()))
#H = list(map(int,input().split()))
[N, K] = list(map(int,input().split()))
S = str(input())
tmp = 1
list_S = []
for i in range(N):
    if i == N-1:
        list_S.append(tmp)
        break
    if S[i] != S[i+1]:
        list_S.append(tmp)
        tmp = 1
    else:
        tmp += 1
M = len(list_S)+1
list_S = list_S + [0]*(2*K+5)
if S[0] == "0":
    list_S = [0] + list_S
    
tmp = sum(list_S[0:2*K + 1])
ans = sum(list_S[0:2*K + 1])
for i in range(0,M+2,2):
    tmp = tmp - list_S[i] -list_S[i+1]
    tmp = tmp + list_S[i+2*K+1] + list_S[i+2*K+2]
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
def solve(n, k, s):
    v = []
    if s[0] == "0":
        v.append(0)
    i = 0
    while i < n:
        num = 1
        while (i+1 < n) and (s[i+1] == s[i]):
            num += 1
            i += 1
        v.append(num)
        i += 1
    if s[n-1] == "0":
        v.append(0)
    m = len(v)
    w = [0] * m
    w[0] = v[0]
    for i in range(m-1):
        w[i+1] = w[i] + v[i+1]
    best = w[0]
    for left in range(0, m, 2):
        right = min(left + 2*k + 1, m)
        if left == 0:
            cur = w[right-1]
        else:
            cur = w[right-1] - w[left-1]
        best = max(best, cur)
    return best

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

Submission status: Accepted

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

Submission status: Accepted

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

cnts = []
# denote whether the first block is 0 or 1
tmp, cnt = s[0], 0
flag = int(s[0])

for i in range(n):
    if s[i] == tmp:
        cnt += 1
    else: # here tmp should be cleared
        cnts.append(cnt)
        cnt = 1
    tmp = s[i]
cnts.append(cnt)
# print(cnts)

n_zero = (len(cnts) + 1) // 2 if flag == 0 else len(cnts) // 2
if n_zero <= k:
     ans = sum(cnts)

else:
    ans = 0
    cumsum = [0]
    for i in range(len(cnts)):
        cumsum.append(cumsum[-1] + cnts[i])

    for inx in range(flag, len(cnts), 2):
        start = max(0, inx - 1)
        end = min(inx + 2 * k , len(cnts))
        tmp = cumsum[end] - cumsum[start]
        ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = [int(x) for x in list(input())]

state = 1
cnt = 0
l = []
for e in s:
    if e != state:
        l.append(cnt)
        cnt = 1
        state = e
    else:
        cnt += 1

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


if len(l) % 2 == 1:
    l.append(0)

Add = 2 * k + 1
ruiseki = [0]

for i, e in enumerate(l):
    ruiseki.append(ruiseki[i] + l[i])

answer = 0
for i in range(0, len(l), 2):
    left = i
    right = min(i + Add, len(l))
    tmp = ruiseki[right] - ruiseki[left]
    answer = max(tmp, answer)

print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = [int(x) for x in list(input())]

state = 1
cnt = 0
l = []
for e in s:
    if e != state:
        l.append(cnt)
        cnt = 1
        state = e
    else:
        cnt += 1

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

if len(l) % 2 == 1:
    l.append(0)

Add = 2 * k + 1
ruiseki = [0]

for i, e in enumerate(l):
    ruiseki.append(ruiseki[i] + l[i])

answer = 0
for i in range(0, len(l), 2):
    left = i
    right = min(i + Add, len(l))
    tmp = ruiseki[right] - ruiseki[left]
    answer = max(tmp, answer)
 
print(answer)

Submission status: Accepted

Solution code:
import copy
def main():
    n, k = map(int, input().rstrip().split(' '))
    s = [c == '1' for c in input().rstrip()]

    windows = []
    current_window = None
    for i, c in enumerate(s):
        if not c:
            if current_window  == None:
                current_window = Window(False)
            elif current_window.one:
                windows.append(current_window)
                current_window = Window(False)
            current_window.count += 1
        else:
            if current_window  == None:
                current_window = Window(True)
            elif not current_window.one:
                windows.append(current_window)
                current_window = Window(True)
            current_window.count += 1
    windows.append(current_window)
    
    counts = []
    count = 0
    zero_window_count = 0
    for i, w in enumerate(windows):
        if not w.one:
            zero_window_count += 1
            if zero_window_count > k:
                counts.append(count)
                leftmost = i - (2 * k) - 1
                if leftmost >= 0:
                    count -= windows[leftmost].count #1s, if exist
                count -= windows[leftmost + 1].count #0s

        count += w.count
    counts.append(count)
    print(max(counts))

class Window:
    def __init__(self, one_or_zero):
        self.one = one_or_zero
        self.count = 0
    
    def __repr__(self):
        return ("1" if self.one else "0") + " " + str(self.count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
s = input()
data = [int(a) for a in s]

#numsの偶数番目の要素が連続した1の個数,奇数番目の要素が連続した0の個数
#	data[1001110001] -> nums[1,2,3,3,1]
nums = []
if data[0]==0:
	nums.append(0)
i,j = 0,0
for i in range(len(data)):
	i,count = j,1
	for j in range(i+1,len(data)):
		if data[i]==data[j]:
			count+=1
		if data[i]!=data[j] or j==len(data)-1:
			nums.append(count)
			break

#累積和 nums[1,2,3,3,1] -> sums[0,1,3,6,9,10]
sums = [0]
for i in range(len(nums)):
	sums.append(sums[i] + nums[i])

#連続した0を1にする操作をK回行うと、2K+1個連続した1の要素が並ぶ 
ans = 1
for i in  range(0,len(sums),2):
	j = i + K*2+1
	if j>=len(sums):
		j = len(sums)-1
	ans = max(ans, sums[j]-sums[i])

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
if S[0] == '0':
  divide = []
else:
  divide = [0]
tmp = 1
for i in range(1,N):
  if S[i] == S[i-1]:
    tmp += 1
  else:
    divide += [tmp]
    tmp = 1
divide += [tmp]
le = len(divide)
zero = [0]*2*le + divide + [0]*2*le
su = [0]
for i in range(0,5*le):
  su += [su[-1]+zero[i]]
del su[0]
lle = len(su)
mxm = 0
for k in range(K,lle):
  if 2*k+1 >= lle:
    break
  cd = su[2*k+1] - su[2*k-2*K]
  if cd > mxm:
    mxm = cd
xmx = max(divide)
print(max(mxm,xmx))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

s_num = []

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

if prev == '0':
    s_num.append(0)

if s[0] == '0':
    s_num = [0] + s_num
if s[-1] == '0':
    s_num = s_num + [0]

w = 2 * k + 1

if len(s_num) <= w:
    print(n)
else:

    acc = [0] + list(accumulate(s_num))
    res = [acc[i+w] - acc[i] for i in range(0, len(acc) - w, 2)]

    # print(s)
    # print(s_num)
    # print(acc)
    print(max(res))

Submission status: Accepted

Solution code:
from itertools import accumulate
 
n, k = list(map(int, input().split()))
s = input()
 
l = []

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

if prev == '0':
  l.append(0)

w = 2 * k + 1

if len(l)<= w :
  print(n)
else :
  acc = [0] + list(accumulate(l))
  ans = 0
  for i in range(0, len(l) - w + 1, 2):
    #print(i+w, i)
    #print(ans, acc[i+w]-  acc[i])
    ans = max(ans, acc[i + w] - acc[i])
  print(ans)

Submission status: Accepted

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

# 0 ,1 のまとまりを作る
sum01 = []
pre = 1
cnt = 0
# 111010
# 001010
for i, e in enumerate(list):
    if e != pre:
        sum01.append(cnt)
        cnt = 1
        pre = e
    else:
        cnt += 1
if cnt != 0:
    sum01.append(cnt)

if len(sum01) % 2 == 1:
    sum01.append(0)

# print(sum01)
Add = 2 * k + 1
ruiseki = [0]
for i, e in enumerate(sum01):
    ruiseki.append(ruiseki[i] + sum01[i])

# print(ruiseki)
answer = 0
for i in range(0, len(sum01), 2):
    left = i
    right = min(i + Add, len(sum01))
    temp = ruiseki[right] - ruiseki[left]
    answer = max(temp, answer)

print(answer)

Submission status: Accepted

Solution code:
def Main():
    N, K = map(int, input().split())
    S = input()
    arr = []
    arr.append(0)
    if S[0] == '0':
        arr.append(0)
    cnt = 1
    for i in range(1, N):
        if S[i-1] == S[i]:
            cnt += 1
        else:
            arr.append(cnt)
            cnt = 1
    arr.append(cnt)
    n = len(arr)
    for i in range(1, n):
        arr[i] += arr[i-1]
    #print(arr)
    ans = 0
    sum = 0
    l = 0
    for r in range(1, n):
        while((r-l)//2 > K):
            l += 2
        #print(l, r)
        ans = max(ans, arr[r]-arr[l]) 
       
    print(ans)

if __name__ == "__main__":
    Main()

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
S = input()
 
S += "X"
i = 0
j = 0
max_len = 0
change = 0 if S[0] != "0" else 1
while j < len(S)-1:
  if change <= K:
    #print(i, j)
    max_len = max([j-i+1, max_len])
    if S[j:j+2] == "10":
      change += 1
    j += 1
  else:
    if S[i:i+2] == "01":
      change -= 1
    i += 1

print(max_len)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
po=[0]
X=[]
i=0
for i in range(N-1):
	if not S[i] == S[i+1]:
		po.append(i+1)
po.append(len(S))
for i in range(len(po)):
	if 2*K+1>=len(po):
		X.append(po[-1])
		break
	elif 2*K+i+1>=len(po):
		X.append(po[2*K+i]-po[i])
		break
	elif S[po[i]]=='0':
		X.append(po[2*K+i]-po[i])
	else:
		X.append(po[2*K+1+i]-po[i])
print(max(X))

Submission status: Accepted

Solution code:
def calc_seq(xs):
    seq = []
    count = 1
    for i in range(0, len(xs)-1):
        if xs[i] == xs[i+1]:
            count += 1
        else:
            seq.append(count)
            count = 1
    seq.append(count)
    return seq

def form_seq(xs):
    seq = calc_seq(xs)
    if xs[0] == 0:
        seq.insert(0, 0)
    if len(seq) % 2 == 0:
        seq.append(0)
    return seq

def main(n, k, xs):
    seq = form_seq(xs)
    m = len(seq)
    i = 1
    if i + 2*k > m:
        print(n)
        return
    j = i - 1
    val = sum(seq[j:j+2*k+1])
    biggest = val
    i += 2
    while i + 2*k <= m:
        j = i - 1
        val += seq[j+2*k-1] + seq[j+2*k] - seq[j-2] - seq[j-1]
        if biggest < val:
            biggest = val
        i += 2
    print(biggest)

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

main(n, k, xs)

Submission status: Accepted

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

si = [1]
si.extend(2+i for i, (s1, s2) in enumerate(zip(S, S[1:])) if s1 != s2)
si.append(N + 1)


def f(i, si):
    return si[min(i + 2*K + 1, len(si)) - 1] - si[i-1]

j0 = min(1 + 2*K + (1 if S[0] == "1" else 0), len(si)) - 1
x0 = si[j0] - 1

x = [x0]
x.extend(f(i+1, si) for i in range(2 if S[0] == "1" else 1, len(si), 2))
print(max(x))

Submission status: Accepted

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

now_char = '1'
cnt = 0
cnt_list = []

# cnt_listを[1が何連続したか、0が何連続したか、1が何連続したか...]にする
# cnt_listは1に始まり1で終えたいので、例えば0100なら
# [1が0回、0が1回、1が1回、0が2回、1が0回]とカウントしたい
for i, s in enumerate(S):
    # これまで連続していた文字とs[i]が異なるとき
    # 結果をリストに加えてリセット
    if s != now_char:
        cnt_list.append(cnt)
        cnt = 1
        now_char = s
    # 同じ文字ならカウントアップ
    else:
        cnt += 1
else:
    # 最後の文字についてのカウントを追加
    cnt_list.append(cnt)
    # 最後が1なら補正する
    if S[-1] == '0':
        cnt_list.append(0)

# cnt_list = [1, 1, 2, 3, 5](つまりS = 101100011111), K = 1なら
# 最初の0を反転させたときの(左側の)1が連続する区間の長さは 
# [1, 1, 2] を抜き出したときの合計に対応
# これをもとに [[1, 1, 2], 3, 5] → [1, 1, [2, 3, 5]] と走査していけばいい
# ※真ん中の [1, 2, 3] は K = 1 の場合意味がない (両端が0の並ぶ数)
if 2 * K + 1 >= len(cnt_list):
    ans = sum(cnt_list)  # 全部 1 にできる
else:
    l = 0
    r = 2 * K
    tmp_sum = sum(cnt_list[l:r+1])
    max_sum = 0
    while r < len(cnt_list):
        if tmp_sum > max_sum:
            max_sum = tmp_sum
        tmp_sum = tmp_sum + sum(cnt_list[r+1:r+3]) - sum(cnt_list[l:l+2])
        l += 2
        r += 2
    ans = max_sum

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
S = input()
nums = []
if S[0] == '0':
    nums.append(0)
i = 0
while i < N:
    j = i
    while j < N and S[i] == S[j]:
        j += 1
    nums.append(j - i)
    i = j
if S[-1] == '0':
    nums.append(0)

sums = [0] * (len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
ans = 0
left = 0
while left < len(nums):
    right = left + 2 * K + 1
    if right > len(sums):
        right = len(sums) - 1
    ans = max(ans, sums[right]-sums[left])
    left += 2

print(ans)