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 = list(input())
left = 0
right = 0
onecnt = 0
zerocnt = 0
zeroflag = False
leftflag = False
ans = 0

while right < N:
    if S[right] == '0' and not zeroflag:
        zerocnt += 1
        zeroflag = True
    elif S[right] == '1' and zeroflag:
        zeroflag = False
        
    if zerocnt > K and zeroflag:
        tmp = right - left
        if tmp > ans:
            ans = tmp
        while True:
            if S[left] == '0' and not leftflag:
                leftflag = True
            elif S[left] == '1' and leftflag:
                leftflag = False
                break
            left += 1
        zerocnt -= 1
    right += 1

if right - left > ans:
    ans = right - left

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
x = list(input())
xn = "1"
c = 0
y = []
for n in range(N):
    if x[n] == xn:
        c += 1
    else:
        xn = x[n]
        y.append(c)
        c = 1
y.append(c)
if len(y) % 2 == 0:
    y.append(0)
y = np.array(y)
l = 2 * K + 1
if l >= len(y):
    print(np.sum(y))
else:
    z = [np.sum(y[2 * i:2 * i + l]) for i in range((len(y) + 3 - l) // 2)]
    print(max(z))

Submission status: Accepted

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

def main():
    n, k = [int(i) for i in input().split()]
    s = input() + "3"
    s0 = []
    s1 = []
    cnt = 0
    start = 1
    for i in range(n+1):
        if start == 1 and s[i] != "1":
            s1.append(cnt)
            cnt = 1
            start = 0
        elif start == 0 and s[i] != "0":
            s0.append(cnt)
            cnt = 1
            start = 1
        else:
            cnt += 1

    #ans = max(s1)
    #for i in range(n // 2 +1):
    #    ans = max(ans, sum(s1[i:i+k+1]) + sum(s0[i:i+k]))

    ans = sum(s1[0:0+k+1]) + sum(s0[0:0+k])
    n_ans = ans

    for i in range(n):
        try:
            n_ans = n_ans + s1[k+1+i] + s0[k+i] - s1[i] - s0[i]
            ans = max(ans, n_ans)
        except:
            try:
                n_ans = n_ans + s0[k+i] - s1[i] - s0[i]
                ans = max(ans, n_ans)
            except:
                pass

    print(ans)
    #print(s1, s0)

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
s += "@" # banpei
ans, tmp = 0, 0
r, l = 0, 0
t, j = 0, 0
d = {}
cnt = 0
while True:
    bit = s[r] # current bit
    if bit == "@": # archive last, break
        tmp = r - l
        ans = max(ans, tmp)
        break
    if bit == "1":
        tmp = r - l + 1
        ans = max(ans, tmp)
    else:
        if cnt == k:
            l = d[j]; j += 1
            cnt -= 1

        while s[r+1] == "0":
            r += 1
        d[t] = r+1; t += 1
        cnt += 1

    r += 1 # move right

print(ans)

Submission status: Accepted

Solution code:
def renzoku(S):
    N = len(S)
    ans = []
    tmp = [0] * N
    for i in range(N-1):
        if S[i] == S[i+1]:
          tmp[i+1] = tmp[i] + 1  
    for i in range(N-1):
        if tmp[i] < tmp[i+1]:
            pass
        else:
            ans.append(  (S[i], tmp[i]+1)  )
    
    i = N-1
    ans.append(  (S[i], tmp[i]+1)  )
    # print(tmp)
    # print(ans)
    # return ""
    return ans


if __name__ =="__main__":
    N,K = map(int, input().split())
    S = input()
    ans = 0

    ren = renzoku(S)
    num = [ r[1] for r in ren]
    typ = [ r[0] for r in ren]
    numnew = len(ren)

    i = 0
    j = -1
    if typ[i] == "0":
        j = K*2 - 1
        pass
    else:
        j = K*2 
        pass

    if numnew <= j:
        # intS = list(map(lambda x: 1 if x=="1" else 0 , S))
        print(N)
        exit()
    

    # print("renzoku: ", ren)
    tmp = 0
    p = i
    # print("i, j: ", i, j)
    while p <= j:
        tmp += num[p]
        p += 1
    
    # print("tmp: ", tmp)
    ans = max(ans, tmp)
    while True:
        i += 1
        ans = max(ans, tmp)
        if typ[i] == "0":
            tmp -= num[i-1] 
        else:
            tmp -= num[i-1]
            prevJ = j
            j = min(j+2, numnew-1) # new J 
            for p in range(prevJ+1, j+1):
                tmp += num[p]
            ans = max(ans, tmp)
        if j == numnew -1:
            break
    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
z=[]
c=1
if n==1:
    print(1)
    exit()
for i in range(1,n):
    if s[i]==s[i-1]:
        c+=1
    else:
        z+=[c]
        c=1
z+=[c]
if s[0]=="0":
    z=[0]+z
if s[-1]=="0":
    z=z+[0]
lz=len(z)
pre=sum(z[0:2*k+1])
mx=pre
for i in range(2,lz-2*k,2):
    pre=pre-z[i-2]-z[i-1]+z[i+2*k-1]+z[i+2*k]
    if pre>mx:
        mx=pre
print(mx)

Submission status: Accepted

Solution code:
#D問題
N,K=map(int,input().split())
S=str(input())
Slist=list(S)
#偶数が”1”
hu=[]
ima=""
imal=0
for i in range(N):
    if i == 0:
        ima=Slist[0]
        imal=1
        if Slist[0] == "0":
            hu.append(0)
    else:
        if ima==Slist[i]:
            imal+=1
        else:
            hu.append(imal)
            ima=Slist[i]
            imal=1
hu.append(imal)
Ngu=len(hu)
rui=[0]
for i in range(Ngu):
    if i == 0:
        rui.append(hu[0])
    else:
        karui=rui[i]+hu[i]
        rui.append(karui)

        
MAX=0

for i in range(Ngu+1):
    if i%2==0:
        if 2*K+i-1<Ngu+1:
            if i > 0:
                kari=rui[2*K+i-1]-rui[i-1]
            else:
                kari=rui[2*K+i-1]
        else:
            if i > 0:
                kari=rui[-1]-rui[i-1]
            else:
                kari=rui[-1]
    else:
        if 2*K+i<Ngu+1:
            if i > 0:
                kari=rui[2*K+i]-rui[i-1]
            else:
                kari=rui[2*K+i]
        else:
            if i > 0:
                kari=rui[-1]-rui[i-1]
            else:
                kari=rui[-1]
    MAX=max(kari,MAX) 
print(MAX)

Submission status: Accepted

Solution code:
import math

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

S=input()
zerostart=0

if S[0]=='0':
  zerostart=1

continouslist=[]

nowchar=S[0]
nowcon=1
for i in range(1,len(S)):
  if nowchar!=S[i]:
    continouslist.append(nowcon)
    nowcon=1
    nowchar=S[i]
  else:
    nowcon+=1
continouslist.append(nowcon)

if zerostart:
  #print('Zero')
  if K>=math.ceil(len(continouslist)/2):
    print(N)
    exit()
  else:
    now=0
    ans=0
    for i in range(len(continouslist)):
      now+=continouslist[i]
      if K<=int(i/2) and i%2==0:
        now-=continouslist[i-2*K]
        if (i-2*K)!=0:
          now-=continouslist[i-2*K-1]
      #print(now)
      ans=max(now,ans)
  
else:
  #print('ONe')
  if K>=math.floor(len(continouslist)/2):
    print(N)
    exit()
  else:
    now=0
    ans=0
    for i in range(len(continouslist)):
      now+=continouslist[i]
      if K<int(i/2)+1 and i%2==1:
        now-=continouslist[i-2*K]
        now-=continouslist[i-2*K-1]
      #print(now)
      ans=max(now,ans)
#print(continouslist)
print(ans)

Submission status: Accepted

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


    
check="1"
seq=0
for i in s:
    if check!=i:
        check=i
        li.append(seq)
        seq=1
    else:
        seq+=1
        
li.append(seq)

for  i in range(len(li)):
    if i%2==0:
        li_o.append(li[i])
    else:
        li_z.append(li[i])
    
if s[n-1]=="0":
    li_o.append(0)


if len(li_o)<=k:
    print(n)
else:
    m=sum(li_o[0:0+k+1])+sum(li_z[0:0+k])
    tmp=m
    for i in range(1,len(li_o)-k):
        tmp=tmp-li_o[i-1]+li_o[i+k]-li_z[i-1]+li_z[i+k-1]
        m=max(tmp,m)
        
    print(m)

Submission status: Accepted

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

kukan = []
cnt0 = 0
cnt1 = 0
for n in range(N):
        if S[n] == '0':
                cnt0 +=1
                if cnt1 > 0:
                        kukan.append(cnt1)
                cnt1 = 0
        if S[n] == '1':
                cnt1 +=1
                if cnt0 > 0:
                        kukan.append(cnt0)
                cnt0 = 0

kukan.append(max(cnt1,cnt0))

#print(kukan)
ans = []

if S[0] == '0':
        start = 1
else:
        start = 0

l = len(kukan)

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

cnt = [0]*(l+1)
for i in range(1,l+1):
        cnt[i] = cnt[i-1] + kukan[i-1]

#print(cnt)
        


for i in range(1,l-K+1):
        if (i+start)%2 == 1:
                #print(i+2*K)
                ans.append(cnt[min(l,i+2*K)]-cnt[i-1])
        else:
                #print(i+2*K-1)
                ans.append(cnt[min(l,i+2*K-1)]-cnt[i-1])


print(max(ans))

Submission status: Accepted

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

o = []
z = []

i = 0
while True:
  cnt = 0
  while i <= N-1 and int(S[i]) == 1:
    cnt += 1
    i += 1
  o.append(cnt)
  if i > N-1:
    break
  cnt = 0
  while i <= N-1 and int(S[i]) == 0:
    cnt += 1
    i += 1
  z.append(cnt)
#print(o)
#print(z)

if len(z) <= K:
  print(len(S))
  sys.exit()

num = o[0]
for j in range(K):
  num += z[j]+o[j+1]

max_num = num
for j in range(K, len(z)):
  num -= o[j-K]+z[j-K]
  num += z[j]+o[j+1]
  max_num = max(max_num, num)

print(max_num)

Submission status: Accepted

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

ls = []
temp = 0
n = 1
for i in S:
    if n == i:
        temp += 1
    else:
        ls.append(temp)
        n = i
        temp = 1
if temp != 0: 
    ls.append(temp)
if n == 0:
    ls.append(0)

if K * 2 + 1 > len(ls):
    m = 0
    for i in ls:
        m += i
    print(m)
else:
    m = 0
    temp = 0
    for i in range(2*K + 1):
        temp += ls[i]
    m = temp
    for i in range(len(ls) // 2 - K):
        temp = temp - ls[2*i] - ls[2*i+1] + ls[2*K + 2*i + 1] + ls[2*K + 2*i + 2]
        if m < temp:
            m = temp

    print(m)

Submission status: Accepted

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

isOne = True
cnt = 0
ans = 0
for i in S:
    if isOne:
        if i == "0":
            countList.append(cnt)
            isOne = False
    else:
        if i == "1":
            countList.append(cnt)
            isOne = True
    cnt += 1
countList.append(cnt)
if(isOne == False):
    countList.append(cnt)
K = min(len(countList)//2, K)
for i in range(len(countList)):
    if i*2+2*K<len(countList):
        if i*2-1 < 0:
            ans = max(ans, countList[i*2+2*K])
            continue
        ans = max(ans, countList[i*2+2*K]-countList[i*2-1])
    else:
        break

if len(countList)==1:
    ans = countList[0]
print(ans)

Submission status: Accepted

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

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

cursum = [0]*(len(li)+1)
for i in range(len(li)):
    cursum[i+1] = cursum[i]+ li[i]

if s[0]=="1":
  is_s_1 = True
else:
  is_s_1 = False

ans = 0
for i in range(1,len(cursum)):
    if is_s_1:
        low_limit = max(i-2*k-1,0)
    else:
        low_limit = max(i-2*k,0)
    ans = max(ans,cursum[i] - cursum[low_limit])
    is_s_1 = not is_s_1

if ans == 0:
    print(n)
else:
    print(ans)

Submission status: Accepted

Solution code:
_n,_k = map(int,input().split())
_s = input()
_w=[]
if _s[0]=='0':
    _w.append(0)
ps=''
for s in _s:
    if ps==s:
        _w[-1]+=1
    else:
        _w.append(1)
        ps=s
if ps=='0':
    _w.append(0)
lw=len(_w)
wsum=sum(_w[0:(2*_k+1)])
wsum_max=wsum
for j in range(0,lw,2):
    if j+2*_k+1>=lw:
        break
    wsum-=_w[j]
    wsum-=_w[j+1]
    wsum+=_w[j+2*_k+1]
    wsum+=_w[j+2*_k+2]
    if wsum_max<wsum:
        wsum_max=wsum
print(wsum_max)

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,K = list(map(int,input().split()))
        S = np.asarray(list(map(int,list(str(input())))))
    else:
        N,K = [10**5,1]
        T = np.asarray(range(N))
        S = np.zeros(N)
        S[T%2==0] = 1

    SN = np.zeros(10**5+2)
    first = S[0]
    tmpnum = first
    k = 0
    if first == 0:
        k += 1
    k += 1

    count = 0
    for n in range(N)[1:]:
        if S[n] == tmpnum:
            count += 1
        else:
            count += 1
            SN[k] = count
            k += 1
            tmpnum = S[n]
    else:
        count += 1
        SN[k] = count
        if tmpnum == 0:
            SN[k+1] = count

    max = 0
    flag = 0
    for n in range(SN.size)[2*K+1::2]:
        if SN[n] == 0: break
        if max < SN[n] - SN[n-2*K-1]:
            max = SN[n] - SN[n-2*K-1]
        flag = 1
    
    if flag == 0:
        print(int(np.max(SN)))
    else:
        print(int(max))

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
check=1
cnt=0
l=[]
for i in range(n):
    if check==1 and s[i]=='0':
        check=-1
        l.append(cnt)
        cnt=0
    elif check==-1 and s[i]=='1':
        check=1
        l.append(cnt)
        cnt=0
    cnt+=1
    if i==n-1:
        l.append(cnt)
if s[0]=='1':
    ans=sum(l[0:k*2+1])
    ansl=[ans]
    i=2*k+1
    while i<len(l):
        ans+=l[i]-l[i-2*k-1]-l[i-2*k]
        if i+1<len(l):
            ans+=l[i+1]
        i+=2
        ansl.append(ans)
if s[0]=='0':
    ans=sum(l[0:2*k+1])
    ansl=[ans]
    i=2*k+1
    while i<len(l):
        ans+=l[i]+-l[i-2*k-1]-l[i-2*k]
        if i+1<len(l):
            ans+=l[i+1]
        i+=2
        ansl.append(ans)
print(max(ansl))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
left = 0
rc = 0
rf = False
lf = False
ans = 0
if set(S) == set("0") or set(S) == set("1"):
    print(len(S))
    exit()
for right in range(N):
    if rf and S[right] == "0" and rc <= K:
        if right != N-1:
            continue
        else:
            ans = max(ans, right - left)
            break
    if S[right] == "1":
        rf = False
    if S[right] == "0":
        rc += 1
        rf = True
    if rc > K:
        while True:
            if S[left] == "1":
                left += 1
            if S[left] == "0":
                while S[left] == "0":
                    left += 1
                break
        rc -= 1
    ans = max(ans, right - left)
print(ans+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])
S = input()

prev = '1'
count = 0
nums = []
for i in S:
    if i == prev:
        count += 1
    else:
        nums.append(count)
        count = 1
        prev = i
if count > 0:
    nums.append(count)
# print(nums)

C = min(K * 2 + 1, len(nums))
s1 = 0
for i in range(0, C):
    s1 += nums[i]
sums = [s1]
prev = s1
for i in range(0, len(nums)):
    s = prev - nums[i]
    if i + C < len(nums):
        s += nums[i + C]
    if i % 2 == 1:
        sums.append(s)
    prev = s
# print(sums)

print(max(sums))

Submission status: Accepted

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

def gen_0_idx(S):
  N = len(S)
  idx_list = []
  start_0 = False
  for i in range(N):
    if S[i] == "0" and not start_0:
      start_idx = i
      start_0 = True
    elif S[i] == "1" and start_0:
      end_idx = i - 1
      idx_list.append((start_idx, end_idx))
      start_0 = False
    if i == N - 1 and start_0:
      end_idx = i
      idx_list.append((start_idx, end_idx))
  return idx_list

idx_list = gen_0_idx(S)
if len(idx_list) <= K:
  print(N)
else:
  N_I = len(idx_list)
  one_len_list = []
  for i in range(N_I - K + 1):
    if i == 0:
      length = idx_list[K][0]
    elif i == N_I - K:
      length = N - idx_list[N_I - K - 1][1] - 1
    else:
      length = idx_list[i + K][0] - idx_list[i - 1][1] - 1
    one_len_list.append(length)
  print(max(one_len_list))

Submission status: Accepted

Solution code:
nk = input()
nk = nk.split()
n = int(nk[0])
k = int(nk[1])

s = input()

count = 0
now = None
clist = []

for ss in s:
    if now is None:
        if ss == '0':
            clist.append(0)

    if now is None or now == ss:
        count += 1
    else:
        clist.append(count)
        count = 1
    now = ss

clist.append(count)

max_len = k * 2 + 1
max_sum = 0
clist_len = len(clist)
now_sum = None

for i in range(0, clist_len):
    if i % 2 == 1:
        continue
    j = i + max_len

    if now_sum is None:
        now_sum = sum(clist[i:j])
        max_sum = now_sum
    else:
        now_sum -= sum(clist[(i-2):i])
        now_sum += sum(clist[(j-2):(j)])
        max_sum = max(max_sum, now_sum)

print(max_sum)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template #


N, K = mi()
strS = li()
S = [int(i) for i in strS]
S.append(0)
# S.insert(0, 1)
# print(S)

cnt = 0
lis0 = []
if S[0] == 1:
    listart = [0]
    cnt += 1
else:
    listart = []
liend = []
for i in range(1, N):
    # if S[i] == 0:
    #     cnt += 1
    if S[i-1] == 0 and S[i] == 1:
        listart.append(i)
        lis0.append(i)
    if S[i-1] == 1 and S[i] == 0:
        liend.append(i-1)
# if S[N-1] == 0:
#     lis0.append(N)
if S[N-1] == 1:
    liend.append(N - 1)
    cnt += 1
# lis.append(N)
# lis.insert(0, -1)
len0 = len(listart) + 1 - cnt
# print(listart)
# print(liend)
# print(len0)
# print(ma)
if K >= len0:
    print(N)
else:
    ma = max(liend[K - 1] + 1, N - listart[-K])
    for i in range(len(listart) - K):
        ma = max(ma, liend[i+K]-listart[i]+1)
    print(ma)

Submission status: Accepted

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

c_1 = [0]
c_0 = [0]
count = 0
before = '1'
answer = 0



for i in S:
    if i == before:
        count += 1
    else:
        if before == '1':
            c_1.append(c_1[-1] + count)
        else:
            c_0.append(c_0[-1] + count)
        if i == '0':
            if K+1 < len(c_1):
                answer = max(answer, c_1[-1] - c_1[-(K+2)] + c_0[-1] - c_0[-(K+1)])
            else:
                answer = max(answer, c_1[-1] + c_0[-1])
        count = 1
        before = i

if i == '1':
    c_1.append(c_1[-1] + count)
    if K + 1 < len(c_1):
        answer = max(answer, c_1[-1] - c_1[-(K + 2)] + c_0[-1] - c_0[-(K + 1)])
    else:
        answer = max(answer, c_1[-1] + c_0[-1])

else:
    c_0.append(c_0[-1] + count)

    if K + 1 < len(c_1):
        answer = max(answer, c_1[-1] - c_1[-(K + 1)] + c_0[-1] - c_0[-(K + 1)])
    else:
        answer = max(answer, c_1[-1] + c_0[-1])


print(answer)

Submission status: Accepted

Solution code:
import numpy as np
# import copy


n,k = map(int,input().split())
s = [int(a) for a in input()]

ls = []
start = s[0]
prev = s[0]
cnt = 1
for i in range(1,n):
    if s[i] == prev:
        cnt += 1
    else:
        prev = s[i]
        ls.append(cnt)
        cnt = 1
ls.append(cnt)

ma = 0
if start == 1:
    if len(ls) <= 2*k + 1:
        ma = len(s)
    else:
        attack_points = len(ls) // 2
        ls = np.array(ls)
        for i in range(attack_points+1-k):
            try:
                su = np.sum(ls[2*i:2*k+1+2*i])
            except IndexError:
                su = np.sum(ls[2*i:2*k+2*i])
            
            if su > ma:
                ma = su
else:
    if len(ls) <= 2*k - 1:
        ma = len(s)
    else:
        attack_points = (len(ls)+1) // 2 
        ls = np.array(ls)
        for i in range(attack_points+1-k):
            if i == 0:
                try:
                    su = np.sum(ls[:2*k])
                except IndexError:
                    su = np.sum(ls[:2*k-1])
                if su > ma:
                    ma = su
            elif i == attack_points - k:
                try:
                    su = np.sum(ls[2*i-1:2*k+2*i])
                except IndexError:
                    su = np.sum(ls[2*i-1:2*k+2*i-1])
                if su > ma:
                    ma = su
            else:
                try:
                    su = np.sum(ls[2*i-1:2*k+2*i])
                except IndexError:
                    su = np.sum(ls[2*i-1:2*k-1+2*i])
                if su > ma:
                    ma = su
print(ma)

Submission status: Accepted

Solution code:
tmp=input().split(" ")
n = int(tmp[0])
k = int(tmp[1])

s=input()

def sumrange(arr, l, r):
    #print("sumrange:", l, r, arr[r] - arr[l-1])
    return arr[r] - arr[l-1]

prev="1"
counts=[0]
count=0
prev_count=0
for c in s:
    if c == prev:
        count+=1
    else:
        counts.append(prev_count + count)
        prev=c
        prev_count += count
        count=1
else:
    counts.append(prev_count + count)

#print(counts)

w = k * 2 + 1
#print(w)

max_score=0
for i in range(0, len(counts)-1, 2):
    if(i + 1 >= len(counts)):
        break
    l = i+1
    r = min(l + w - 1, len(counts)-1)
    score = sumrange(counts, l, r)
    max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

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

p=S[0]
l=[]

prev_c0=0
prev_c1=0
c=0
order=0
ind=0
ans=[]
val=0

for s in S:
    if s==p:
        c+=1
    else:
        if p=='0':
            prev_c0=c
        if p=='1':
            order+=1
            val+=prev_c0+c
            l.append(prev_c0+prev_c1)
            if order>K:
                val-=l[ind]
                ind+=1
            ans.append(val)
            prev_c1=c
        c=1
        p=s
if c>=2:
    if p=='0':
        if order<K:
            ans.append(val+c)
        else:
            ans.append(val+c-l[ind])
    if p=='1':
        order+=1
        val+=prev_c0+c
        if order>K:
            val-=l[ind]
        ans.append(val)
if len(ans)>0:
    print(max(ans))
else:
    print(len(S))

Submission status: Accepted

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

scores = []

if S[0] == '0':
    scores.append(0)

cur = 'w'
for i in range(len(S)):
    if cur == S[i]:
        scores[-1] += 1
    else:
        scores.append(1)
        cur = S[i]

if S[-1] == '0':
    scores.append(0)

import numpy as np
scoreCS = np.cumsum(np.array([0]+scores))

ans = -1
for l in range(0, len(scoreCS), 2):
    r = K*2 + 1 + l
    if r >= len(scoreCS):
        break
    ans = max(ans, scoreCS[r] - scoreCS[l])

if ans == -1:
    ans = scoreCS[-1]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

b = input().split()
n = int(b[0])
k = int(b[1])
s = input()

arr = []

if int(s[0]) == 0:
    arr.append(0)

before_change = 0
for i in range(1,n):
    if int(s[i - 1]) != int(s[i]):
        arr.append(i - before_change)
        before_change = i
arr.append(n - before_change)
arr = np.array(arr)
#print(arr) 

n_add = 2 * k + 1
ans = 0

if n <= n_add:
    ans = arr.sum()
else:
    i = 0
    while i + n_add <= n:
        temp = arr[i:i+n_add].sum()
        if temp > ans:
            ans = temp
        i += 2

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

# 2 * k + 1
# 累積和
# W 白(0)から
if S[0] == '0':
    W = [0, 0, 1]
else:
    W = [0, 1]
    
for i in range(1,N):
    if S[i-1] == S[i]:
        W[-1] += 1
    else:
        W.append(1)
if S[-1] == '0':
    W.append(0)

W_ac = list(itertools.accumulate(W))
W_un = list(set(S))
if len(W_ac) <= 2 * K + 1 or len(W_un) == 1:
    ans = N
    print(ans)
else:
    ans = []
    for i in range(2*K+1, len(W_ac)):
        if i % 2 == 1:
            ans.append(W_ac[i] - W_ac[i-(2*K+1)])
    print(max(ans))

Submission status: Accepted

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

res = 0
left = 0
right = 0
# start
cnt = 0
for i in range(N-1):
    if S[i] == "0" and S[i+1] == "1":
        cnt += 1
    if cnt == K and S[i+1] == "0":
        right = i
        break
    if i == N - 2:
        right = N - 1
    
res = max(res, right - left + 1)

while right < N-1:
    left += 1
    right += 1
    while left < N:
        if S[left] == "1" and S[left-1] == "0":
            break
        else:
            left += 1
    while right < N - 1:
        if S[right] == "1" and S[right+1] == "0":
            break
        else:
            right += 1
    res = max(res, right - left + 1)
    
print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

consecutive01s = [[], [0]]
turn = 0
num = 0
for S in Ss+[9]:
    if S == turn:
        num += 1
    else:
        consecutive01s[turn].append(num)
        turn = 1-turn
        num = 1
if turn == 0:
    consecutive01s[0].append(0)
consecutive01s[1].append(0)

N0, N1 = len(consecutive01s[0]), len(consecutive01s[1])
K = min(K, N0)

acc0s = list(accumulate([0]+consecutive01s[0]))
acc1s = list(accumulate([0]+consecutive01s[1]))

len0s = [acc0s[i+K]-acc0s[i] for i in range(N0-K+1)]
len1s = [acc1s[i+K+1]-acc1s[i] for i in range(N1-K)]

ans = max([len0+len1 for len0, len1 in zip(len0s, len1s)])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()+"d"
d=[]
r=s[0]
c=0
for i in range(n+1):
    if r==s[i]:
        c+=1
    else:
        d.append(c)
        r=s[i]
        c=1
if s[0]=="0":
        d=[0]+d
if s[-2]=="0":
    d+=[0]
if len(d)<=2*k+1:
    print(n)
else:
    l=sum(d[:2*k+1])
    p=sum(d[:2*k+1])
    for i in range((len(d)-2*k-1)//2):
        p=p-d[2*i]-d[2*i+1]+d[2*i+2*k+1]+d[2*i+2*k+2]
        l=max(l,p)
    print(l)

Submission status: Accepted

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

now = None
cnt = []
before_i = 0
for i, c in enumerate(s):
	if i==0:
		now = c
		continue
	if now==c:
		continue
	else:
		cnt.append(i-before_i)
		now = c
		before_i = i
cnt.append(i+1-before_i)
l=0

if s[0] == '0':
	tmp = sum(cnt[:2*k])
	r = 2*k-1
	l0 = True
else:
	tmp = sum(cnt[:2*k+1])
	r = 2*k
	l0 = False

if r>=len(cnt):
	print(tmp)
	exit()

ans = tmp

while r+1<len(cnt):
	if l0:
		tmp = tmp - cnt[l]
		l += 1
		l0 = (cnt[l]==0)
	else:
		tmp = tmp - cnt[l] - cnt[l+1]
		l += 2
		l0 = (cnt[l]==0)
	tmp += cnt[r+1]
	if r+2<len(cnt):
		tmp += cnt[r+2]
		r += 2
	else:
		r += 1
	r0 = (cnt[r]==0)

	if tmp>ans:
		ans = tmp

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = [int(n) for n in input().split()]
    S = input()
    S = [int(s) for s in S]
    cnt = 0
    suc = 1
    zeros = []
    ones = []
    
    for i in S:
        if i == suc:
            cnt += 1
        else:
            if suc == 0:
                zeros.append(cnt)
                cnt = 1
            elif suc == 1:
                ones.append(cnt)
                cnt = 1
            suc ^= 1
    if suc == 0:
        zeros.append(cnt)
    elif suc == 1:
        ones.append(cnt)
    
    if suc != 1:
        ones.append(0)
    
    if len(zeros) <= K:
        print(len(S))
        return
    # print(zeros)
    # print(ones)
    s = sum(zeros[:K])+sum(ones[:K+1])
    # print(s)
    m = s
    left = 0
    right = K-1
    while True:
        if right == len(zeros)-1:
            break
        s -= zeros[left] + ones[left]
        s += zeros[right+1] + ones[right+2]
        if s > m:
            m = s
        # print(left, right, s)
        
        left += 1
        right += 1
    print(m)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy

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

strList = [0, 0]
oneNum = 0
zeroNum = 0
if S[0] == "1":
    strList.append(0)

for i in range(N):
    if S[i] == "1":
        oneNum += 1
        if zeroNum != 0:
            strList.append(zeroNum)
        zeroNum = 0
    if S[i] == "0":
        zeroNum += 1
        if oneNum != 0:
            strList.append(oneNum)
        oneNum = 0

if oneNum != 0:
    strList.append(oneNum)
if zeroNum != 0:
    strList.append(zeroNum)

strList.append(0)
strList.append(0)

strCumsum = numpy.cumsum(strList).tolist()

ans = 0
for i, s in enumerate(strCumsum):
    if i % 2 == 1:
        ans = max(ans, strCumsum[i] - strCumsum[max(0, i - K * 2 - 1)])

print(ans)

Submission status: Accepted

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

array = [0]
result = 0
if S[0] == '1':
    flag = False

else:
    flag = True
    array.append(0)

flag2 = False

for i in range(N):
    if S[i] == '0':
        if not flag:
            flag = True
            array.append(i)
            if len(array) == K * 2 + 2:
                flag2 = True
                result = max(array[-1] - array[0], result)
                del array[0]
                del array[0]
            

    else:
        if flag:
            flag = False
            array.append(i)

result = max(N - array[0], result)

print(result if flag2 else N)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

x = [[0, 0]]
current_s = S[0]
count_zero = 0
count_one = 0
for i, s in enumerate(S):
    if s == current_s:
        if s == '0':
            count_zero += 1
        else:
            count_one += 1
    else:
        if current_s == '0':
            x.append([count_one, count_zero])
            count_one = 1
            count_zero = 0
        else:
            count_zero = 1
        current_s = s
x.append([count_one, count_zero])    

if x[-1][-1] != 0:
    x.append([0,0])
num_white = len(x)
        
cum_x = []
current_sum = 0
for i in range(len(x)):
    current_sum += sum(x[i])
    cum_x.append(current_sum)

if num_white <= (K + 1):
    print(N)
else:
    max_value = 0
    for i in range(K, num_white-1):
        max_value = max(max_value, cum_x[i] - cum_x[i - K] + x[i + 1][0])
    print(max_value)