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()
 
l = [[], []]
ans = []
k = [int(s) for s in S]
if k[0] == 0:
    l[1].append(0)
v0 = 1 if k[0] == 0 else 0
v1 = 1 if k[0] == 1 else 0
for i in range(1, N):
    if (k[i]==0) & (k[i-1]==0):
        v0 += 1
    elif (k[i]==1) & (k[i-1]==0):
        l[0].append(v0)
        v0 = 0
        v1 += 1
    elif (k[i]==0) & (k[i-1]==1):
        l[1].append(v1)
        v0 += 1
        v1 = 0 
    else:
        v1 += 1
        
for i, v in enumerate([v0, v1]):
    if v > 0:
        l[i].append(v)
        
if k[0] == 0:
    l[1].append(0)
    
l[0] += [0]*(K+1)
l[1] += [0]*(K+1)
a = sum(l[0][:K]) + sum(l[1][:K+1])
ans.append(a)
for i in range(1, len(l[0])-K-1):
    a -= l[0][i-1] + l[1][i-1]
    a += l[0][i+K-1] + l[1][i+K]
    ans.append(a)
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import groupby
N, K = map(int,input().split())
S = '1' + input() + '1'
acc = [0]
for i, (k, v) in enumerate(groupby(S)):
    acc.append(acc[i] + len(list(v)))
sz = len(acc)
l = [acc[min(sz - 1, i + 2 * K + 1)] - acc[i] - (i == 0) - (i + 2 * K + 1 >= sz - 1) for i in range(sz)]
print(max(l[::2]))

Submission status: Accepted

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
# -1は終端
S = [int(x) for x in stdin.readline().rstrip()] + [-1]

# 連続して立っている人のカウント
straight_stand_cnt = 0

if S[0] == 0:
    straight_stand_cnt = 1

l = 0
r = 0
ans = -999

while r < N:
    # for DEBUG
    #print(l, r)
    if straight_stand_cnt <= K:
        if S[r] == 1 and S[r+1] == 0:
            straight_stand_cnt += 1

        ans = max(ans, r-l+1)
        r += 1
    else:
        if S[l] == 0 and S[l+1] == 1:
            straight_stand_cnt -= 1
        l += 1      


print(ans)

Submission status: Accepted

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

nums = []
count = 0
prev = '1'
for c in list(s):
    if prev != c:
        nums.append(count)
        count = 1
    else:
        count += 1
    prev = c
nums.append(count)
if prev == '0':
    nums.append(0)

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

ans = 0
lencml = len(cml)
for l in range(0,lencml,2):
    r = l + (2 * k + 1)
    if r >= lencml:
        r = lencml - 1
    tmp = cml[r] - cml[l]
    if ans < tmp:
        ans = tmp

print(ans)

Submission status: Accepted

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

S=S+'E'
ans=-1

if(S[0]=='0'):
    stand=1
else:
    stand=0

L=0
R=0

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc124_d

# input
n, k = [int(s) for s in input().split()]
S = input()
# get ans
node = [len(s) for s in S.split('0')]
node = [s for i, s in enumerate(node) if not (s==0 and i!=0 and i!=len(node)-1)]
arch = [len(s) for s in S.split('1')]
arch = list(filter(int, arch))
from itertools import chain
flatten = chain.from_iterable
xs = list(flatten(zip(node, arch))) + node[-1:]
l = len(xs)
sumlist = [None]*(l+2)
sumlist[-1] = 0
for i in range(l):
    sumlist[i] = sumlist[i-1] + xs[i]
def get_sum(f, n):
    f = min(f, l)
    t = f+n
    t = min(t, l)
    return sumlist[t-1] - sumlist[f-1]
