Problem:


Score : 400 points

Problem Statement

N people are arranged in a row from left to right.

You are given a string S of length N consisting of 0 and 1, and a positive integer K.

The i-th person from the left is standing on feet if the i-th character of S is 0, and standing on hands if that character is 1.

You will give the following direction at most K times (possibly zero):

Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.

Find the maximum possible number of consecutive people standing on hands after at most K directions.

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of consecutive people standing on hands after at most K directions.

Sample Input 1

5 1
00010

Sample Output 1

4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:

Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Accepted

Solution code:
import copy
N, K = map(int, input().split())
S = input()
if S.count('0') == 0:
    print(S.count('1'))
    exit()

if N == K:
    print(N)
    exit()

olst = []
zlst = []
tmp = S[0]
tcnt = 1
for i in range(1, N):
    if tmp != S[i]:
        if tmp == '1':
            olst.append(tcnt)
        else:
            zlst.append(tcnt)
        tmp = S[i]
        tcnt = 1
    else:
        tcnt += 1

if tmp == '1':
    olst.append(tcnt)
else:
    zlst.append(tcnt)

index = 0
flst, slst = [], []
if S[0] == '1':
    index = 1
    flst = copy.deepcopy(olst)
    slst = copy.deepcopy(zlst)
else:
    flst = copy.deepcopy(zlst)
    slst = copy.deepcopy(olst)
