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 sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

N, K = map(int, readline().split())
S = list(map(int, s_readline().strip()))


def solve():
    s_grp = itertools.groupby(S)
    zl = []
    ol = []

    llen = 0
    f = False

    for k, l in s_grp:

        l = list(l)
        if k == 0:
            llen += len(l)
            f = True
        elif k == 1:
            ol.append(len(l))
            if f:
                llen += len(l)
                zl.append(llen)
                llen = 0

    else:
        if k == 0:
            zl.append(llen)

    if S[0] == 0:
        ol = [0] + ol

    # print(zl)
    # print(ol)

    zl_N = len(zl)

    zl_tsum = [0 for _ in range(zl_N + 1)]
    for i in range(zl_N):
        zl_tsum[i + 1] = zl_tsum[i] + zl[i]

    Km = min(K, zl_N)
    ans = 0
    for i in range(zl_N - Km + 1):
        t = zl_tsum[Km + i] - zl_tsum[i] + ol[i]
        ans = max(ans, t)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
rest = k
i = 0
while i < n:
    if s[i] == '1':
        i += 1
    else:
        if rest == 0:
            break
        rest -= 1
        while i < n and s[i] == '0':
            i += 1
ans = i
j = 0
while i < n:
    while i < n and s[i] == '0':
        i += 1
    while i < n and s[i] == '1':
        i += 1
    while j < n and s[j] == '1':
        j += 1
    while j < n and s[j] == '0':
        j += 1
    ans = max(ans, i - j)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
if N==1:
 print(1)