def get_ans():
    for i in range(l//2+1):
        yield get_sum(i*2, k*2+1)
ans = max(get_ans())
# output
# print(node)
# print(arch)
# print(xs)
# print(sumlist)
# print(get_sum(0, 2))
# print(list(get_ans()))
print(ans)

Submission status: Accepted

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

arr = [0] * N
cnt = 0
Flag = False
for i, char in enumerate(s):
    if not Flag and char == '0':
        Flag = True
        cnt += 1
    if char == '1':
        Flag = False
    arr[i] = cnt
ans = 0
for i, val in enumerate(s):
    if val == '0':
        ans = max(ans, bisect_right(arr,arr[i]+K-1)-i)
    else:
        ans = max(ans, bisect_right(arr,arr[i]+K)-i)
print(ans)

Submission status: Accepted

Solution code:
import math
N, K = list(map(int, input().split()))
S = str(input())
list = []
cnt = 1
list.append(1)
for i in range(len(S)):
  if(i + 1) >= len(S): 
    break
  if (S[i+1] != S[i]):
    list.append(i + 2)

# 切り替わりの最初の位置を記録した配列ができた
ans = 0
tmp = 0
# 1始まりのとき
if (S[0] == '1'):
  for i in range(len(list) // 2):
    if ((2 * i) + (2 * K) + 1) >= len(list):
      tmp = len(S) - list[(2 * i)] + 1
      if ans < tmp:
        ans = tmp
      break
    tmp = list[(2 * i) + (2 * K) + 1] - list[(2 * i)]
    if ans < tmp:
      ans = tmp
  # 1の塊しかない場合
  if(len(list) // 2) == 0: ans = len(S)
# 0始まりのとき
if (S[0] == '0'):
  for i in range(math.ceil(len(list) / 2)):
    # 先頭以外の時
    if ((2 * i) - 1) >= 0:
      if ((2 * i) + (2 * K) + 1) > len(list):
        tmp = len(S) - list[(2 * i) - 1] + 1
        if ans < tmp:
          ans = tmp
        break
      tmp = list[(2 * K) + (2 * i)] - list[(2 * i) - 1]
      if ans < tmp:
        ans = tmp
    # 先頭の時
    else:
      if ((2 * i) + (2 * K) + 1) > len(list):
        tmp = len(S)
        if ans < tmp:
          ans = tmp
        break
      tmp = list[(2 * K)] - 1
      if ans < tmp:
        ans = tmp
  # 0の塊しかない場合
  if(len(list) // 2) == 0: ans = len(S)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = input() + '1'
L = []

i = 0
d = []
while i <= n:
    if s[i] == '0':
        d.append(i)

    else:
        if d != []:
            L.append(d)
            d = []
    i += 1

ans = 0
nl = len(L)

if nl <= k:
    print(n)
else:
    for i in range(nl - k + 1):

        if i == 0:
            sta = 0
        else:
            sta = L[i - 1][-1] + 1

        if i == nl - k:
            end = n - 1
        else:
            end = L[i + k][0] - 1

        ans = max(ans, end - sta + 1)

    print(ans)

Submission status: Accepted

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

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

# N, Kがそれぞれ10^5以下なので、O(NK)は不可能
# 1の連続Bit数を最大化する
# K回の操作で、ある区間におけるK個の00を11に変えることに相当。
# (001100を110011にして、111111にするのも結局2回要している)

# 00,11のグループで再カウント、[(start, end, True/False)]: Trueなら1
start = 0
l = []
for i in range(1,N):
    if S[i-1] == S[i]:
        continue
    else:
        v = True if S[i-1] == "1" else False
        l.append((start, i, v))
        start = i
v = True if S[-1] == "1" else False
l.append((start, N, v))

mx = 0
L = len(l)
for i, val in enumerate(l):
    start, end, v = val
    if v is True:   # "1"
        # 1 0 1 0 1として、1+2Kのグループを1にできる
        idx = min(i+2*K, L-1)
    else:   # "0"
        # 0 1 0 1として、2Kのグループを1にできる
        idx = min(i+2*K-1, L-1)
    ln = l[idx][1] - start
    if ln > mx:
        mx = ln

print(mx)

Submission status: Accepted

Solution code:
# しゃくとり
# ref. https://atcoder.jp/contests/abc124/submissions/4962905
N, K = map(int, input().split())
S = map(int, list(input()))

num_list = []
now = 1
count = 0

for char in S:
    if char == (0 + now):
        count += 1
    else:
        num_list.append(count)
        now = 1 - now
        count = 1
if count > 0:
    num_list.append(count)
# 1-0-1-0になっていたら、最後に1つ0を足す
if len(num_list) % 2 == 0:
    num_list.append(0)

ans = 0
add = 2 * K + 1

left = 0
right = 0
tmp = 0 # [left, right)のsum
for i in range(0, len(num_list), 2):
    next_left = i
    next_right = min(i + add, len(num_list))

    while left < next_left:
        tmp -= num_list[left]
        left += 1
    while right < next_right:
        tmp += num_list[right]
        right += 1
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N, K = [int(_) for _ in input().split()]
S = str(input())

Nums = []
now, cnt = 1, 0
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
# ans = 0
# for i in range(0, len(Nums), 2):
#     tmp = 0
#     left = i
#     right = min(i+add, len(Nums))
#     j = left
#     while j < right:
#         tmp += Nums[j]
#         j += 1
#     ans = max(tmp, ans)
# print(ans)

#------------------------
# add = 2 * K + 1
# ans = 0
# left = 0
# right = 0
# tmp = 0
# for i in range(0, len(Nums), 2):
#     nextLeft = i 
#     nextRight = min(i + add, len(Nums))
#     while nextLeft > left:
#         tmp -= Nums[left]
#         left += 1
#     while nextRight > right:
#         tmp += Nums[right]
#         right += 1
#     #print('left, right:   ', left, right)
#     ans = max(tmp, ans)
        
# print(ans)
#------------------------
#print(Nums)
add = 2 * K + 1
sums = [0 for _ in range(len(Nums) + 1)]
for i in range(len(Nums)):
    sums[i+1] = sums[i] + Nums[i]
#print(sums)

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

Submission status: Accepted

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

now = 1
cnt = 0
for i in range(len(s)):
    if s[i] == str(now): cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if not cnt == 0: nums.append(cnt)
if len(nums) % 2 == 0: nums.append(0)

summ = [0]
for i in range(len(nums)):
    summ.append(summ[i]+nums[i])

ans = 0
for i in range(len(nums))[::2]:
    left = i
    right = min(i+k*2+1, len(nums))
    tmp = summ[right] - summ[left]

    ans = max(tmp, ans)


print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N, K = [int(_) for _ in input().split()]
S = str(input())

Nums = []
now, cnt = 1, 0
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
# ans = 0
# for i in range(0, len(Nums), 2):
#     tmp = 0
#     left = i
#     right = min(i+add, len(Nums))
#     j = left
#     while j < right:
#         tmp += Nums[j]
#         j += 1
#     ans = max(tmp, ans)
# print(ans)

#------------------------
add = 2 * K + 1
ans = 0
left = 0
right = 0
tmp = 0
for i in range(0, len(Nums), 2):
    nextLeft = i 
    nextRight = min(i + add, len(Nums))
    while nextLeft > left:
        tmp -= Nums[left]
        left += 1
    while nextRight > right:
        tmp += Nums[right]
        right += 1
    #print('left, right:   ', left, right)
    ans = max(tmp, ans)
        
print(ans)

Submission status: Accepted

Solution code:
# ref. https://atcoder.jp/contests/abc124/submissions/4963013
N, K = map(int, input().split())
S = map(int, list(input()))

num_list = []
now = 1
count = 0

for char in S:
    if char == (0 + now):
        count += 1
    else:
        num_list.append(count)
        now = 1 - now
        count = 1
if count > 0:
    num_list.append(count)
# 1-0-1-0になっていたら、最後に1つ0を足す
if len(num_list) % 2 == 0:
    num_list.append(0)

#累積和を作る
cumulative = [0] * (len(num_list) + 1)
for i in range(len(num_list)):
    cumulative[i + 1] = cumulative[i] + num_list[i]

ans = 0
add = 2 * K + 1

for i in range(len(cumulative)):
    if i % 2 == 0:
        add_i = min(i + add, len(cumulative) - 1)
        ans = max(ans, cumulative[add_i] - cumulative[i])
print(ans)

Submission status: Accepted

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

DP = [0]
ans = 0
l = 0

for index,x in enumerate(S):
    if(index==0):
        if(x=='0'):
            DP.append(0)
            DP.append(1)
        else:
            DP.append(1)
    else:
        if(S[index-1]!=x):
            DP.append(DP[-1]+1)
        else:
            DP[-1]+=1
    if(index==N-1):
        if(x=='1'):
            DP.append(DP[-1])
        DP.append(DP[-1])

l=0
i = min(int((len(DP))/2)-1,K)
while(1+2*i+l<len(DP)):
    ans = max(DP[2*i+1+l]-DP[l],ans)
    l+=2

if(not '0' in S):
    ans = len(S)
elif(not '1' in S):
    ans = len(S)

print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

positions = []
idx = 0
keep = None
while idx < N:
    if S[idx] == '0':
        if keep == None:
            keep = idx
    else:
        # 1の場合は無視
        if keep != None:
            positions.append([keep, idx])
            keep = None
        else:
            # keepしない場合
            keep = None
    idx += 1
else:
    if keep != None:
        positions.append([keep, keep+1])
#  print(positions)
if len(positions) == 0:
    print(N)
    exit()
elif len(positions) <= K:
    print(N)
    exit()

ans = 0

for idx in range(len(positions)):
    if idx + K - 1 > len(positions) - 1:
        break
    if idx == 0:
        left = 0
    else:
        left = positions[idx-1][1]

    if idx + K - 1 == len(positions)-1:
        end = N
    else:
        end = positions[idx+K-1+1][0]
    #  print(end, left)
    ans = max(ans, end - left)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
s=list(map(int,s))
stack=[]
tmp=0
now=1
for i in range(n):
  if s[i]==now:
    tmp+=1
  else:
    stack.append(tmp)
    tmp=1
    now=1-now
stack.append(tmp)
if len(stack)%2==0:
  stack.append(0)
Acc=[0]*(len(stack)+1)
for i in range(len(stack)):
  Acc[i+1]=Acc[i]+stack[i]
ans=0
for i in range(0,len(stack),2):
  left = i
  right = min(i+k*2+1,len(stack))
  ans=max(ans,Acc[right]-Acc[left])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
S = input() + "2"
T = []
i = 0
for j in range(1, len(S)):
    if S[i] != S[j]:
        T.append(j - i)
        i = j
U = [0] + list(accumulate(T))
ans = 0
for i in range(len(T)):
    if (i + int(S[0])) % 2 == 0:
        j = i + 2 * (K - 1) + 1
    else:
        j = i + 2 * K
    j = min(j, len(T) - 1)
    ans = max(ans, U[j + 1] - U[i])
print(ans)

Submission status: Accepted

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

now = 1
cnt = 0
one_zero = [0]
for i in S:
    if i == now:
        cnt += 1
    else:
        one_zero.append(cnt)
        now = 1 - now
        cnt += 1
if (cnt != 0):
    one_zero.append(cnt)

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

print(ans)

Submission status: Accepted

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

if S.count("0") == 0:
	print(N)
	exit(0)


curLen=0
# rangeLens=[]
rangeVals=[]
stackLens=[]
prev = S[0]
for n in range(N):
	if prev != S[n]:
		# rangeLens.append(curLen)
		stackLens.append(curLen)
		rangeVals.append(prev)
		# curLen=1
	# else:
	# 	curLen+=1
	curLen+=1
	prev = S[n]

stackLens.append(curLen)
rangeVals.append(prev)

stackLens.insert(0,0)
rangeVals.insert(0,rangeVals[0])

# stackLens.append(curLen+1)
# rangeVals.append(prev)

# print(stackLens)

curSumLenMax=0
for r in range(1,len(stackLens)):
	rangeLen=0
	if rangeVals[r] == "0":
		high = 2*K+r-1
		if len(stackLens)-1 < high:
			high = len(stackLens)-1
		rangeLen=stackLens[high]-stackLens[r-1]
	else:
		high = 2*K+1+r-1
		if len(stackLens)-1 < high:
			high = len(stackLens)-1
		# print(high,r,stackLens[high],stackLens[r])
		rangeLen=stackLens[high]-stackLens[r-1]
	curSumLenMax = max( curSumLenMax, rangeLen )


print(curSumLenMax)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    s = input()
    
    arr = []
    if s[0] == '0':
        arr.append(0)
    cnt = 1
    i = 1
    while i != n:
        if s[i] != s[i - 1]:
            arr.append(cnt)
            cnt = 1
        else:
            cnt += 1
        i += 1
    arr.append(cnt)
    if s[-1] == '0':
        arr.append(0)
    
    ans = 0
    curr = arr[0]
    j = 1
    if len(arr) - 1 <= 2 * k:
        print(n)
        return 0
    for i in range(1, len(arr), 2):
        curr += arr[i] + arr[i + 1]
        if i - j == 2 * k:
            curr -= arr[j] + arr[j - 1]
            j += 2
        ans = max(ans, curr)
    print(ans)
    return 0
main()

Submission status: Accepted

Solution code:
def main():
    ans = 0
    n, k = map(int, input().split())
    s = input()
    arr = []
    if s[0] == '0':
        arr.append(0)
    cnt = 1
    i = 1
    while i != n:
        if s[i] != s[i - 1]:
            arr.append(cnt)
            cnt = 1
        else:
            cnt += 1
        i += 1
    arr.append(cnt)
    if s[-1] == '0':
        arr.append(0)
    ans = 0
    curr = arr[0]
    j = 1
    if len(arr) - 1 <= 2 * k:
        print(n)
        return 0
    for i in range(1, len(arr), 2):
        curr += arr[i] + arr[i + 1]
        if i - j == 2 * k:
            curr -= arr[j] + arr[j - 1]
            j += 2
        ans = max(ans, curr)
    print(ans)
    return 0
main()

Submission status: Accepted

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

X=[]
now=1
tmp=0
for i in range(N):
	if int(S[i])-0==now:
		tmp+=1
	else:
		now=1-now
		X.append(tmp)
		tmp=1
if tmp!=0:
	X.append(tmp)

n=len(X)
R=[0]*(n+1)
for i in range(n):
	R[i+1]=X[i]+R[i]

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

Submission status: Accepted

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

cnt = 0
now = 1
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
tmp = 0

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

print(ans)

Submission status: Accepted

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

# 終端を追加
S = S + 'E'
ans = -1

# standは利用した命令の数であるのでS[0] == '0'のときstand = 1になる
if (S[0] == '0'):
    stand = 1
else:
    stand = 0

L = 0
R = 0

# 尺取り法　(two pointers というみたい)
while(R < N):
    if (stand <= K):
        # 0からはじまる連続列が見つかったらstandを増やす
        if (S[R] == '1' and S[R+1] == '0'):
            stand+=1
        ans = max(ans, R - L + 1)
        R += 1
    elif L == R:
        L += 1
        R += 1
    else:
        if (S[L] == '0' and S[L+1] == '1'):
            stand -= 1
        L += 1

print(ans)

Submission status: Accepted

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

# 終端を追加
S = S + 'E'
ans = -1

# standは利用した命令の数であるのでS[0] == '0'のときstand = 1になる
if (S[0] == '0'):
    stand = 1
else:
    stand = 0

L = 0
R = 0

# 尺取り法　(two pointers というみたい)
while(R < N):
    if (stand <= K):
        # 0からはじまる連続列が見つかったらstandを増やす
        if (S[R] == '1' and S[R+1] == '0'):
            stand+=1
        ans = max(ans, R - L + 1)
        R += 1
    elif L == R:
        L += 1
        R += 1
    else:
        if (S[L] == '0' and S[L+1] == '1'):
            stand -= 1
        L += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

S = input()
n = list(map(int, str(S)))
count = 1
mas = []
for i in range(N-1):
    if n[i] == n[i + 1]:
        count += 1
        if i == N-2:
            mas.append(count)
    else:
        mas.append(count)
        count = 1
        if i == N-2:
            mas.append(1)
        

mas2 = []
if n[0] == 0:
    mas.insert(0, 0)
    
if n[N-1] == 0:
    mas.append(0)
    
l=len(mas)
mas2=[0] + list(accumulate(mas))
#for i in range(1, 1+len(mas)):
#    mas2.append(sum(mas[:i]))
    
if K >= (l-1)/2:
    print(N)
else:
    mas3 = []
    k = int(((l-1)/2)-K+1)
    for i in range(k):
        mas3.append(mas2[K*2 + 2*i+1]-mas2[0 + 2*i])
    print(max(mas3))

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
S = "1" + input() + "1"
arr = []
cnt = 0
flg = 1
for s in S:
    if s == "1" and 1 - flg:
        flg = 1
        arr.append(cnt)
        cnt = 1
    elif s == "0" and flg:
        flg = 0
        arr.append(cnt)
        cnt = 1
    else:
        cnt += 1
arr.append(cnt)
csum = [0] + list(accumulate(arr))
ans = 0
tmp = 0
for i in range(0, len(csum), 2):
    l = i
    r = min(i + 2*K + 1, len(csum) - 1)
    tmp = csum[r] - csum[l] - (r == len(csum) - 1) - (l == 0) - (l == 1)
    ans = max(ans, tmp)
if len(csum) == 2:
    print(csum[1] - 2)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = "1" + input() + "1"
arr = []
cnt = 0
flg = 1
for s in S:
    if s == "1" and 1 - flg:
        flg = 1
        arr.append(cnt)
        cnt = 1
    elif s == "0" and flg:
        flg = 0
        arr.append(cnt)
        cnt = 1
    else:
        cnt += 1
arr.append(cnt)
csum = [0] * (len(arr)+1)
for i in range(len(arr)):
    csum[i + 1] = csum[i] + arr[i]
ans = 0
tmp = 0
for i in range(0, len(csum), 2):
    l = i
    r = min(i + 2*K + 1, len(csum) - 1)
    tmp = csum[r] - csum[l] - (r == len(csum) - 1) - (l == 0) - (l == 1)
    ans = max(ans, tmp)
if len(csum) == 2:
    print(csum[1] - 2)
else:
    print(ans)

Submission status: Accepted

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

# Initial values
ans=1
l=0
r=0
edge=[]

# 立っているグループのカウント
# 最初の文字が0なら1
if S[l]=='0':
    count=1
else:
    count=0    

# ｒがNまでループ
while(r < N-1):
    r+=1
    #　もし1=>0の境目だと、countを追加
    if ( S[r-1]=='1') & (S[r]=='0'):
        count+=1

    #　countがKを超すとlのループに入る(Break)
    while(count>K):
        l+=1
        # lを更新したとき0=>1の境目だと、l~r間の0グループが減るので、countを減らす
        if (S[l-1]=='0') & (S[l]=='1'):
            count-=1
        #lがrを追い越さないように
        if l==r:
            r+=1
        #print(r,l,count,ans)

    #何事もなく 進んだ場合は答えの更新
    ans=max(ans,r-l+1)
    #print(r,l,count,ans) 

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
s = [int(S[i]) for i in range(0,N)]
#print (s)

ll = []
v = s[0]
a = 0
for i in range(0,N) :
    if s[i] == v :
        if s[i] == 1 :
            a += 1
        else :
            a -= 1
    else :
        ll.append(a)
        a = 0
        v = s[i]
        if s[i] == 1 :
            a += 1
        else :
            a -= 1
ll.append(a)    
#print (ll)

left = 0
right = 0
NN = len(ll)
max = 0
ln = 0

if (right < NN) :   #  leading 1
    if ll[right] > 0 :
        ln += ll[right]
        right += 1
for i in range(0,K) :
    if (right < NN) :    #  leading 0
        if ll[right] < 0 :
            ln -= ll[right]
            right += 1
    if (right < NN) :    #  trailing 1
        if ll[right] > 0 :
            ln += ll[right]
            right += 1
    else :               #   reached to the end
        break
    
max = ln
while (right < NN) :
    if (right < NN) :    #  leading 0
        if ll[right] < 0 :
            ln -= ll[right]
            right += 1
    if (right < NN) :    #  trailing 1
        if ll[right] > 0 :
            ln += ll[right]
            right += 1
    else :                # reached to the end
        right = right  # do nothing
    
    if (left < NN) :    #  leading 1
        if ll[left] > 0 :
            ln -= ll[left]
            left += 1
    if (left < NN) :    #  trailing 0
        if ll[left] < 0 :
            ln += ll[left]
            left += 1
    if max < ln :
        max = ln

print (max)

Submission status: Accepted

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

num101 = []
if("0" == S[1]):
    num101 = [0]
for i in range(1, N + 1):
    if(S[i - 1] != S[i]):
        st = i
    if(S[i] != S[i + 1]):
        num101.append(i - st + 1)
if("0" == S[-2]):
    num101.append(0)
#print("num101= {}".format(num101))

sum101 = [0]
for i in range(len(num101)):
    sum101.append(sum101[-1] + num101[i])
#print("sum101={}".format(sum101))

maxsum = 0
for i in range(0, len(sum101), 2):
    left = i
    right = min(i + 2 * K + 1, len(sum101) - 1)
    sumK = sum101[right] - sum101[left]
    maxsum = max(maxsum, sumK)
    if(right >= len(sum101) - 1):
        break

print(maxsum)

Submission status: Accepted

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

# ランレングス ex:00010 => ["03", "11", "01"]
run_length_S = []
count = 1
for i in range(len(S)):
    try:
        if S[i] == S[i+1]:
            count += 1
        else:
            run_length_S.append([S[i], count])
            count = 1
    except:
        run_length_S.append([S[i], count])

# しゃくとり法
right = 0
total = 0
max_total = 0

for left in range(len(run_length_S)):
    # Kより下なら右に移動
    while right < len(run_length_S) and K >= 0:
        # 1なら移動
        if run_length_S[right][0] == "1":
            total += int(run_length_S[right][1])
            right += 1
        # 0ならKより下で移動
        elif K == 0 and run_length_S[right][0] == "0":
            break
        else:
            total += int(run_length_S[right][1])
            right += 1
            K -= 1
    
    # 最大合計の更新
    max_total = max(total, max_total)
    
    # leftをインクリメントする準備
    if right == left:
        right += 1
    else:
        total -= int(run_length_S[left][1])
    
    # 外されるleftが0だった場合、反転回数を増やす
    if run_length_S[left][0] == "0":
        K += 1

print(max_total)

Submission status: Accepted

Solution code:
t,s=open(0)
n,k=map(int,t.split())
l=2*k+1
x=[0]+[i for i in range(n)if s[i]!=s[i-1]]+[n]*l
print(max(x[i+l]-x[i]for i in range(s>'1',len(x)-l,2)))

Submission status: Accepted

Solution code:
def d_handstand(N, K, S):
    index_switched = [0] + [i for i in range(1, N) if S[i] != S[i - 1]]

    ans_candidate = []
    for k in range(len(index_switched)):
        if S[index_switched[k]] == '0':
            t = index_switched[k + 2 * K] if k + 2 * K < len(index_switched) else N
            ans_candidate.append(t - index_switched[k])
        elif S[index_switched[k]] == '1':
            t = index_switched[k + 2 * K + 1] if k + 2 * K + 1 < len(index_switched) else N
            ans_candidate.append(t - index_switched[k])
    return max(ans_candidate)

N, K = [int(i) for i in input().split()]
S = input()
print(d_handstand(N, K, S))

Submission status: Accepted

Solution code:
t,s=open(0)
n,k=map(int,t.split())
l=2*k+1
x=[0]*2+[i for i in range(1,n)if s[i]!=s[i-1]]+[n]*l
print(max(x[i+l]-x[i]for i in range(s>'1',len(x)-l,2)))

Submission status: Accepted

Solution code:
t,s=open(0)
n,k=map(int,t.split())
l=2*k+1
x=[0]*2+[i+1for i in range(n-1)if s[i]!=s[i+1]]+[n]*l
print(max(x[i+l]-x[i]for i in range(s>'1',len(x)-l,2)))

Submission status: Accepted

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

# 部分文字列の和を算出
array = []
now_num = 1
count = 0
for i in s:
  if now_num == int(i):
    count += 1
  else:
    array.append(count)
    count = 1
    now_num = 1 - now_num

if count != 0:
  array.append(count)

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

res = 0
add = 2 * k + 1
ans = 0
left = 0
right = 0
tmp = 0

for i in range(len(array))[::2]:
    next_left = i
    next_right = min(i+add, len(array))
    # 尺取法
    while next_left > left:
        tmp -= array[left]
        left += 1
    while next_right > right:
        tmp += array[right]
        right += 1
    ans = max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = str(input())
S_list = []
cum_list = [0]
tmp = 1
count = 0

for i in range(N):
    if i == 0:
        if int(S[i]) == tmp:
             count += 1
        else:
            S_list.append(count)
            count = 1
    else:
        if S[i] == S[i - 1]:
            count += 1
            
        else:
            S_list.append(count)
            count = 1

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


now = 0
for i in range(len(S_list)):
    now += S_list[i]
    cum_list.append(now)


answer_list = []
i = 0
if 2 * K + 1 < len(cum_list):
    while i + 2 * K + 1 < len(cum_list):
        answer_list.append(cum_list[i + 2 * K + 1] - cum_list[i])
        i += 2
else:
    answer_list.append(len(S))
answer = max(answer_list)
print(answer)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
instr=input()
lft=0
rgt=1
voids=0 if instr[0] == '1' else 1

maxlen=0
while lft < rgt:
    maxlen = max(maxlen, rgt-lft)
    if rgt < N and (instr[rgt] == '1' or (instr[rgt-1] == '0' and instr[rgt] == '0')):
        rgt += 1
    elif rgt < N and instr[rgt] == '0' and voids < K:
        voids += 1
        rgt += 1
    else:
        if lft+1 < N and instr[lft] == '0' and instr[lft+1] == '1':
            voids -= 1
        lft += 1

print(maxlen)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
instr=input()
lft=0
rgt=1
voids=0 if instr[0] == '1' else 1

maxlen=0
while lft < rgt:
    maxlen = max(maxlen, rgt-lft)
    # print("lft {} rgt {} maxlen {} void {} {}".format(lft, rgt, maxlen, voids, instr[lft:rgt]))
    if rgt < N and (instr[rgt] == '1' or (instr[rgt-1] == '0' and instr[rgt] == '0')):
        rgt += 1
    elif rgt < N and instr[rgt] == '0' and voids < K:
        voids += 1
        rgt += 1
    else:
        # 左を動かすケース
        if lft+1 < N and instr[lft] == '0' and instr[lft+1] == '1':
            voids -= 1
        lft += 1

print(maxlen)