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()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


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

    """
    chokudaiさんのコードも尺取りで写経してみる！
    """

    A = []
    char = 1 # 必ず１から始まるようにするのかなるほど。。。
    cnt = 0
    for i in range(N):
        if S[i] == str(char):
            cnt += 1
        else:
            A.append(cnt)
            char = 1 - char
            cnt = 1
    if cnt != 0: A.append(cnt)
    if len(A) % 2 == 0: A.append(0)
    #print(A)

    """
    この時点でA = [(1の個数), (0の個数), (1の個数), (0の個数),...,(1の個数)]
    のように並んでいるので、Sの先頭が0か1かの場合分けが不要になるし、
    以降の尺取りは(1の個数)のところから常にカウントを始めて良い。
    """

    add = K * 2 + 1
    ans = 0
    left = 0
    right = 0
    tmp = 0 # [left, right)の値

    i = 0
    l = len(A)
    while i < l:
        nextLeft = i
        nextRight = min(i + add, l)
        while nextLeft > left:
            tmp -= A[left]
            left += 1
        while nextRight > right:
            tmp += A[right]
            right += 1
        ans = max(ans, tmp)
        i += 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


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

    """
    反転させる区間は独立であるとしてよい。実際反転させる２区間が左図のように
    オーバーラップしていたとすると、これは右図のように反転させるのと同値だからである：
               _______________                             _______  
        ______|_______        |     --->    ______        |       |
    ___|______|_______|_______|_____    ___|______|_______|_______|_____ 
    
    そうすると安直には0がなるべく長く連続している区間に反転をかけたくなるが、
    長い順に反転をかけた場合1が連続する保証がないのでダメ。

    そこで1の連続する箇所を固定したうえで、そこから0の連続する区間に順番に反転をかけることを考える。
    当然愚直にやるとTLEなので、累積和で実装する
    """

    A = []
    char = S[0]
    cnt = 1
    for i in range(1, N):
        if S[i] == char:
            cnt += 1
        else:
            A.append(cnt)
            char = S[i]
            cnt = 1
    A.append(cnt)
    #print("A={}".format(A))

    B = list(accumulate(A))
    B.append(B[-1])
    #print("B={}".format(B))
    l = len(A)
    if S[0] == '0':
        ans = B[min(K * 2 - 1, l - 1)]
        for i in range(1, l - K * 2 + 1):
            if i % 2 == 0:
                j = i + K * 2 - 1
                val = B[j] - B[i - 1]
            else:
                j = i + K * 2
                val = B[j] - B[i - 1]
            #print("[{}, {}]->val={}".format(i, j, val))
            ans = max(ans, val)
    else:
        ans = B[min(K * 2, l - 1)]
        for i in range(1, l - K * 2 + 1):
            if i % 2 == 1:
                j = i + K * 2 - 1
                val = B[j] - B[i - 1]
            else:
                j = i + K * 2
                val = B[j] - B[i - 1]
            #print("[{}, {}]->val={}".format(i, j, val))
            ans = max(ans, val)
    print(ans)
       


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N, K = map(int, input().split())
S = input()
flg = int(S[0])
gr = itertools.groupby(S)
ans, tmp = 0, 0
check_0, check_1 = [], []
for key, group in gr:
    target = len(list(group))
    tmp += target
    if key == '1':
        check_1.append(target)
    else:
        check_0.append(target)
    if key == '0':
        if len(check_0) > K:
                tmp -= check_0[len(check_0)-(K+1)]
        if len(check_1) > K:
                tmp -= check_1[len(check_1)-(K+1)]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s01=[[1,s[0]]]
for i in range(1,n):
  if s[i]==s[i-1]:
    s01[-1][0]+=1
  else:
    s01.append([1,s[i]])
a=len([i0 for i0,i1 in s01 if i1=='0'])
if a<=k:
  print(n)
  exit()
# 累計和
si=0
sums=[0]
for s01i in s01:
  si+=s01i[0]
  sums.append(si)
ans=0
#print(s01)
#print(sums)
l=0 if s[0]=='0' else 1
for i in range(l,len(s01),2):
  l=max(0,i-1)
  r=min(len(sums)-1,2*k+i)
  #print(sums[r]-sums[l],i,l,r)
  ans=max(ans,sums[r]-sums[l])
print(ans)