total = [0] * (len(flst) + len(slst) + 1)
for i in range(1, len(flst) + len(slst) + 1):
    if i % 2 != 0:
        total[i] += flst[i // 2] + total[i - 1]
    else:
        total[i] += slst[i // 2 - 1] + total[i - 1]
ans = 0
tmp1 = (2 * K) - 1
tmp2 = 2 * K
for i in range(1, len(total) - K):
    tmp = 0
    if index == 0:
        if i % 2 != 0:
            if i + tmp1 < len(total):
                tmp += total[i + tmp1] - total[i - 1]
            else:
                tmp += total[-1] - total[i - 1]
        else:
            if i + tmp2 < len(total):
                tmp += total[i + tmp2] - total[i - 1]
            else:
                tmp += total[-1] - total[i - 1]
    else:
        if i % 2 != 0:
            if i + tmp2 < len(total):
                tmp += total[i + tmp2] - total[i - 1]
            else:
                tmp += total[-1] - total[i - 1]
        else:
            if i + tmp1 < len(total):
                tmp += total[i + tmp1] - total[i - 1]
            else:
                tmp += total[-1] - total[i - 1]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

s.append("")

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

if s[0] == "0":
    l.insert(0, 0)
if s[-2] == "0":
    l.append(0)

cusum = [0]*(len(l)+1)
for i in range(len(l)):
    cusum[i+1] = cusum[i]+l[i]

ans = 0
for i in range(0, len(cusum), 2):
    j = i+k*2+1
    if j >= len(cusum): j = len(cusum) - 1
    ans = max(ans, cusum[j]-cusum[i])

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
if N==1:
    print(1)
    exit()


lst=[]
if S[0]!="1":
    lst.append([0,0])
flag=0
for i in range(N):
    if flag==0 and S[i]=="1":
        flag=1
        st=i
    elif flag and S[i]=="0":
        lst.append([st,i-1])
        flag=0
if S[-1]!="1":
    lst.append([N-1,N-1])

if flag:
    lst.append([st,N-1])

if K>=len(lst):
    print(N)
    exit()
else:
    value=0
    for i in range(len(lst)-K):
        a=lst[i+K][1]-lst[i][0] +1
        if a>value:
            value=a
print(value)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[0]
s=input()
cnt=0
for c in s:
  if (len(l)%2) ^ (c=='0'):
    cnt+=1
  else:
    l.append(cnt)
    cnt+=1
l.append(cnt)
if len(l)%2:
  l.append(cnt)
#print(l)
k = min(k,(len(l)-1)//2)
#print(l,k)
ans = 0
for i in range(0,len(l)-2*k-1,2):
  ans = max(ans,l[i+2*k+1]-l[i])
print(ans)

Submission status: Accepted

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

if len(set(S)) == 1:
  print(len(S))
  exit(0)
  

nums = []
if S[0] != '1':
  nums.append(0)

current = S[0]
count = 1
for i, s in enumerate(list(S)):
  if i == len(S)-1:
    nums.append(count)
    break
  if S[i+1] != s:
    nums.append(count)
    count = 1
    current = s
  else:
    count += 1

if S[len(S)-1] != '1':
  nums.append(0)

sums = [0]
for index, i in enumerate(nums):
  sums.append(sums[index] + 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:
N, K = map(int, input().split())
S = input()
T = []
count = 1
for n in range(N - 1):
    s0, s1 = S[n], S[n + 1]
    if s0 == s1:
        count += 1
    else:
        T.append(count)
        count = 1
T.append(count)
if S[0] == '0':
    T = [0] + T
if S[-1] == '0':
    T = T + [0]
L = len(T)
if 2 * K + 1 >= L:
    print(N)
    exit()
# 偶数番目から始まる連続する2K+1個の和の最大値
now = sum(T[0: 2 * K + 1])
ans = now
for l in range(2, L - (2 * K + 1) + 1, 2):
    now -= T[l - 2]
    now -= T[l - 1]
    now += T[l + 2 * K - 1]
    now += T[l + 2 * K]
    if now > ans:
        ans = now
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from numpy import cumsum


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

if len(set(S)) == 1:
    print(N)
    exit()

# ランレングス圧縮
G = []
for k, v in groupby(S):
    G.append(len(list(v)))
# 1 0 1 0 1...の配列が欲しいので、
# 先頭、末尾が0ならダミーの要素をそれぞれ追加する
if S[0] == '0':
    G.insert(0, 0)
if S[-1] == '0':
    G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, gc-w+2, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from numpy import cumsum


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

if len(set(S)) == 1:
    print(N)
    exit()

G = []
for k, v in groupby(S):
    G.append(len(list(v)))
if S[0] == '0':
    G.insert(0, 0)
if S[-1] == '0':
    G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, gc-w+2, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from numpy import cumsum


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

if len(set(S)) == 1:
    print(N)
    exit()

G = []
if S[0] == '0':
    G.append(0)
for k, v in groupby(S):
    G.append(len(list(v)))
G.append(0)

cum = [0]
cum.extend(list(cumsum(G)))
cum.append(0)

ans = 0
gc = len(G)
w = min(gc, 3+(K-1)*2)
for i in range(0, gc-w+2, 2):
    ans = max(ans, cum[i+w]-cum[i])
print(ans)

Submission status: Accepted

Solution code:
from sys import exit
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2

n,k=map(int,input().split())
s=list(input())
x=groupby(s)
l=len(x)
y=[x[i][1] for i in range(l)]

if x[0][0]=="0":
    su=sum(y[:2*k])
    ans=su
    y.pop(0)
    l-=1
else:
    ans=0
su=sum(y[:2*k+1])
ans=max(ans,su)
l_sub=(l-(2*k+1))//2
if l_sub<=0:
    print(ans)
    exit()
for i in range(l_sub):
    su-=y[2*i]
    su-=y[2*i+1]
    su+=y[2*k+1+(2*i)]
    su+=y[2*k+1+(2*i+1)]
    ans=max(su,ans)
#最後のところの判定っぽいな
if 2*k+1+2*l_sub<l:
    su-=y[2*l_sub]
    su-=y[2*l_sub+1]
    su+=y[2*k+1+2*l_sub]
    ans=max(su,ans)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
start = [0] * k
c = '0'
ret = 0
for i in range(len(s)):
    if c == '0' and s[i] == '1':
        start.append(i)
    elif c == '1' and s[i] == '0':
        ret = max(ret, i - start.pop(0))
    c = s[i]
ret = max(ret, n - start.pop(0))
print(ret)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
start = [0] * (k + 1)
c = '1'
ret = 0
for i in range(len(s)):
    if c == '0' and s[i] == '1':
        start.append(i)
    elif c == '1' and s[i] == '0':
        ret = max(ret, i - start.pop(0))
    c = s[i]
ret = max(ret, n - start.pop(0))
print(ret)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
l = [0] * (k * 2 + 1)
c = '1'
p = 0
ret = 0
for i in range(len(s)):
    if s[i] != c:
        ret = max(ret, i - l[p])
        l.append(i)
        if c == '1':
            l.pop(0)
            l.pop(0)
        c = s[i]
ret = max(ret, n - l[p])
print(ret)

Submission status: Accepted

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

segs = []
i = 0
while i < n:
    if s[i] == '0':
        j = i
        while j + 1 < n and s[j + 1] == '0':
            j += 1
        segs.append((i, j))
        i = j
    i += 1
segs = segs or [(0, n - 1)]

ret = 0
for right in range(len(segs)):
    left = max(0, right - nFlips + 1)
    size = segs[right][1] - segs[left][0] + 1
    size += segs[left][0] - segs[left - 1][1] - 1 if left - 1 >= 0 else segs[left][0]
    size += segs[right + 1][0] - segs[right][1] - 1 if right + 1 < len(segs) else n - segs[right][1] - 1
    ret = max(ret, size)
print(ret)

Submission status: Accepted

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

segs = []
i = 0
while i < n:
    if s[i] == '0':
        j = i
        while j + 1 < n and s[j + 1] == '0':
            j += 1
        segs.append((i, j))
        i = j
    i += 1
segs = segs or [(0, n - 1)]

ret = 0
left = 0
for right in range(len(segs)):
    while right - left + 1 > nFlips:
        left += 1
    size = segs[right][1] - segs[left][0] + 1
    size += segs[left][0] - segs[left - 1][1] - 1 if left - 1 >= 0 else segs[left][0]
    size += segs[right + 1][0] - segs[right][1] - 1 if right + 1 < len(segs) else n - segs[right][1] - 1
    ret = max(ret, size)
print(ret)

Submission status: Accepted

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

segs = []
i = 0
while i < n:
    if s[i] == '0':
        j = i
        while j + 1 < n and s[j + 1] == '0':
            j += 1
        segs.append((i, j))
        i = j + 1
    else:
        i += 1
segs = segs or [(0, n - 1)]

ret = 0
left = 0
for right in range(len(segs)):
    while right - left + 1 > nFlips:
        left += 1
    size = segs[right][1] - segs[left][0] + 1
    size += segs[left][0] - segs[left - 1][1] - 1 if left - 1 >= 0 else segs[left][0]
    size += segs[right + 1][0] - segs[right][1] - 1 if right + 1 < len(segs) else n - segs[right][1] - 1
    # print('(%d, %d) -> %d' % (left, right, size))
    ret = max(ret, size)
print(ret)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
s = input() + 'E'
top = int(s[0])
now = s[0]
idx = 0
ranges = []
for i, v in enumerate(s):
	if now != v:
		ranges.append(i - idx)
		idx = i
		now = v
zero = (k * 2) * [0]
ranges = zero + ranges + zero
targetIdx = 1 if top % 2 == 0 else 0 
ret = 0
tmp = 0
for i, v in enumerate(ranges):
	tmp += v
	if i > (k * 2 + 1):
		tmp -= ranges[i - (k * 2 + 1)]
	if i % 2 == targetIdx:
		ret = max(tmp, ret)
print(ret)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
l = [0] * (k * 2 + 1)
c = '1'
p = 0
ret = 0
for i in range(len(s)):
    if s[i] != c:
        ret = max(ret, i - l[p])
        l.append(i)
        if c == '1':
            p += 2
        c = s[i]
ret = max(ret, n - l[p])
print(ret)

Submission status: Accepted

Solution code:
N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
ssc = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        ssc.append(len(subs))
        subs = s
        continue
    subs += s
ss.append(subs)
ssc.append(len(subs))
suma = [0]
for sc in ssc:
    suma.append(suma[-1] + sc)

#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = suma[r] - suma[l]
    max_c = max(max_c, c)

print(max_c)

Submission status: Accepted

Solution code:
from bisect import bisect_right


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

psum = [0] * 2
ncnt = [0] * 2

i = 1
state = int(S[0])
if state == 0:
    ncnt[i] += 1
for s in S:
    if int(s) != state:
        psum.append(psum[i])
        ncnt.append(ncnt[i])
        i += 1
        state ^= 1
        if s == '0':
            ncnt[i] += 1

    psum[i] += 1

ans = 0
for i in range(len(psum)):
    j = bisect_right(ncnt, K + ncnt[i])
    ans = max(ans, psum[j - 1] - psum[i])

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
#Aは0の左端、Bは0の右端
A=[]
B=[]
for i in range(N-1):
  if S[i]=='0'and S[i+1]=='1':
    B.append(i)
if S[-1]=='0':
  B.append(N-1)
if S[0]=='0':
  A.append(0)
for i in range(N-1):
  if S[i]=='1'and S[i+1]=='0':
    A.append(i+1)

if len(A)<=K:
  print(N)
else:
  y=A[K]
  z=N-B[-1*(K+1)]-1
  l=0
  ans=0
  for i in range(len(A)-K-1):
    l=A[i+K+1]-B[i]-1
    ans=max(l,ans)
  print(max(ans,y,z))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=list(input())
j=0
ans=0
cnt=0
for i in range(N):
  if S[i]=="0":
    if i==0 or S[i-1]=="1":
      cnt+=1
  if cnt>K:
    while S[j]=="1":
      j+=1
    while S[j]=="0":
      j+=1
    cnt-=1
  ans=max(ans,i-j+1)

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
a = []
for i in range(n):
    if i == 0 or s[i] != s[i - 1]:
        a.append(1)
    else:
        a[len(a) - 1] += 1
for i in range(1, len(a)):
    a[i] += a[i - 1]
cur = int(s[0])
ans = 0
for i in range(len(a)):
    tmp = a[i]
    if cur:
        if i > 2 * m:
            tmp -= a[i - 2 * m - 1]
    else:
        if i > 2 * m - 1:
            tmp -= a[i - 2 * m]
    ans = max(ans, tmp)
    cur = 1 - cur
print(ans)

Submission status: Accepted

Solution code:
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/arc081/tasks/arc081_b
# D - Coloring Dominoes
"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()
K = gi()
S = gw()

seg_ps = []

seg_ps.append(0)

cl = 1
cur = S[0]

for i in range(1, len(S)):
    if (S[i] == S[i - 1]):
        cl += 1
    else:
        tail = seg_ps[-1]
        seg_ps.append(tail + cl)
        cur = S[i]
        cl = 1

seg_ps.append(seg_ps[-1] + cl)

ans = 0

start1 = S[0] == '1'

for i in range(1, len(seg_ps)):
    is1 = 0
    if start1:
        is1 = i % 2
    else:
        is1 = (i + 1) % 2
    if is1:
        si = max(0, i - 2 * K - 1)
    else:
        si = max(0, i - 2 * K)
    ans = max(ans, seg_ps[i] - seg_ps[si])

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
j=0
ans=0
cnt=0
for i in range(n):
    if s[i]=="0":
        if i==0 or s[i-1]=="1":
            cnt+=1
    if cnt>k:
        while s[j]=="1":
            j+=1
        while s[j]=="0":
            j+=1
        cnt-=1
    ans=max(ans,i-j+1)

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF = 10**18


def input():
    return sys.stdin.readline().rstrip()


def main():
    N,K=map(int,input().split())
    S=list(map(int,list(input())))
    f=S[0]
    left1=0
    for i,x in enumerate(S):
        if x==0:
            break
        else:
            left1+=1
    l=[left1]
    tmp=0
    pre=1
    for i,x in enumerate(S[left1:]):
        if pre!=x:
                l.append(tmp)
                tmp=0
        tmp+=1
        pre=x
    l.append(tmp)
    A=[0]*(len(l)+1)
    for i in range(len(l)):
        A[i+1]=A[i]+l[i]
    ans=0
    for i in range(len(l)+1):
        if i%2:
            ans=max(ans,A[i]-A[max(0,i-K*2)])
        else:
            ans=max(ans,A[i]-A[max(0,i-K*2-1)])
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N, K = [int(x) for x in input().split()]
    S = input().strip()

    count, right, ans = 0, 1, 0
    if S[0] == '0':
        count += 1
    for i, v in enumerate(S):
        if i != 0 and S[i - 1] == '0' and S[i] == '1':
            count -= 1
        while count <= K and right < len(S):
            ans = max(ans, right - i)
            if S[right - 1] == '1' and S[right] == '0':
                count += 1
            right += 1
        if count <= K:
            ans = max(ans, right - i)

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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:
import sys
input = sys.stdin.readline

def main():
    N, K = [int(x) for x in input().split()]
    S = input().strip()
    ans = []
    prev = '0'
    if S[0] == '1':
        ans.append(0)
        prev = '1'

    count = 0
    for s in S:
        if s == prev:
            count += 1
        else:
            prev = s
            ans.append(count)
            count = 1
    ans.append(count)

    ans2 = 0
    tmp = 0
    count = 0
    r = 0
    l = 0
    if ans[0] == 0:
        l = 2
    for i, v in enumerate(ans):
        r = i
        if v == 0:
            continue
        tmp += v
        if count == K:
            break
        if not i & 1:
            count += 1

    ans2 = max(tmp, ans2)

    while r <= len(ans) - 2:
        if l == 0:
            tmp -= ans[0]
        else:
            tmp -= ans[l]
            tmp -= ans[l - 1]

        l += 2
        r += 2
        if not len(ans) - 1 < r:
            tmp += ans[r]
        tmp += ans[r - 1]

        ans2 = max(tmp, ans2)

    print(ans2)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=0
history=[0]*(2*K+1)
sum_recent=0
idx=0
c=1
for i in range(1,N+1):
    #print(ans,sum_recent,history,idx,c)
    if i<N and S[i]==S[i-1]:
        c+=1
        continue
    sum_recent=sum_recent+c-history[idx]
    history[idx]=c
    idx=(idx+1)%(2*K+1)
    c=1
    if S[i-1]=='1':
        ans=max(ans,sum_recent)
    elif i==N:
        sum_recent-=history[idx]
        ans=max(ans,sum_recent)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def run_length(data, init):
    tmp = init
    cnt = 0
    length = []
    for c in data:
        if tmp != c:
            length.append(cnt)
            cnt = 0
        tmp = c
        cnt += 1
    length.append(cnt)
    return length

n,k = map(int, input().split())
s = input()
length = run_length(s, '')
if s[0] == '0':
    acc = [0] + list(accumulate(length))
else :
    acc = list(accumulate(length))
acc.append(acc[-1])

ans = acc[0]
if k * 2 + 1 > len(acc)-2:
    k = (len(acc)-2) // 2
# print(k)
for i in range(0, n, 2):
    # print(i)
    if i + k * 2 + 1 >= len(acc):
        break
    if ans < acc[i + k * 2 + 1] - acc[i]:
        ans = acc[i + k * 2 + 1] - acc[i]
print(ans)
# print(acc)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,K=map(int,input().split())
S=list(map(int,list(input())))

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

ans=0
if S[0]==0:
    l=[0]+l

if len(l)%2==0: #エラー回避の長さ調整
    l.append(0)

tgt=sum(l[:2*K+1])
ans=max(ans,tgt)

#lは1から始まることが前提
for i in range(0,len(l)-(2*K+1))[::2]:
    tgt-=l[i]
    tgt-=l[i+1]
    tgt+=l[2*K+1+i]
    tgt+=l[2*K+2+i]
    ans=max(ans,tgt)
    
#print(l)    
print(ans)

Submission status: Accepted

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

l = []
l.append(0)
ans = 0
before = ""
count = 0
if sl[0] == "0":
   l.append(0)
for idx,s in enumerate(sl):
   if s != before:
      before = s
      if idx > 0:
         l.append(idx)
         if len(l) == 2*k + 2:
            ans = max(l[-1] - l[0], ans)
            l.pop(0)
            l.pop(0)
l.append(n)
ans = max(l[-1] - l[0], ans)
print(ans)

Submission status: Accepted

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

A=[]
cnt=1

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

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

nn=len(A)

if 2*k+1>=nn:
  print(sum(A))
  exit(0)

B=[0]*nn
B[0]=A[0]
for i in range(nn-1):
  B[i+1]=B[i]+A[i+1]
ans=sum(A[:2*k+1])

for i in range(1,nn-2*k-1,2):
  ans=max(ans,B[i+2*k+1]-B[i])
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

N,K = map(int,input().split())
S = input()
cntS = []
sum_num = 0
for key, elems in groupby(S):
  num = len(list(elems))
  sum_num += num
  cntS.append([key,num,sum_num])
len_cntS = len(cntS)  

cnt0 = []
for i in range(len_cntS):
  key, num, sum_num = cntS[i]
  if key == '0':
    cnt0.append([i,num,sum_num])
  i += 1
  
if len(cnt0) <=K:
  print(N)
else:
  len_cnt0 = len(cnt0)
  ans = -float('inf')
  for i in range(-1,len_cnt0-K):
    if i == -1:
      tmp_ans = cnt0[i+K][2]
      if cnt0[i+K][0]+1 < len_cntS:
        tmp_ans += cntS[cnt0[i+K][0]+1][1]
    else:
      tmp_ans = cnt0[i+K][2]-cnt0[i][2]
      if cnt0[i+K][0]+1 < len_cntS:
        tmp_ans += cntS[cnt0[i+K][0]+1][1]
    ans = max(ans,tmp_ans)
    #print(i,i+K,ans)
  print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

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

if N == 1:
    print(1)
    exit()

# nums[i]: iが偶数なら1の個数 奇数なら0の個数
nums = []
if S[0] == "0":
    nums.append(0)
left = 0
while left < N:
    right = left
    while right < N and S[right] == S[left]:
        right += 1
    nums.append(right - left)
    left = right
if S[-1] == "0":
    nums.append(0)

from itertools import accumulate
# 累積和(1-indexed)
nums = [0] + list(accumulate(nums))

answer = 0
for left in range(0,len(nums),2):
    right = min(len(nums)-1, left + 2*K+1)
    answer = max(answer, nums[right] - nums[left])

print(answer)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate
from operator import sub
N, K = map(int, input().split())
S = input()
A = list(map(lambda p: (p[0], len(list(p[1]))), groupby(S, lambda s: s=="1")))
M = len([() for t,_ in A if not t])
B = [0] + list(accumulate(l for _,l in A))
R = B[K * 2 + int(A[0][0])::2] + ([] if A[-1][0] else [B[-1]])
L = ([] if A[0][0] else [B[0]]) + B[int(not A[0][0])::2]
print(max(map(sub, R, L)) if M > K else len(S))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
zeros = []
ones = []
i = 0
if S[0] == '0':
    ones.append(0)
while i < N:
    count = 1
    j = i + 1
    while j < N:
        if S[i] == S[j]:
            count += 1
            j += 1
        else:
            break
    if S[i] == '0':
        zeros.append(count)
    else:
        ones.append(count)
    i = j
if S[-1] == '0':
    ones.append(0)

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

sum_zero = 0
sum_one = 0
for i in range(K):
    sum_zero += zeros[i]
    sum_one += ones[i]
sum_one += ones[K]

ans = sum_zero + sum_one
for i in range(len(zeros) - K):
    sum_zero = sum_zero - zeros[i] + zeros[i+K]
    sum_one = sum_one - ones[i] + ones[i+K+1]
    ans = max(ans, sum_zero + sum_one)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import groupby
    from collections import deque
    N, K = (int(i) for i in input().split())
    S = input()
    ans = 0
    cur_0 = 0
    cur_sum = 0
    que = deque()
    for k, g in groupby(S):
        len_g = len(list(g))
        # print(k, len(list(g)))
        if k == "0":
            cur_0 += 1
            cur_sum += len_g
            que.append((0, len_g))
        else:
            cur_sum += len_g
            que.append((1, len_g))

        if K < cur_0:
            cur_0 -= 1
            key, val = que.popleft()
            while key != 0:
                cur_sum -= val
                key, val = que.popleft()
            cur_sum -= val
        ans = max(ans, cur_sum)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)

directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])


def acinput():
    return list(map(int, input().split(" ")))


sys.setrecursionlimit(100000)


directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
directions = list(map(np.array, directions))


def acinput():
    return list(map(int, input().split(" ")))


N, K = acinput()
s = list(map(int, list(input())))

nums = [1]
for i in range(1, N):
    if s[i] == s[i-1]:
        nums[-1] += 1
    else:
        nums.append(1)

if s[0] != 1:
    nums.insert(0, 0)
nums_cs = np.cumsum(nums)

res = nums_cs[min(len(nums_cs)-1,2*K)]
# if len(nums_cs) > 1:
#     res = nums_cs[min(len(nums_cs)-1, 2*K-1)]
# else:
#     res = nums_cs[0]

for i in range(1,len(nums_cs)-2*K+1):
    if i % 2 == 0:
        #print(i)
        res = max(res, nums_cs[min(i+2*K,len(nums_cs)-1)]-nums_cs[i-1])


print(res)

Submission status: Accepted

Solution code:
N,K=[int(s) for s in input().split()]
S=input()
ls=[]
if S[0]=='0':
  ls.append([0,0])
else:
  start=0
i=1
while True:
  if i>=N:
    if S[N-1]=='0':
      ls.append([N,N])
    else:
      ls.append([start,N])
    break
  if S[i-1]=='0' and S[i]=='1':
    start=i
  if S[i-1]=='1' and S[i]=='0':
    goal=i
    ls.append([start,goal])
  i+=1
if K>=len(ls)-1:
  print(N)
else:
  ls2=[ls[i+K][1]-ls[i][0] for i in range(len(ls)-K)]
  print(max(ls2))

Submission status: Accepted

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

if '1' not in S or '0' not in S:
    print(N)
    exit()

ans = 0
l = 0
r = S.index('0')
k = 0
while r < N:
    while r < N and k < K:
        while r < N and S[r] == '0':
            r += 1
        while r < N and S[r] == '1':
            r += 1
        k += 1
    ans = max(ans, r - l)
    k -= 1
    while l < N and S[l] == '1':
        l += 1
    while l < N and S[l] == '0':
        l += 1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, K = map(int, input().split())
    S = input()
    
    cur = S[0]
    start = [0]
    end = []
    for i, char in enumerate(S):
        if cur == '0' and char == '1':
            start.append(i)
        elif cur == '1' and char == '0':
            end.append(i)
        cur = char
    end.append(len(S))
    
    ans = 0
    for s, e in zip(start, end[K+int(S[0])-1:]):
        ans = max(ans, e - s)
    if ans == 0:
        ans = len(S)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

#K=1
#S="01100"
#N=len(S)

LIST=[[[0] for j in range (2)]for i in range(N)]

t=S[0]
c=0
k=0
for i in range(N):
    if(t!=S[i]):
        LIST[k][0]=c
        LIST[k][1]=t
        t=S[i]
        k+=1
        c=0
    c+=1

LIST[k][0]=c
LIST[k][1]=t
LIST=LIST[0:k+1]
MAX=0

s=0
l=0
r=0

if(LIST[r][1]=="1"):
    s+=LIST[r][0]
    r+=1
x=0
while(K>0 and len(LIST)>r):
    s+=LIST[r][0]
    K-=1
    if(len(LIST)-1==r):
        x=1
        break
    r+=1
    s+=LIST[r][0]
    if(len(LIST)-1==r):
        x=1
        break
    r+=1

MAX=max(s,MAX)

f=0
if(x==0):
    while(r<len(LIST)):
        if(l< len(LIST)-1):
            s-=LIST[l][0]
            l+=1
            f=1
        if(l<len(LIST)-1 and LIST[l][1]=="0"):
            s-=LIST[l][0]
            l+=1

        if(f==0):
            break
        

        s+=LIST[r][0]
        MAX=max(s,MAX)
        r+=1
        if(len(LIST)==r):
            break
        
        s+=LIST[r][0]
        MAX=max(s,MAX)
        r+=1
        if(len(LIST)==r):
            break

print(MAX)

Submission status: Accepted

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

ans = []
ansmax = 0
if K>=len(ls0):
    ansmax = len(s)
else:
    ans.append(sum(ls0[0:K])+sum(ls1[0:K+1]))
    for i in range(1,len(ls0)-K+1):
        ans.append(ans[-1]+ls0[i+K-1]+ls1[i+K]-ls0[i-1]-ls1[i-1])
    else:
        ansmax = max(ans)
print(ansmax)