else:
 lst=[]
 ct=1
 if int(S[0])==0:
  lst.append(0)
 ima=int(S[0])
 for i in range(1,N):
  if int(S[i])==ima:
   ct+=1
  else:
   lst.append(ct)
   ima=int(S[i])
   ct=1
 lst.append(ct)
 if ima==0:
  lst.append(0)
 A=len(lst)-2
 if A<=K*2-1:
  print(N)
 else:
  for i in range(1,len(lst)):
   lst[i]+=lst[i-1]
  ans=0
  for i in range((len(lst)-1-2*K)//2+1):
   if i==0:
    ans=max(ans,lst[2*i+2*K])
   else:
    ans=max(ans,lst[2*i+2*K]-lst[2*i-1])
  print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(str(input()))
arr = [0,0]
D = [0,0]
cnt = 0
d = 0

for i in range(len(S)):
  a = int( S[i] )
  if a == 1:
    cnt += 1 + d
    if d > 0:
      D.append(d)
    d = 0
  elif a == 0 and d == 0:
    arr.append(cnt)
    d += 1
  else:
    d += 1
if a == 1:
  arr.append(cnt)
if a == 0:
  arr.append(cnt+d)
arr.sort()

ans = 0
for i in range(len(arr)-K-1):
  a = arr[i+K+1] - arr[i]
  b = D[i]
  ans = max(a-b,ans)
if len(arr) <= K:
  ans =  N
print(ans)

Submission status: Accepted

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

if seq[n-1]=="0":
    seq=seq+"1"
else:
    seq=seq+"0"

l=[]

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

st=0
for i in range(n):
    if seq[i:i+2] in ("01","10"):
        l.append(i+1-st)
        st=i+1

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

if 2*k+1>=len(l):
    print(sum(l))
else:
    lis=[sum(l[0:2*k+1])]
    for i in range((len(l)-2*k-1)//2):
        lis.append(lis[i]-l[2*i]-l[2*i+1]+l[2*i+2*k+1]+l[2*i+2*k+2])
    print(max(lis))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
S = '1' + S + '1'
rev = []
for i in range(N+1):
    if S[i] != S[i+1]:
        rev.append(i)
l = len(rev)//2
a = [(rev[2*i], rev[2*i+1]) for i in range(l)]

a = [(0, 0)] + a + [(N, N)]
K = min(K, l)

m = -1
for i in range(l-K+1):
    x = a[i+K+1][0]-a[i][1]
    m = max(m, x)

print(m)

Submission status: Accepted

Solution code:
from collections import deque

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

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


if len(cnt_01) <= 2*k:
    print(n)
    exit()


if s[0] == '0':
    ans_candi = sum(cnt_01[0:2*k])
    cnt_01 = cnt_01[1:]
else:
    ans_candi = 0


first_que = cnt_01[0:2*k+1]
que = deque(first_que)
curr_sum = sum(first_que)
ans = curr_sum
for i in range(k, len(cnt_01)-1):
    break_flag = False
    poped1 = que.popleft()
    poped2 = que.popleft()
    curr_sum -= (poped1 + poped2)
    if 2*i+1 < len(cnt_01):
        que.append(cnt_01[2*i+1])
        curr_sum += cnt_01[2*i+1]
    if 2*i+2 < len(cnt_01):
        que.append(cnt_01[2*i+2])
        curr_sum += cnt_01[2*i+2]
    else:
        break_flag = True
    ans = max(curr_sum, ans)
    if break_flag: break

print(max(ans,ans_candi))

Submission status: Accepted

Solution code:
import sys

N, K = map(int, sys.stdin.readline().strip().split())
S = sys.stdin.readline().strip()

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:
# 累積和による解法
def resolve():
    N, K = list(map(int, input().split()))
    S = input()
    seq = []
    cnt = 0
    if S[0] != "1":
        seq.append(0)
    for i in range(len(S)-1):
        if S[i] != S[i+1]:
            seq.append(cnt+1)
            cnt = 0
        else:
            cnt += 1
    seq.append(cnt+1)
    if S[-1] != "1":
        seq.append(0)
    #print(seq)

    cum = [0]
    cur = 0
    for c in seq:
        cur += c
        cum.append(cur)
    #print(cum)
    
    maxlen = len(S) if len(cum) <= (2*K+1) else 0
    for i in range(0, len(cum)-(2*K+1), 2):
        l = cum[i+(2*K+1)] - cum[i]
        maxlen = max(maxlen, l)
    print(maxlen)
    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    N, K = list(map(int, input().split()))
    S = input()
    seq = []
    cnt = 0
    for i in range(len(S)):
        if i == N-1 or S[i] != S[i+1]:
            seq.append([cnt+1, S[i]])
            cnt = 0
        else:
            cnt += 1
    #print(seq)
    left = 0
    right = 0
    maxlen = 0
    val = 0
    n_rev = 0
    for left in range(0, len(seq)):
        while (right < len(seq) and (n_rev < K or seq[right][1]=="1")):
            #print("left={}, right={}, n_rev={}".format(left, right, n_rev))
            cnt, state = seq[right]
            val += cnt
            if state == "0":
                n_rev += 1
            right += 1
        maxlen = max(maxlen, val)
        cnt, state = seq[left]
        val -= cnt
        if state == "0":
            n_rev -= 1
        if left == right:
            right += 1
    print(maxlen)
    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
l = list(s)
s_list = []
count = 1
if n >=2:
  for i in range(1,n):
    if s[i] != s[i-1]:
      s_list.append(count)
      count = 1
    else:
      count += 1
    if i == n-1:
      s_list.append(count)
  sum_s = [0,s_list[0]]
  for i in range(1,len(s_list)):
    sum_s.append(sum_s[-1] + s_list[i])
  if s[0] == "1":
    result = []
    for i in range(1,len(sum_s)):
      if i % 2 == 1:
        result.append(sum_s[min(len(sum_s)-1,i+2*k)] - sum_s[i-1])
      else:
        result.append(sum_s[min(len(sum_s)-1,i+2*k-1)] - sum_s[i-1])

  else:
    result = []
    for i in range(1,len(sum_s)):
      if i % 2 == 1:
        result.append(sum_s[min(len(sum_s)-1,i+2*k-1)] - sum_s[i-1])
      else:
        result.append(sum_s[min(len(sum_s)-1,i+2*k)] - sum_s[i-1])

if n == 1:
  print(1)
else:
  print(max(result))

Submission status: Accepted

Solution code:

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

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    if f != S[i]:
        a.append(i-l)
        l = i
        f = S[i]
        

if S[0] == '0':
    a = [0] + a

SUM = sum(a[0:0+2*K+1])

MAX = max(0, SUM)
for i in range(2, len(a)):
    if i % 2 == 0:
        try:
            SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1]+a[i+2*K])
        except:
            try:
                SUM = SUM - (a[i-2]+a[i-1]) + (a[i+2*K-1])
            except:
                break
        
        MAX = max(MAX, SUM)