Submission status: Accepted

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

if(S[0] == "1"):
    s = []
else:
    s = [0]
cnt = 1
tmp = S[0]
for i in range(1, len(S)):
    if(tmp == S[i]):
        cnt += 1
    else:
        s.append(cnt)
        tmp = S[i]
        cnt = 1
s.append(cnt)
tmp1 = 0
if(len(s)//2 <= K):
    ans = sum(s)        
else:
    ans = sum(s[:(2*K+1)])
    tmp = ans
    cnt = 0
    for i in range(2*K+1, len(s)-1, 2):
        if(ans < tmp-s[cnt]-s[cnt+1]+s[i]+s[i+1]):
            ans = tmp-s[cnt]-s[cnt+1]+s[i]+s[i+1]
            tmp = tmp-s[cnt]-s[cnt+1]+s[i]+s[i+1]
        else:
            tmp = tmp-s[cnt]-s[cnt+1]+s[i]+s[i+1]
        cnt += 2
    ss = s[::-1]
    if(S[-1] == "0"):
        tmp1 = sum(ss[:(2*K)])
    else:
        tmp1 = sum(ss[:(2*K+1)])
print(max(ans, tmp1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

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

len_list = []
ind = 0
if S[0] == '0':
    #len_list[0] = 0
    len_list.append(0)
    #ind += 1

cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        #len_list[ind] = cnt
        len_list.append(cnt)
        #ind += 1
        cnt = 1
    else:
        cnt += 1
#len_list[ind] = cnt
len_list.append(cnt)

l_list = len(len_list)
wa = [0] + list(accumulate(len_list))
ans = 0
i = 1
l_wa = len(wa)
while True:
    if i+2*K >= l_wa:
        ans = max(ans, wa[l_wa-1] - wa[i-1]) 
        break
    #if i == 0:
        #ans = wa[i+2*K+1]
    ans = max(ans, wa[i+2*K] - wa[i-1]) 
    i += 2
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

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

len_list = [0]*(2*(10**5)+100)
ind = 0
if S[0] == '0':
    len_list[0] = 0
    ind += 1

cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        len_list[ind] = cnt
        ind += 1
        cnt = 1
    else:
        cnt += 1
len_list[ind] = cnt

#print(len_list[:30])
i = 0
wa = 0
sum_l = sum(len_list[:2*K+1])
while True:
    if len_list[i+2*K+1] != 0:
        wa = max(wa, sum_l)
    else:
        wa = max(wa, sum_l)
        break
    sum_l -= (len_list[i] + len_list[i+1])
    sum_l += (len_list[i+2*K+1] + len_list[i+2*K+2])
    i += 2
print(wa)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
S = input()
inds = [[0, 0]]

flag = 0
s = 0
for i in range(N):
    if S[i] == '0':
        if not flag:
            flag = 1
            inds.append([s, i-1])
    else:
        if flag:
            s = i
        flag = 0
if flag:
    inds.append([N-1, N-1])
if not flag:
    inds.append([s, N-1])
#print(inds)
l_inds = len(inds)
wa = 0
if K >= l_inds-1:
    print(N)
    exit()
for i in range(l_inds-K):
    wa = max(inds[i+K][1] - inds[i][0] + 1, wa)

print(wa)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
l = x = ans = 0
for r in range(n):
    if s[r] == '0' :
        if r == 0 or s[r-1] == '1':
            x += 1
    if x > k:
        while s[l] == '1':
            l += 1
        while s[l] == '0':
            l += 1
        x -= 1
    ans = max(ans,r-l+1)
print(ans)

Submission status: Accepted

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

#print(s1)

# s1の累積和
s2 = [0]*(len(s1)+1)
s2[1] = s1[0]
for i in range(1, len(s1)):
    s2[i+1] = s1[i] + s2[i]
#print(s2)

ans = 0
if len(s2) > 2*k+1:
    for l in range(len(s2)-(2*k+1))[::2]:
        res = s2[2*k+1+l] - s2[l]
        ans = max(ans, res)
else:
    ans = s2[-1]
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = input()
l = []
if a[0] == '0':
    l.append(0)
sum = []
i = 0
while i < len(a):
    j = i
    while j < len(a) and a[j] == a[i]:
        j += 1
    l.append(j-i)
    i = j
if a[-1] == '0':
    l.append(0)
num = [0]*(len(l)+1)
for i in range(0, len(l)):
    num[i+1] = num[i]+l[i]
ans = -1
for i in range(0, len(num), 2):
    j = i + k*2+1
    if j >= len(num):
        j = len(num)-1
    ans = max(ans, num[j] - num[i])
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,K=map(int,input().split())
S=input()
gr=itertools.groupby(S)
li=[] if S[0]=='1' else [0]
for key,group in gr:
    li.append(len(list(group)))
res=0
cum=[0]*(len(li)+1)
for i in range(len(li)):
    cum[i+1]=cum[i]+li[i]
for i in range(0,len(li),2):
    r=i+2*K+1
    if r>=len(cum):
        r=len(cum)-1
    res=max(res,cum[r]-cum[i])
print(res)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
t=1
l=[0]
for i in s:
  i=int(i)
  if i==t: l[-1]+=1
  else: l+=[1]; t=i
if t<1: l+=[0]
s=[0]
for i in l: s+=[s[-1]+i]
a=0
for i in range(0,len(l),2):
  if i<2*k: a=max(a,s[i+1])
  else: a=max(a,s[i+1]-s[i-k*2])
print(a)

Submission status: Accepted

Solution code:
from itertools import*
n, k = map(int, input().split())
s = input()
d = [len(list(t)) for _, t in groupby(s)]
if s[0] == "0":
    d = [0] + d
a = [0] + list(accumulate(d))
m = l = 0
while True:
  try:
    m = max(m, a[l+2*k+1] - a[l])
    l += 2
  except IndexError:
    m = max(m, a[-1] - a[l])
    break
print(m)

Submission status: Accepted

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

zero_index_left = []
flag = False
for i in range(N):
    if flag is False and S[i] == "0":
        zero_index_left.append(i)
        flag = True
    elif S[i] == "1":
        flag = False

if K >= len(zero_index_left):
    print(N)
    exit()
    
zero_index_right = []
S = S[:: -1]
flag = False
for i in range(N):
    if flag is False and S[i] == "0":
        zero_index_right.append(i)
        flag = True
    elif S[i] == "1":
        flag = False
        
ans = 0
for i in range(len(zero_index_left) - K):
    if i == 0:
        ans = max(ans, zero_index_left[i + K])
        ans = max(ans, zero_index_right[i + K])
    else:
        ans = max(ans, zero_index_left[i + K] - N + 1 + zero_index_right[-i] - 1)
        ans = max(ans, zero_index_right[i + K] - N + 1 + zero_index_left[-i] - 1)
print(ans)

Submission status: Accepted

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

    cnt = 0
    buf = '1'
    for ele in s:
        if ele != buf:
            ls.append(cnt)
            cnt = 1
            buf = ele
        else:
            cnt += 1
    ls.append(cnt)

    if buf == '0':
          ls.append(0)

    w = 2*k+1
    if w >= len(ls):
          print(n)
    else:
          acc = [0] + list(accumulate(ls))
          ans = 0
          for i in range(0,len(ls)-w+1,2):
               ans = max(ans,acc[i+w]-acc[i])
          print(ans)

main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
l=[]
if s[0]=="0":
  l.append(0)

from itertools import groupby,accumulate
gr=groupby(s)

for K,g in gr:
  l.append(len(list(g)))

l_sum=list(accumulate(l))
l_sum=[0]+l_sum

add=2*k+1
ans=0
for i in range(0,len(l)+1,2):
  left=i
  right=min(i+add,len(l))
  tmp=l_sum[right]-l_sum[left]
  ans=max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

l=len(count)
count=list(accumulate(count))
ans=0
for i in range(0,l,2):
    ans=max(ans,count[min(l-1,i+2*K+1)]-count[i])
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=list(map(int,input()))
c1=[]
c0=[]
count=0
if S[0]==0:
    c1.append(0)
for i in range(N-1):
    count=count+1
    if S[i]!=S[i+1]:
        if S[i]==1:
            c1.append(count)
        else:
            c0.append(count)
        count=0
count=count+1
if S[N-1]==1:
    c1.append(count)
else:
    c0.append(count)
    c1.append(0)
if len(c0)<=K:
    print(N)
else:
    ans0=sum(c0[:K])
    ans1=sum(c1[:K+1])
    ans=ans0+ans1
    for i in range(len(c0)-K):
        ans0=ans0-c0[i]+c0[i+K]
        ans1=ans1-c1[i]+c1[i+K+1]
        ans=max(ans,ans0+ans1)
    print(ans)

Submission status: Accepted

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

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

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

mil = min(l, 2 * k + 1)

ans = 1
for i in range(0, l - mil + 1, 2):
    ans = max(ans, su[mil + i] - su[i])
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
lis = [0]
j = 0
if s[0] == '0':
    lis.append(0)
    j = 1
#print(len(lis))
lis[j] += 1
for i in range(1,n):
    #print(len(lis))
    if s[i] != s[i-1]:
        j += 1
        lis.append(0)
    lis[j] += 1
if s[n-1] == '0':
    lis.append(0)
#print(lis)
com = [0] * (len(lis) + 1)
for i in range(len(lis)):
    com[i+1] = com[i] + lis[i]
#print(com)
ans = 0
for i in range(len(lis)):
    if i % 2 == 0:
        ans = max(ans,lis[i])
l = 0
while l < len(com):
    r = l + (2 * k + 1)
    if r >= len(com):
        r = len(com) - 1
    ans = max(ans,com[r] - com[l])
    l += 2
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
s = [i for i in input()]
zero_one = [0]
if s[0] == "0":
    zero_one.append(0)
s_ = s[0]
cnt = 0
for i in range(n):
    if s_ == s[i]:
        cnt += 1
    else:
        zero_one.append(cnt)
        cnt = 1
        s_ = s[i]
zero_one.append(cnt)
if s[-1] == "0":
    zero_one.append(0)
ans = 0
l = len(zero_one)
zero_one = list(accumulate(zero_one))
for i in range(0, l, 2):
    ans = max(ans, zero_one[min(l-1, i+2*k+1)] - zero_one[i])
print(ans)

Submission status: Accepted

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

nums = []
cnt = 1
if S[0] == "0":
  nums.append(0)
for i in range(N):
  if i == N-1 or S[i] != S[i+1]:
    nums.append(cnt)
    cnt = 1
  else:
    cnt += 1
if S[-1] == "0":
  nums.append(0)

Sum = [0]*(len(nums)+1)
for i in range(1, len(nums)+1):
  Sum[i] = Sum[i-1] + nums[i-1]

ans = 0
if len(nums) <= 2*K+1:
  ans = N
else:
  for i in range(0, len(nums) - 2*K+1, 2):
    ans = max(ans, Sum[i+2*K+1] - Sum[i])

print(ans)

Submission status: Accepted

Solution code:
# Handstand

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

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

tsum = [0]*(len(t)+1)
for i in range(len(t)):
    tsum[i+1] = tsum[i] + t[i]

#print(tsum)

ans = 0
for i in range(1+int(s[0])%2, len(tsum)-2*k,2):
    tmp = tsum[i+2*k] - tsum[i-1]
    #print(tmp)
    ans = max(ans, tmp)

if ans==0:
    ans = len(s)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

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

    cumsum = [0 for _ in range(len(counts) + 1)]
    for i in range(0, len(counts)):
        cumsum[i + 1] = cumsum[i] + counts[i]

    res = 0
    for left in range(0, len(cumsum), 2):
        right = left + 2 * K + 1
        if right >= len(cumsum):
            right = len(cumsum) - 1
        res = max(res, cumsum[right] - cumsum[left])

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
a = []
c = 1
for i in range(n-1):
    if s[i]==s[i+1]:
        c+=1
    else:
        a.append(c)
        c = 1
a.append(c)
b = [0]
for i in range(len(a)):
    b.append(b[-1]+a[i])
b.append(b[-1])
n = len(b)
l = 2*k+1
st=int(s[0])
ans = 0
for i in range(st,n,2):
    ans = max(ans,b[i]-b[max(0,i-l)])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

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

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

C = [0] * (len(nums)+1)
for i in range(len(nums)):
    C[i+1] = C[i] + nums[i]

ans = 0
m = 2 * K + 1
for i in range(0, max(len(nums)-m+1, 1), 2):
    m = min(m, len(nums))
    ans = max(ans, C[i+m] - C[i])

if len(nums) != 1:
    print(ans)
else:
    print(nums[0])

Submission status: Accepted

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

Submission status: Accepted

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

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

if s[0] == "0":
    al = [0] + al
if s[-1] == "0":
    al = al + [0]
    
nn = len(al)
nagasa = min(2*k+1,nn)
r = (nn-nagasa) // 2

ans = sum(al[:nagasa])
cur = sum(al[:nagasa])
for i in range(1,r+1):
    cur = cur + (al[nagasa+i*2-1] + al[nagasa+i*2-2]) -(al[i*2-1] + al[i*2-2])
    ans = max(cur,ans)
    
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().strip().split())
s=input().strip()
l=r=0
c=0
while r<n and s[r]=='1': r+=1
while c<k:
 while r<n and s[r]=='0':r+=1
 while r<n and s[r]=='1':r+=1
 if r==n:print(n);exit()
 c+=1
ans=r-l
while r<n:
 while l<n and s[l]=='1':l+=1
 while l<n and s[l]=='0':l+=1 
 while r<n and s[r]=='0':r+=1
 while r<n and s[r]=='1':r+=1
 ans=max(ans,r-l)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
L = []
R = []
maximum = 0
if S[0] == "0":
    L.append(0)
if S[N-1] == "0":
    R.append(N-1)
for n in range(N-1):
    if S[n] == "1" and S[n+1] == "0":
        L.append(n+1)
    if S[-n-1] == "1" and S[-n-2] == "0":
        R.append(N-n-2)
L.append(N)
R.append(-1)
R.reverse()
if len(L) <= K:
    print(N)
else:
    for n in range(len(L)-K):
        maximum = max(maximum, L[n+K]-R[n]-1)
    print(maximum)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
tmp1 = 0
tmp1_list = []
tmp2 = 0
tmp2_list = []
cnt0 = 0
flag = 0

for i in range(n):
    if flag == 0:
        if s[i] == "0":
            cnt0 += 1
            flag = 1
            tmp1 += 1
            tmp2 += 1
        else:
            tmp1 += 1
            tmp2 += 1
    else:
        if s[i] == "1":
            tmp1_list.append(tmp1)
            tmp1 = 1
            tmp2 += 1
            flag = 0
        else:
            tmp1 += 1
            tmp2 += 1
    if cnt0 == k + 1:
        tmp2_list.append(tmp2 - 1)
        tmp2 -= tmp1_list.pop(0)
        cnt0 -= 1
    if i == n - 1:
        tmp2_list.append(tmp2)

print(max(tmp2_list))

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,K = inputlist()
S = list(input())
li = []
s = S[0]
for i in range(1,N):
    if S[i] == S[i-1]:
        s += S[i]
    else:
        li.append(s)
        s = S[i]
li.append(s)
n = len(li)
dic = {}
indexa = 0
ans = 0
ksum = [0]*n
ksum[0] = len(li[0])
for i in range(1,n):
    ksum[i] = ksum[i-1]+len(li[i])
for i in range(n):
    if li[i][0] == '0':
        indexa +=1
        dic[indexa] = i
if indexa <= K:
    print(N)
    exit()
if K == 1:
    for i in range(1,indexa+1):
        j = dic[i]
        if i == 1:
            m = ksum[j+1]
            ans = max(ans,m)
            continue
        if j == n-1:
            m = ksum[j]-ksum[j-2]
            ans = max(ans,m)
            continue
        else:
            m = ksum[j+1]-ksum[j]+1
            m += ksum[j-1]-ksum[j-2]
            ans = max(m,ans)
else:
    for i in range(K,indexa+1):
        j = dic[i]
        l = dic[i-K+1]
        sup = 0
        inf = 0
        if j == n-1:
            sup = ksum[j]
        if j != n-1:
            sup = ksum[j+1]
        if l != 0:
            inf = ksum[l-2]
        m = sup-inf
        ans = max(ans,m)
print(ans)

Submission status: Accepted

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i //= 2
    return

def get_sum(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans += tree[s]
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans += tree[t]
            t = (t - 1) // 2
    return ans

n, k = map(int, input().split())
s = list(input())
t = []
if s[0] == "0":
    t.append(0)
u = s[0]
c = 0
for i in s:
    if i == u:
        c += 1
    else:
        t.append(c)
        u = i
        c = 1
t.append(c)
if s[n - 1] == "0":
    t.append(0)
lt = len(t)
tree = make_tree(lt)
for i in range(lt):
    update(i, t[i])
k = 2 * k + 1
ans = 0
if lt - k > 0:
    for i in range((lt - k) // 2 + 1):
        ans = max(ans, get_sum(2 * i, 2 * (i + (k - 1) // 2)))
else:
    ans = n
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

memo = np.zeros(10**5+1, dtype = np.int64)
W = min(2*K, 10**5)

current = 1 # 最初は1が0個ある
p = 0

for x in S:
  if x == current:
    memo[p] += 1
  else:
    current = 1 - current
    p += 1
    memo[p] += 1

ans = memo[:W+1].sum()
x = ans
for r in range(2,10**5+1,2):
  if r+W > 10**5:
    break
  x = x-memo[r-2]-memo[r-1]+memo[r+W]+memo[r+W-1]
  if x > ans:
    ans = x

print(ans)

Submission status: Accepted

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

L = []
cur = s[0]
cnt = 0
for i in range(n):
    if s[i] == cur:
        cnt += 1
    else:
        L.append((cnt, int(cur)))
        cnt = 1
        cur = s[i]
else:
    L.append((cnt, int(cur)))

#print(L)

t = 0
S = 0
C = 0
ans = 0
for s in range(len(L)):
    while C <= k and t < len(L):
        if C == k and L[t][1] == 0:
            break
        S += L[t][0]
        if L[t][1] == 0:
            C += 1
        t += 1
    #print(S, C)
    ans = max(ans, S)
    if s == t:
        t += 1
    else:
        S -= L[s][0]
        if L[s][1] == 0:
            C -= 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
S = input()
s = []
if S[0]=='0':s = [0]
for x in S.replace('01', '0,1').replace('10','1,0').split(','):
    s.append(len(x))
M = len(s)
ans = [0] * M
ans[0] = sum(s[:2*K+1])

for i in range(2, M, 2):
    ans[i] = ans[i-2] - s[i-2] - s[i-1] + sum(s[min(i+2*K-1,M):i+2*K+1])
print(max(ans))

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  import numpy as np
  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0.append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0.append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1.append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0.append(c0)
    chk_1.append(0)
  elif c1 != 0:
    chk_1.append(c1)
    chk_0.append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  ab = np.array([x+y for x,y in zip(chk_0,chk_1)])
  np.cumsum(ab,out=ab)

  ans = ab[k-1]
  for i in range(len(ab)-k):
    chk = ab[k+i]-ab[i]
    chk += chk_1[i]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  import numpy as np

  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  chk_0_append = chk_0.append
  chk_1_append = chk_1.append
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0_append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0_append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1_append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0_append(c0)
    chk_1_append(0)
  elif c1 != 0:
    chk_1_append(c1)
    chk_0_append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  chk_1 = tuple(chk_1)
  chk_0 = tuple(chk_0)
  ab = np.array([x+y for x,y in zip(chk_0,chk_1)])
  np.cumsum(ab,out=ab)
  ab = tuple(ab)
  #print(ab)
  ans = ab[k-1]
  for i in range(len(ab)-k):
    chk = ab[k+i]-ab[i]
    chk += chk_1[i]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections
import bisect

input = sys.stdin.readline

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

zerocnt = collections.Counter()
zeroindex = [-1] * N
onecnt = collections.Counter()
oneindex = [-1] * N

zh = oh = None
for i, x in enumerate(S):
    if x == "0":
        if i == 0 or S[i - 1] == "1":
            zh = i
    else:
        if i == 0 or S[i - 1] == "0":
            oh = i
    if zh is not None:
        zeroindex[i] = zh
        zerocnt[zh] += x == "0"
    if oh is not None:
        oneindex[i] = oh
        onecnt[oh] += x == "1"

zerolist = sorted(zerocnt.keys()) + [N]
onelist = sorted(onecnt.keys())


def solve():
    maxval = -1
    maxrange = None
    for i, head in enumerate(zerolist):
        zstart = max(i - K, 0)
        start = zerolist[zstart]
        if start > 0:
            assert S[start - 1] == "1"
            start = oneindex[start - 1]
        val = head - start
        if maxval < val:
            maxval = val
            maxrange = (start, head)
    return maxval


if len(zerocnt) <= K:
    print(N)
else:
    print(solve())