print(MAX)

Submission status: Accepted

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

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

m = len(cnt)
cs = [0] * (m+1)
for i in range(m):
    cs[i+1] = cs[i] + cnt[i]

ans = 0
for l in range(0, m+1, 2):
    r = l + 2 * k + 1
    if r > m: r = m
    ans = max(ans, cs[r] - cs[l])

print(ans)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
   plus=0
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
   plus=1
max_n=sum_n
for i in range(len(ans)-end+plus):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         print(max_n)
         exit()
      now=0
   max_n=max(sum_n,max_n)
print(max_n)

Submission status: Accepted

Solution code:
from operator import add
from collections import deque
from itertools import accumulate

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

if N == 1:
  if S == "1" or K >= 1:
    print(1)
  else:
    print(0)
    
else:
  num = []
  cnt = 1
  ans = 0
  M = 2 * K + 1

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

  if S[0] == "0":
    num = [0] + num
  
  acc = list(accumulate(num,add))
  acc = [0] + acc
  A = len(acc)
  
  for left in range(0,A,2):
    right = min(A - 1,left + M)
    ans = max((acc[right] - acc[left]),ans)
    
  print(ans)

Submission status: Accepted

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


L = [0]
R = []
for i, (a, b) in enumerate(zip(s, s[1:])):
    if (a, b) == ('0', '1'):
        L.append(i+1)

    if (a, b) == ('1', '0'):
        R.append(i)
else:
    R.append(n-1)

ans = R[0]-L[0]+1
if s[0] == '0':
    k -= 1
k = min(k, len(R)-1)
for l, r in zip(L, R[k:]):
    x = r-l+1
    if ans < x:
        ans = x
print(ans)

Submission status: Accepted

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

prev_R = '1'
for R in range(n):
    if (prev_R, s[R]) == ('1', '0'):
        k -= 1
        if k < 0:
            R -= 1
            break
    prev_R = s[R]

ans = R+1
for L in range(n-1):
    if (s[L], s[L+1]) != ('0', '1'):
        continue
    R += 1
    while R < n-1 and (s[R], s[R+1]) != ('1', '0'):
        R += 1
    if ans < R-L:
        ans = R-L
print(ans)

Submission status: Accepted

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

if N==1:
  U=[ [T[0],1] ]
else:
  tmp=T[0]
  cnt=1
  for i in range(1,N):
    if i==N-1:
      if T[i]==T[i-1]:
        cnt+=1
        U.append([tmp,cnt] )
      else:
        U.append([tmp,cnt] )
        U.append([T[i],1])
    else:
      if T[i]==T[i-1]:
        cnt+=1
      else:
        U.append([tmp,cnt] )
        tmp=T[i]
        cnt=1

summ=0
for j in range(len(U)):
  summ += U[j][1]
  U[j][1]=summ
if U[0][0]==0:
  U.insert(0,[1,0])
  U.insert(0,[0,0])
else:
  U.insert(0,[0,0])

#print(U)
maxi=0
  
for p,q in enumerate(U):
  if q[0]==1:
    pass
  else:
    right=min(p+K*2+1,len(U)-1)
    diff=U[right][1]-U[p][1]
    maxi=max(diff,maxi)
    #print(p,right,diff)
print(maxi)

Submission status: Accepted

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

s=list(input())

memo = [0]

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

ans = 0

kyoukai_math = len(memo)

for i in range(kyoukai_math):
  if s[memo[i]] == '1':
    hasi = i+k*2+1
  else:
    hasi = i+k*2
    
  if hasi < kyoukai_math:
    ans = max(ans,memo[hasi]-memo[i])
  else:
    ans = max(ans,n-memo[i])
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
cou = 0
p = 1
nagasa = []
for i in range(n):
    if int(s[i]) == p:
        cou += 1
    elif int(s[i]) != p:
        if p == 1:
            p = 0
        elif p == 0:
            p = 1
        nagasa.append(cou)
        cou = 1
nagasa.append(cou)
if len(nagasa) % 2 == 0:
    nagasa.append(0)
h = len(nagasa)

if h // 2 <= k:
    print(n)
    exit()
lef = 0
rig = 2*k+1
now = sum(nagasa[lef:rig])
ans = now
while True:
    if rig == h:
        break
    now = now - nagasa[lef] - nagasa[lef+1] + nagasa[rig] + nagasa[rig+1]
    ans = max(ans,now)
    lef += 2
    rig += 2
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
Nums = []
now = 1 # 今見ている数
cnt = 0 # nowがいくつ並んでいるか
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now   # 0と1を切り替えるときの計算 now ^= 1
        cnt = 1
if cnt != 0:
    Nums.append(cnt)
# 1-0-1-0-1-0-1 って感じの配列が欲しい
# 1-0-1-0-1-0 みたいに0で終わっていたら適当に1つ足す
if len(Nums) % 2 == 0:
    Nums.append(0)

Add = 2 * K + 1
ans = 0
# 尺取り法 forループの外側にleft, rightを持つ
left = 0
right = 0
tmp = 0 # [left, right)のsum
# 1-0-1... の1から始めるので、偶数番目だけ見る
for i in range(0, len(Nums), 2):
    # 次のleft, rightを計算する
    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 = map(int, input().split())
S = input()

#累積和の準備
zero_list = []
one_list = []
tmp = S[0]
count = 1
pin = 0
if tmp == '1':
    zero_list.append(0)
for i in range(1,N):
    if S[i] == tmp:
        count += 1
    else:
        if tmp == '1':
            one_list.append(count)
            count = 1
            tmp = '0'
        else:
            zero_list.append(count)
            count = 1
            tmp = '1'
if tmp == '1':
    one_list.append(count)
else:
    zero_list.append(count)
        
if K >= len(zero_list):
    pin =1
    print(N)
else:
    start = sum(zero_list[:K]) + sum(one_list[:K])
    ans = start
    if len(one_list) > K:
        tmp = start - zero_list[0] + zero_list[K] + one_list[K]
    else:
        tmp = start - zero_list[0] + zero_list[K]
    if tmp > ans:
        ans = tmp
    basyo = 1
    last = len(one_list)
    while basyo + K < last:
        tmp = tmp -zero_list[basyo] - one_list[basyo -1] + zero_list[K + basyo] + one_list[K + basyo]
        if tmp > ans:
            ans = tmp
        basyo += 1
    if len(one_list) != len(zero_list) and K + basyo <  len(zero_list):
        tmp = tmp -zero_list[basyo] - one_list[basyo -1] + zero_list[K + basyo] 
        if ans < tmp:
            ans = tmp
if pin == 0:
    print(ans)

Submission status: Accepted

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

s = '1' + s + '1'

cnt_1 = []
cnt_0 = []
stack_1 = 0
stack_0 = 0
for i in s:
    if i == '1':
        if stack_0 > 0:
            cnt_0.append(stack_0)
            stack_0 = 0
        stack_1 += 1
    else:
        if stack_1 > 0:
            cnt_1.append(stack_1)
            stack_1 = 0
        stack_0 += 1
if stack_1 > 0:
    cnt_1.append(stack_1)

if len(cnt_1) == 0 or len(cnt_0) == 0:
    print(n)
    exit()
cnt_1[0] -= 1
cnt_1[-1] -= 1

if k > len(cnt_0):
    k = len(cnt_0)
cum_1 = [sum(cnt_1[:k+1])]
cum_0 = [sum(cnt_0[:k])]
for i in range(1, len(cnt_1)-k):
    cum = cum_1[i-1] + cnt_1[i+k] - cnt_1[i-1]
    cum_1.append(cum)
for i in range(1, len(cnt_0)-k+1):
    cum = cum_0[i-1] + cnt_0[i+k-1] - cnt_0[i-1]
    cum_0.append(cum)
res = []

for v, w in zip(cum_1, cum_0):
    res.append(v+w)
print(max(res))

Submission status: Accepted

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

counts = []
tmp = []
for i in range(len(s)):
    if tmp == []:
        tmp = [s[i], 1]
    else:
        if tmp[0] == s[i]:
            tmp[1] += 1
        else:
            counts.append(tmp)
            tmp = [s[i], 1]
if tmp:
    counts.append(tmp)

zero_ints = 0
for char, count in counts:
    if char == '0':
        zero_ints += 1

if counts[0][0] == '0':
    left = 0
else:
    left = 1
right = left - 2

used = 0
l = 0
for char, count in counts:
    if char == '0':
        if used < k:
            used += 1
            right += 2
        else:
            break
    l += count

ans = l
for i in range(zero_ints):
    l = l - counts[left][1]
    if left - 1 >= 0:
        l-= counts[left - 1][1]
    if right + 2 < len(counts):
        l += counts[right + 2][1]
    if right + 3 < len(counts):
        l += counts[right + 3][1]
    ans = max(ans, l)
    left += 2
    right += 2
    # print(left, right, l)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
u = []
d = []
if s[0]=='0':
    d.append(0)
cnt = 1
for i in range(n-1):
    if s[i+1]=='1' and s[i]=='0':
        u.append(cnt)
        cnt = 1
    elif s[i+1]=='0' and s[i]=='1':
        d.append(cnt)
        cnt = 1
    else:
        cnt += 1
if s[-1]=='0':
    u.append(cnt)
    d.append(0)
else:
    d.append(cnt)
if len(u)<=k:
    print(n)
    exit()
tmp = sum(d[:k+1]) + sum(u[:k])
ans = tmp
for i in range(len(u)-k):
    tmp += u[i+k]+d[i+k+1]-u[i]-d[i]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
S = S()

zero = []
one = []

prev = None
count = 1
for s in S:
  if s == prev:
    count += 1
  else:
    if prev == "0":
      zero.append(count)
    if prev == "1":
      one.append(count)
    count = 1
  prev = s
if prev == "0":
  zero.append(count)
if prev == "1":
  one.append(count)
  
if len(zero) <= K:
  print(N)
  exit()

ruiseki_zero = [0]
ruiseki_one = [0]
for i in range(len(zero)):
  ruiseki_zero.append(ruiseki_zero[-1]+zero[i])
for i in range(len(one)):
  ruiseki_one.append(ruiseki_one[-1]+one[i])

MAX = 0
if S[0] == "0":
  for i in range(len(ruiseki_zero)-K):
    MAX = max(MAX,ruiseki_zero[i+K]-ruiseki_zero[i]+ruiseki_one[min(i+K,len(ruiseki_one)-1)]-ruiseki_one[max(i-1,0)])
else:
  for i in range(len(ruiseki_zero)-K):
    MAX = max(MAX,ruiseki_zero[i+K]-ruiseki_zero[i]+ruiseki_one[min(i+K+1,len(ruiseki_one)-1)]-ruiseki_one[i])

print(MAX)

Submission status: Accepted

Solution code:
import itertools

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():

    N, K = ZZ()
    S = input()
    gr = itertools.groupby(S)
    l = []
    c = 0
    for i, j in gr:
        l.append([int(i), len(list(j))])
        if i == '0': c += 1
    if c <= K:
        print(N)
        return
    output = 0
    left = right = 0
    sum = c = 0
    while left < len(l):

        while right < len(l) and c < K:
            if l[right][0] == 0: c += 1
            sum += l[right][1]
            right += 1
        if right < len(l) and l[right][0] == 1:
            sum += l[right][1]
            right += 1
        output = max(output, sum)
        if right == left:
            right += 1
            left += 1
        else:
            if l[left][0] == 0: c -= 1
            sum -= l[left][1]
            left += 1
            while left < len(l) and c >= K:
                if l[left][0] == 0: c -= 1
                sum -= l[left][1]
                left += 1
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int,input().split())
S = input()
L = np.zeros(N+1, int)
flag = '1'
i = 0
for char in S:
    if char == flag:
        L[i] += 1
    else:
        i += 1
        flag = char
        L[i] += 1

W = min(2 * K + 1, N + 1)

ans = L[:W].sum()

cnt = L[:W].sum()

for i in range((N+1-W) // 2):
    cnt = cnt - L[i*2] - L[i*2+1] + L[i*2+W] + L[i*2+W+1]
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

M=len(g)
ans=0
S=[0]
for h in range(M):
    S.append(S[h]+g[h])

if s[0]=="0":
    if K>M//2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>M:
                break
            elif j==0:
                ans=max(ans,S[j+2*K]-S[j])
            elif j%2==1:
                ans=max(ans,S[j+2*K+1]-S[j])
        ans=max(ans,S[M]-S[M-2*K])
        print(ans)
    
else:
    if K>=M//2+M%2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>M:
                break
            elif j%2==0:
                ans=max(ans,S[j+2*K+1]-S[j])
        ans=max(ans,S[M]-S[M-2*K])
        print(ans)

Submission status: Accepted

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

ttl = []
prev = S[0] # 0
cnt = 1
if S[0] == '0':
    ttl.append(0)
for i in range(1, N):
    if S[i] == prev:
        cnt += 1
    else:
        ttl.append(cnt)
        cnt = 1
    prev = S[i]
if cnt != 0:
    ttl.append(cnt)
if S[-1] == '0':
    ttl.append(0)
l = len(ttl)
sums = [0] * (l + 1)
for i in range(l):
    sums[i+1] = sums[i] + ttl[i]

cnt_width = 2 * K + 1
ans = 0
chk_l = len(sums)
for left in range(0, chk_l, 2):
    right = left + cnt_width
    if right >= chk_l:
        right = chk_l - 1
    ans = max(ans, sums[right] - sums[left])
    if left >= chk_l - 1 - cnt_width:
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,k=map(int,input().split())
s=list(map(int,list(input())))
cnt=0
q=deque()
prev=1
ans=[]
for i in s:
    if i==0 and prev==1:
        cnt+=1
    q.append(i)
    prev=i
    if cnt>k:
        #print(q)
        ans.append(len(q)-1)
        prev1=1
        while len(q)>0:
            if q[0]==1 and prev1==0 and cnt<=k:
                break
            if q[0]==0 and prev1==1:
                cnt-=1
            prev1=q[0]
            q.popleft()
ans.append(len(q))
print(max(ans))

Submission status: Accepted

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

tmp = S[0]
S_lst = []
if S[0] == '0':
    S_lst.append(0)  # 逆立ちから始める

ct = 0
for s in S:
    if tmp == s:
        ct += 1
    else:
        S_lst.append(ct)
        tmp = s
        ct = 1
if ct:
    S_lst.append(ct)

if S[-1] == '0':
    S_lst.append(0)  # 逆立ちで終える

l, r = 0, K * 2

M = sum(S_lst[:K * 2 + 1])
ans = M
while r < len(S_lst) - 2:
    M += S_lst[r + 1] + S_lst[r + 2] - S_lst[l] - S_lst[l + 1]
    ans = max(ans, M)
    l += 2
    r += 2
print(ans)

Submission status: Accepted

Solution code:
import sys

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

isOneFound = False
ruiseki = []
if S[0] == "0":
    ruiseki.append(0)

for i in range(N):
    if i == N-1:
        ruiseki.append(i+1)
        continue
    if S[i] != S[i+1]:
        ruiseki.append(i+1)

if S[-1] == "0":
    ruiseki.append(N)

#print(ruiseki)

# 全部ひっくり返せる場合
if K >= (len(ruiseki)-1) // 2:
    print(N)
    sys.exit(0)


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

print(ans)

Submission status: Accepted

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

    res = []
    buf = '1' # start:1 kara NG->s[0]
    cnt = 0
    for i in range(n):
        if s[i] == buf:
            cnt += 1
        else:
            res.append(cnt)
            buf = s[i]
            cnt = 1
    if cnt != 0:
        res.append(cnt)

    if len(res)%2 == 0:
        res.append(0) # end:1 no kosu

    #from itertools import accumulate
    #rui = list(accumulate(res))
    rui = [0]*(len(res)+1)
    for i in range(len(rui)-1):
        rui[i+1] = rui[i] + res[i]

    ans = 0
    for i in range(0,len(res),2): # 1 only
        left = i
        right = min(i+2*k+1, len(res))
        tmp = rui[right] - rui[left]
        ans = max(tmp,ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans_c,ans_n = int(s[0]),1,[] , []
    for i in range(1,len(s)):
        if tmp == int(s[i]):
            count += 1
        else:
            ans_c.append(tmp)
            ans_n.append(count)
            tmp = int(s[i])
            count = 1
    ans_c.append(tmp)
    ans_n.append(count)
    return ans_c,ans_n

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a_c,a_n =rle(S)
a_len =len(a_c)
a_n +=[0]
count =[0]*a_len
ans =0

#
if K >= (a_len +1)//2:
    ans =N
elif a_len==2:
    ans =N
elif a_len ==3 and a_c[0]==1:
    ans=N
else:
    if a_c[0] ==1:
        i=2
        indx =i +2*K 
        count[0] =sum(a_n[:0 +2*K +1])
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2
            indx =i +2*K 
    else:
        count[0] =sum(a_n[:2*K])
        count[1] =sum(a_n[1: 1+2*K+1])
        i=3
        indx =i +2*K 
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2      
            indx =i +2*K 
    ans =max(count)
print(ans)

Submission status: Accepted

Solution code:
def burst(S):
    S += "_" #dummyを追加
    st,sp,ep = S[0],0,0
    S0,S1 = [],[]
    for i in range(1,len(S)):
        if st == S[i]:
            ep += 1
        else:
            if st == "0":
                S0.append((sp,ep))
            else:
                S1.append((sp,ep))
            st,sp,ep = S[i],i,i

    return [S0,S1]

def connect(S0,S1,K,len_S):
    if len(S0) == 0 or len(S1) == 0:
        return len_S
    else:
        if S1[0][0] != 0:
            S1 = [(0,0)] + S1
        if S1[len(S1)-1][1] != len_S-1:
            S1.append((len_S-1,len_S-1))
        if len(S1)-1 <= K:
            return len_S
        else:
            output = 0
            for i in range(len(S1)-K):
                output = max(output,S1[i+K][1]-S1[i][0]+1)
            return output

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

    T = burst(S)
    S0,S1 = T[0],T[1]
    print(connect(S0,S1,K,N))

if __name__ == "__main__":
    main()