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, raw_input().split())
S=raw_input()

c=S[0]
# T[0] := ("1" or "0", num)
T=[[c, 1]]
for s in S[1:]:
    if c==s:
        T[-1][1]+=1
    else:
        c=s
        T.append([c,1])

ans=-1
p=0
n=p
k=0
s=0
while n<len(T):
    if(T[n][0]=="0"):
        if k<K:
            k+=1
            s+=T[n][1]
        else:
            break
    else:
        s+=T[n][1]
    n+=1
ans=s
for pp in range(len(T)-1):
    p=pp+1
    if T[p][0]=="1":
        s-=T[p-1][1]
        if p+2*k-1<len(T):
            s+=T[p+2*k-1][1]
        if p+2*k<len(T):
            s+=T[p+2*k][1]
    else:
        s-=T[p-1][1]        
    ans=max(ans,s)  
print(ans)

Submission status: Accepted

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


S += 'X'
Zero_begin = []

begin_checked = False
for i, s in enumerate(S):
    if not begin_checked:
        if s == '0':
            Zero_begin.append(i)
            begin_checked = True

    else:
        if s != '0':
            begin_checked = False


Zero_begin.append(N)
ans = 0
for i in range(N):
    if (i == 0) or (S[i] == '1'):
        left_i = bisect_left(Zero_begin, i)
        right_i = min(left_i + K, len(Zero_begin) - 1)
        ans = max(ans, Zero_begin[right_i] - i)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 20:57:46 2019

@author: Yamazaki Kenichi
"""
import sys

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

T = []
a,b = 0,0
if S[0] == '0':
    T.append(0)
for c in S:
    if c =='1':
        if a > 0:
            a += 1
        else:
            a = 1
            T.append(b)
            b = 0
    else:
        if b > 0:
            b += 1
        else:
            b = 1
            T.append(a)
            a = 0
T.extend([max(a,b),0,0])
if K*2+3 >= len(T):
    print(sum(T))
    sys.exit()
    
m,tmp = sum(T[1:K*2+2]),sum(T[1:K*2+2])
for i in range(0,len(T)-(K*2+3),2):
#    print(i)
#    print(m,tmp,T[i+1],T[i+2],T[i+K*2+2],T[i+K*2+3])
    tmp = tmp-T[i+1]-T[i+2]+T[i+K*2+2]+T[i+K*2+3]
    m = max(m,tmp)
print(m)

Submission status: Accepted

Solution code:
from sys import stdin
##  input functions for me
def ria(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

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

a = [0] * N
prev = 1
v = 0
for i in range(N):
    if S[i] != prev: v += 1
    a[i] = v
    prev = S[i]

ma = 0
l = 0
r = 0
for v in range(a[0], a[N - 1] + 1):
    while a[l] < v : l += 1
    rv = 0
    if S[l] == '0':
        rv = v + 2 * K - 1
    else :
        rv = v + 2 * K
    while r < N and a[r] <= rv: r += 1
    ma = max(ma, r - l)

print(ma)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = str(input().strip())
    S += 'x'

    A = []
    S0 = S[0]
    cnt = 0
    for s in S:
        if S0 == s:
            cnt += 1
        else:
            A.append(cnt)
            cnt = 1
            S0 = s


    n = len(A) // 2
    if len(A) % 2 == 1 and S[0] == '0':
        n += 1

    if n <= K:
        return sum(A)

    if S[0] == '0':
        A = [0] + A
    if S[-2] == '0':
        A = A + [0]
    A = [0] + list(accumulate(A))

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

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

l = []
n = 0
p = '1'
for s in S:
    if s != p:
        l.append(n)
        p = s
        n = 1
    else:
        n = n + 1
l.append(n)

nw = sum(l[0:(min(K * 2 + 1, N))])
mx = nw
for j in range(2,len(l),2):
    lef = l[j - 2] + l[j - 1]
    rig = 0
    if (j + K * 2 - 1) < len(l):
        rig = rig + l[j + K * 2 - 1]
        if (j + K * 2) < len(l):
            rig = rig + l[j + K * 2]
    nw = nw - lef + rig
    mx = max(mx, nw)
print(mx)

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
S = list(input())
d = deque()
p = 0
q = 0
num = 0
i = 0
while i < N:
    if S[i] == '0':
        tmp = 0
        while i < N and S[i] == '0':
            tmp += 1
            i += 1
        d.append(p + tmp)
        q += d[-1]
        last = 0
        if len(d) > K:
            q -= d.popleft()
        num = max(num, q)
    else:
        j = i
        while j < N and S[j] == '1':
            j += 1
        p = j - i
        i = j
        num = max(num, p + q)
print(num)

Submission status: Accepted

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

a = [0]
i = 0
p = "1"
for t in s:
  if t == p:
    a[i] += 1
  else:
    p = t
    i += 1
    a += [1]
a += [0]
# print(a)

if len(a) <= 2*k+1:
  print(sum(a))
  quit()

x = sum(a[:2*k+1])
m = x 
for i in range(2*k+1,len(a)):
  # print(i, a[i] , a[i-(2*k+1)])
  x = x + a[i] - a[i-(2*k+1)]
  if i%2 == 0:
    m = max(m,x)
print(m)

Submission status: Accepted

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

keep = []
flag = False
start, end = 0, 0
while start < N and end < N:
    if flag:
        if S[end] == "1": end += 1
        else:
            keep.append(end - start)
            start = end
            flag = False
    else:
        if S[start] == "1":
            keep.append(start - end)
            flag = True
            end = start + 1
        else:
            start += 1
if flag: keep.append(end - start)
else: keep.append(start - end)

stand = len(keep) // 2
if len(keep) % 2 == 1: 
    stand += 1
    keep.append(0)

if stand <= K: print(N)
else:
    maxL = sum(keep[:2*K])
    length = maxL
    for i in range(1, stand - K+1):
        length += keep[2*(K+i-1)]+keep[2*(K+i-1)+1] - keep[2*(i-1)]
        if i >= 2: length -= keep[2*(i-1)-1]
        maxL = max(maxL, length)
    print(maxL)

Submission status: Accepted

Solution code:
size,K = map(int, raw_input().split())
S = raw_input()
flag = 0
a = []
temp1 = []
temp2 = []
n = 0
for c in S:
	if(flag == 0):
		if(c == '1'):
			temp1.append(n)
			flag = 1
	else:
		if(c == '0'):
			flag = 0
			temp2.append(n)
	n += 1
n = 0
if(K <= len(temp2)):
	a.append(temp2[K-1])
	for i in temp1:
		if(n + K < len(temp2)):
			a.append(temp2[n + K] - i)
		else:
			a.append(size - i)
		n += 1
else:
	a.append(size)
print(max(a))

Submission status: Accepted

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

count = 1
if s[0] == 0:
    count_list = [0]
elif s[0] == 1:
    count_list = []

for i in range(n - 1):
    if s[i] == s[i + 1]:
        count = count + 1
    else:
        count_list.append(count)
        count = 1
count_list.append(count)

count_list2 = [0]
count2 = 0
for i in range(len(count_list)):
    count2 = count2 + count_list[i]
    count_list2.append(count2)

maximum = []
i = 0
while 2 * i < len(count_list2):
    l = count_list2[2 * i]
    if 2 * i + 2 * k + 1 > len(count_list2) - 1:
        r = count_list2[len(count_list2) - 1]
    else:
        r = count_list2[2 * i + 2 * k + 1]
    maximum.append(r - l)
    i = i + 1

print(max(maximum))

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
S = input()
O = [[0, 0]]
is1 = False
for i in range(N):
    if S[i] == '1':
        if not is1:
            O += [[i, N]]
        is1 = True
    elif S[i] == '0':
        if is1:
            O[-1][-1] = i
        is1 = False
O += [[N, N]]
K = min([len(O) - 1, K])
ans = 0
for i in range(len(O) - K):
    ans = max([ans, O[i + K][1] - O[i][0]])
print(ans)

Submission status: Accepted

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

first = s[0]
end = s[-1]
len_list = []

count = 0
pre = first
for i in range(n):
    if s[i] == pre:
        count += 1
    else:
        len_list.append(count)
        pre = s[i]
        count = 1
len_list.append(count)
sum_list = [0]
sum_tmp = 0
for i in len_list:
    sum_tmp += i
    sum_list.append(sum_tmp)

size = len(len_list)

if size < 2*k + 1:
    print(n)
else:
    ans = 0
    index = 0
    if first == '0':
        index = 1
        ans = sum_list[2*k] - sum_list[0]
    if end == '0':
        ans = max((sum_list[size] - sum_list[size-2*k]), ans)

    while index + 2 * k < size:
        ans = max(ans, (sum_list[index+2*k+1] - sum_list[index]))
        index += 2

    print(ans)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
S = input()
n = []
p = S[0]
c = 1
for s in S[1:]:
    if s != p:
        n.append(c)
        p = s
        c = 0
    c+=1
n.append(c)
ans = max(n)
sum_n = [0]
for i in n:
    sum_n.append(i+sum_n[-1])
if S[0]=="0":
    for i in range(1,len(n)-2*K+1,2):
        ans = max(ans,sum_n[min(i+2*K+1,len(sum_n)-1)]-sum_n[i])
    sum_n.pop(1)
    n.pop(0)
    K -=1
for i in range(0,len(n)-2*K+1,2):
    ans = max(ans,sum_n[min(i+2*K+1,len(sum_n)-1)]-sum_n[i])
if (len(n)-2*K+1)<=0:
    ans = max(ans,sum_n[-1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


n,k = map(int, input().split())
sn = list(str(input()))
snum = [1] * (10**5)

l = 0
for i in range(1,n):
  if sn[i-1] == sn[i]:
    snum[l] += 1
  else:
    l += 1
snum = snum[:l+1]

if sn[0] == '1':
  snum = [0] + snum
if sn[-1] == '1':
  snum = snum + [0]

csnum = [0] * (len(snum)+1)
for i in range(len(snum)):
  csnum[i+1] = csnum[i] + snum[i]


## solve
l = 0
mx = 0
for r in range(len(csnum)):
  if r&1 == 1 and (r-l+1)//2 > k:
    l += 2
  mx = max(mx, csnum[r] - csnum[max(0,l-1)])

print(mx)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input()
li = [(0, 0)]
i = 0
while i < N:
    if s[i] == '1':
        l = i
    while i < N and s[i] == '1':
        i += 1
        if not (i < N and s[i] == '1'):
            break
    else:
        i += 1
        continue
    r = i - 1
    li.append((l, r))
    i += 1
li.append((N - 1, N - 1))
ans = 0
if K > len(li):
    K = len(li) - 1
for i in range(len(li) - K):
    ans = max(ans, li[i + K][1] - li[i][0])
print(ans + 1)

Submission status: Accepted

Solution code:
import math

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

list2=[]
renzoku=0

if s[0]=='0':
    list2.append(0)

for x in range(n-1):
    renzoku+=1
    if int(s[x])!=int(s[x+1]):
        list2.append(renzoku)
        renzoku=0

list2.append(renzoku+1)
if len(list2)%2==0:
    list2.append(0)

#print(list2)

kaisu=math.ceil(len(list2)/2)-k
max=0
if kaisu<=0:
    max=len(s)

for y in range(kaisu):
    #print(list2[y*2:y*2+(2*k+1)])
    if y==0:
        gokei=sum(list2[y*2:y*2+(2*k+1)])
    else:
        gokei-=(list2[y*2-2]+list2[y*2-1])
        gokei+=(list2[y*2+k*2-1]+list2[y*2+k*2])
    if gokei>max:
        max=gokei
print(max)

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
s = input()
x,y,f,num,ans = [],[],1,0,0
for i in range(n):
    if f and s[i]=="1":
        f = 0
        x.append(i)
    elif 1-f and s[i]=="0":
        f,num = 1,num+1
        y.append(i-1)
if x and x[0]: num+=1
if int(s[-1]): y.append(n-1)
if num<=k: print(n)
else:
    if x[0]: ans = y[k-1]+1
    if s[-1]=="0": ans = max(ans,n-x[-k])
    for i in range(len(y)-k): ans = max(y[i+k]-x[i]+1,ans)
    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

t = []
abs_t = []

cur = s[0]
cnt = 0
for ss in s:
    if cur == ss:
        cnt += 1
    else:
        sgn = 1 if cur == '1' else -1
        # 逆立ちでないなら-1
        t.append(cnt * sgn)
        abs_t.append(cnt)

        cur = ss
        cnt = 1
sgn = 1 if cur == '1' else -1
# 逆立ちでないなら-1
t.append(cnt * sgn)
abs_t.append(cnt)

M = len(t)

sgn_cnt = [0]
for tt in t:
    sgn_cnt.append(sgn_cnt[-1] + (1 if tt < 0 else 0))
# 反転が必要な箇所数の累積和

c_abst = [0]
for att in abs_t:
    c_abst.append(c_abst[-1] + att)

# print(t, abs_t, c_abst, sgn_cnt)

ans = 0
for i in range(M):
    ok = bisect_right(sgn_cnt, (K + sgn_cnt[i]))
    ok -= 1
    # print(ok, i, K + sgn_cnt[i])
    # print(c_abst)
    ans = max(ans, c_abst[min(ok, M)] - c_abst[i])
print(ans)

Submission status: Accepted

Solution code:
def handstand(N: int, K: int, S: str)->int:
    seq = [[], []]
    cur_c, cur_n = S[0], 0

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

    for c in S:
        if cur_c != c:
            seq[int(cur_c)].append(cur_n)
            cur_c = c
            cur_n = 0
        cur_n += 1
    else:
        seq[int(cur_c)].append(cur_n)

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

    if len(seq[0]) <= K:
        # 0 の領域が K こ以内なら全てひっくり返せる。
        return N

    cum = [sum(seq[0][:K]), sum(seq[1][:K+1])]
    max_up = sum(cum)

    for k in range(len(seq[0])-K):
        cum[0] += seq[0][k+K] - seq[0][k]
        cum[1] += seq[1][k+K+1] - seq[1][k]

        max_up = max(max_up, sum(cum))

    return max_up


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

Submission status: Accepted

Solution code:
N, K = [int(s) for s in input().split()]
S = input()
group0 = []
group1 = []
now = '1'
now_n = 0
for c in S:
    if c == now:
        now_n += 1
    else:
        if now == '1':
            group1.append(now_n)
        else:
            group0.append(now_n)
        now = c
        now_n = 1
if now == '1':
    group1.append(now_n)
else:
    group0.append(now_n)
    group1.append(0)

first = 0
last = min(K, len(group0))
now_group = sum(group0[first:last]) + sum(group1[first:last+1])
max_group = now_group
for i in range(last, len(group0)):
    now_group += group0[i] + group1[i+1] - group0[first] - group1[first]
    max_group = max(max_group, now_group)
    first += 1
print(max_group)

Submission status: Accepted

Solution code:
def int_raw():
    return int(input())


def ss_raw():
    return raw_input().split()


def ints_raw():
    return list(map(int, ss_raw()))


N, K = ints_raw()
S = [int(s) for s in raw_input()]
current = S[0]
count = 0
stand_array = []
reverse_array = []
if current == 0:
    reverse_array.append(0)
for s in S:
    if s == current:
        count += 1
    else:
        if current == 1:
            reverse_array.append(count)
        else:
            stand_array.append(count)
        count = 1
        current = 1 - current
if current == 1:
    reverse_array.append(count)
else:
    stand_array.append(count)
if current == 0:
    reverse_array.append(0)

if len(stand_array) <= K:
    print(N)
else:
    max_score = 0
    score = 0
    for i in range(K):
        score += stand_array[i]
        score += reverse_array[i]
    score += reverse_array[K]
    max_score = score
    for i in range(len(stand_array) - K):
        score -= stand_array[i]
        score -= reverse_array[i]
        score += stand_array[i + K]
        score += reverse_array[i + K + 1]
        max_score = max(score, max_score)
    print(max_score)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = str(input())
num = 0
nu = 0
lis = []
li = []
if s[0] == "0":
    li.append(0)
for i in range(len(s)):
    if s[i] == "0":
        if nu != 0:
            num = 1
            li.append(nu)
            nu = 0
        else:
            num += 1
    else:
        if num != 0:
            nu = 1
            lis.append(num)
            num = 0
        else:
            nu += 1
lis.append(num)
li.append(nu)
if len(lis) == len(li):
    li.append(0)
cou = 0
nn = max(0,k-len(lis))
for i in range(nn):
    lis.append(0)
    li.append(0)
ans = sum(lis[:k])+sum(li[:k+1])
num = sum(lis[:k])+sum(li[:k+1])
for i in range(len(lis)-k):
    num -= li[i]+lis[i]
    num += li[i+k+1]+lis[i+k]
    ans = max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
start=[0]
end=[]
bef=S[0]
if bef=='0':
    end.append(0)
for i in range(1,N):
    if S[i]!=bef:
        if bef=='0':
            start.append(i)
        else:
            end.append(i-1)
        bef=S[i]
if S[-1]=='1':
    end.append(N-1)
ans=0
for i in range(len(end)):
    if i-K<0:
        x=0
    else:
        x=start[i-K]
    ans=max(ans,end[i]-x+1)
if S[-1]=='0' and K!=0:
    if len(start)-K<0:
        x=0
    else:
        x=start[-1*K]
    ans=max(ans,N-x)
print(ans)

Submission status: Accepted

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

x = []
idx = 0
b = 1
while idx<n:
    st = idx
    while idx<n and int(s[idx])==b:
        idx += 1
    x.append(idx-st)
    st = idx
    b ^= 1

if b == 1:
    x.append(0)

ans = n
if len(x) > 2*k+1:
    ans = 0

    t = 0
    for i in range(2*k+1):
        t += x[i]
    ans = max(ans, t)

    for i in range(2*k+1, len(x), 2):
        t -= x[i - (2*k+1)]
        t -= x[i+1 - (2*k+1)]
        t += x[i]
        t += x[i+1]
        ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
s = input()

start = s[0]
arr = []
pre = start
cnt = 0
for x in s:
    if x == pre:
        cnt+=1
        continue
    else:
        pre = x
        arr.append(cnt)
        cnt = 1

arr.append(cnt)

if len(arr) == 1:
    print(arr[0])
    exit()

m = 0
if start == "1":
    now = sum(arr[:2*k+1])
    m = now
    for i in range(1, (len(arr)//2)-k+1):
        now = now - arr[2*i-1] - arr[2*i-2] + sum(arr[2*i+2*k-1:2*i+2*k+1]) 
        m = max(now, m)

else:
    m = sum(arr[:2*k])
    now = sum(arr[1:2*k+2])
    m = max(now, m)
    for i in range(1, ((len(arr)+1)//2)-k):
        now = now - arr[2*i] - arr[2*i-1] + sum(arr[2*i+2*k:2*i+2*k+2])
        m = max(now, m)
    
print(m)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
x = [0]
hoge = 1
for i in S:
    i = int(i)
    if i == hoge:
        x[-1] += 1
    else:
        hoge = (hoge+1)%2
        x.append(1)
x.append(0)
l = len(x)
hoge = 2*K+1
saka = [0]
if hoge > l:
    print(N)
else:
    for i in range(hoge):
        saka[0] += x[i]
    for i in range(int((l-hoge)/2)):
        saka.append(saka[i]-x[i*2]-x[i*2+1]+x[i*2+hoge]+x[i*2+1+hoge])
    print(max(saka))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
L=[]
c=0
for i in range(N):
  if c==0 and S[i]=="1":
    c=1
    s=i
  elif c==1 and S[i]=="0":
    c=0
    t=i-1
    L.append([s,t])
if c==1:
  L.append([s,N-1])
if len(L)<=K-1:
  ans=N
elif len(L)==K:
  if L[0][0]!=0 and L[-1][1]!=N-1:
    ans=max(L[-1][1]+1,N-L[0][0])
  else:
    ans=N
else:
  ans=0
  for i in range(len(L)-K):
    ans=max(ans,L[i+K][1]-L[i][0]+1)
  if L[0][0]!=0:
    ans=max(ans,L[K-1][1]+1)
  if L[-1][1]!=N-1:
    ans=max(ans,N-L[-K][0])
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = '1' + input() + '1'
s = 0
t = 0
k = 0
l = 0
while s < N:
  while s < N:
    s += 1
    if S[s] == '0' and S[s + 1] == '1':
      k += 1
    if k == K and S[s] == '1' and S[s + 1] == '0':
      break
  l = max(s - t, l)
  while t < s:
    t += 1
    if S[t] == '0' and S[t + 1] == '1':
      k -= 1
      break
print(l)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


def main():
    n,k = map(int,input().split())
    s = list(input())
    tank = []
    judge = True
    if s[0] == '0':
        judge = False
    cnt = 0
    for i in range(n):
        if judge:
            if s[i] == '0':
                tank.append(cnt)
                judge = False
                cnt = 0
            cnt += 1
        else:
            if s[i] == '1':
                tank.append(cnt)
                judge = True
                cnt = 0
            cnt += 1
        if i == n-1:
            tank.append(cnt)
    #print(tank)
    p = len(tank)
    if s[0] == '0' and (p+1)//2 <= k:
        print(n)
        exit()
    if p//2 <= k and s[0] == '1':
        print(n)
        exit()

    ans = 0
    res = 0
    if s[0] == '0':
        for j in range(2*k):
            res += tank[j]
        ans = res
        for j in range(2*k,p):
            if j == 2*k:
                res -= tank[0]
            elif j%2 == 0:
                res= res - tank[j-2*k] -tank[j-2*k-1]
            res += tank[j]
            ans = max(ans,res)

    else:
        for j in range(2*k+1):
            res += tank[j]
        ans = res
        for j in range(2*k+1,p):
            if j % 2 == 1:
                res = res- tank[j-2*k-1]-tank[j-2*k]
            res += tank[j]
            ans = max(ans,res)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ones = []
zeros = []
current = '1'
n = 0
for i in range(N):
    if S[i] == current:
        n += 1
    else:
        if current == '1':
            ones.append(n)
            current = '0'
        else:
            zeros.append(n)
            current = '1'
        n = 1
if current == '1':
    ones.append(n)
else:
    zeros.append(n)
    ones.append(0)

L = len(zeros)
if L <= K:
    print(N)
else:
    ans = sum(ones[:K+1]) + sum(zeros[:K])
    now = ans
    for i in range(L-K):
        now += (ones[i+K+1]+zeros[i+K]-ones[i]-zeros[i])
        ans = max(ans,now)
    print(ans)

Submission status: Accepted

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

runlengths = []  # 両脇を逆立ちの数字の連続数にする
if S[0] == "0":
    runlengths.append(0)

pre_s = S[0]
cnt = 1
for s in S[1:]:
    if pre_s != s:
        runlengths.append(cnt)
        pre_s = s
        cnt = 1
    else:
        cnt += 1

runlengths.append(cnt)
if S[-1] == "0":
    runlengths.append(0)

if len(runlengths) < K * 2 + 1:
    runlengths.extend([0]*((K*2+1)-len(runlengths)))

# print(runlengths)


con = sum(runlengths[0:K*2+1])
max_con = con
for e_new in range(K*2+2, len(runlengths), 2):
    s_old = e_new - (K*2+2)
    con = con - runlengths[s_old] - runlengths[s_old+1] +\
        runlengths[e_new-1] + runlengths[e_new]
    max_con = max(max_con, con)

print(max_con)

Submission status: Accepted

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

L = [[0, 0]]
re = S[0]
for i in range(1, len(S)):
  if S[i] != re:
    re = S[i]
    L[-1][1] = i
    L.append([i, 0])
l = len(L)
L[-1][1] = N

if S[0] == "0":
  z = (l // 2) + 1
else:
  z = (l + 1) // 2
  
if z <= K:
  print(N)
  exit()

ma = 0
if S[0] == "0":
  ma = max(ma, L[K * 2 - 1][1])
  s = 1
else:
  s = 0
if S[-1] == "0":
  ma = max(ma, N - L[-K * 2][0])

t = K * 2
for i in range(s, l - t, 2):
  ma = max(ma, L[t + i][1] - L[i][0])
print(ma)

Submission status: Accepted

Solution code:
# 1 <= N,K <= 10**5
# len(S) == N
N,K = map(int,input().split())
S = input()
#preprocess
neg = [0]
negSum = 0
pos = [0]
posSum = 0
value = 1
for i in range(N):
    c =S[i]
    if c == "1":
        posSum += 1
        if value == 0:
            neg.append(negSum)
            value = 1
    else:
        negSum += 1
        if value == 1:
            pos.append(posSum)
            value = 0
if value == 1:
    pos.append(posSum)
else:
    neg.append(negSum)
    pos.append(posSum)
# print(neg)
# print(pos)
L = len(neg)
#1 - K ... [i,min(L,i+K-1)] + [i,min(L+1,i+K)]
ans = pos[1]
for i in range(1,L):
    endI = min(L-1,i+K-1)
    # print(endI,i-1,endI+1,i-1)
    candidate = neg[endI] - neg[i-1] + pos[endI+1] - pos[i-1]
    ans = max(ans,candidate)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
s=input()
b=[0]
for i in range(n-1):
    if s[i]!=s[i+1]:
        b.append(i+1)
b.append(len(s))
if s[0]=='0':
    b.insert(0,0)
if s[-1]=='0':
    b.append(len(s))
ans=0
stride=k*2+1
if len(b)-stride<1:
    stride=len(b)-1
for i in range(0,len(b)-stride,2):
    ans=max(ans,b[i+stride]-b[i])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=input()
One,Zero=[],[]
cnt1,cnt0=0,0
for s in S:
    if s=='1':
        cnt1+=1
        if cnt0:
            Zero.append(cnt0)
            cnt0=0
    else:
        cnt0+=1
        if cnt1:
            One.append(cnt1)
            cnt1=0
if cnt1:
    One.append(cnt1)
if cnt0:
    Zero.append(cnt0)
if S[0]=='0':
    One=[0]+One
if S[-1]=='0':
    One=One+[0]
l=len(Zero)
if k>=l:
    ans=n
else:
    ans=sum(One[:k+1]+Zero[:k])
    prev=ans
    for i in range(l-k):
        tmp=prev-One[i]+One[i+k+1]-Zero[i]+Zero[i+k]
        ans=max(ans,tmp)
        prev=tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    S = input_raw[0]
    count_list = []
    s_list = []
    j = 0
    count = 1
    for i in range(1, N):
        if S[i] == S[i - 1]:
            count += 1
        else:
            count_list.append(count)
            s_list.append(S[i - 1])
            count = 1
    count_list.append(count)
    s_list.append(S[N - 1])
    n = len(count_list)
    count = 1
    sum_list = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        sum_list[i] = sum_list[i - 1] + count_list[i - 1]

    max_s = 0
    for i in range(1, n + 1):
        if s_list[i - 1] == "0":
            k = 2 * K
        else:
            k = 2 * K + 1
        max_s = max(sum_list[i] - sum_list[max(i - k , 0)], max_s)
    print max_s








if __name__ == '__main__':
    main()

Submission status: Accepted

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

if S[0] =='0':
  pre = '0'
  memo = {'0': [1], '1':[0]}
else:
  pre = '1'
  memo = {'0': [], '1':[1]}

for s in S[1:]:
  if s==pre:
    memo[s][-1] +=1
  else:
    pre = s
    memo[s].append(1)

if S[-1] =='0':
  memo['1'].append(0)
    
if len(memo['0'])<=K:
  print(len(S))
  exit()

window_sum = sum(memo['0'][:K] + memo['1'][:K+1])
answer = window_sum
for i in range(0, len(memo['0'])-K):
  window_sum = window_sum -memo['0'][i] - memo['1'][i] + memo['0'][i+K] + memo['1'][i+K+1]
  answer = max(answer, window_sum)

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
N, K = inpl()
S = input()

x = S[0]
A = []
B = []
tmp = 0
for s in S:
    if s == x:
        tmp += 1
    else:
        if x == "0":
            A.append(tmp)
        else:
            B.append(tmp)
        x = s
        tmp = 1

if tmp > 0:
    if s == "0":
        A.append(tmp)
    else:
        B.append(tmp)

ans = 0
if S[0] == "1":
    T = sum(A[:K]) + sum(B[:K+1])
    ans = max(ans, T)
    for i in range(len(A) - K):
        T += -A[i] + A[i+K] - B[i]
        if len(B) > i + K + 1:
            T += B[i+K+1]
        ans = max(ans, T)
    print(ans)
else:
    T = sum(A[:K]) + sum(B[:K])
    ans = max(ans, T)
    for i in range(len(A) - K):
        T += -A[i] + A[i+K] - (B[i-1] * (i!=0))
        if len(B) > i + K:
            T += B[i+K]
        ans = max(ans, T)
    print(ans)

Submission status: Accepted

Solution code:
import sys
import random
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n, k = map(int,input().split())
s = input().rstrip()
ans = []
if s[0] == "0":
    ans.append(0)
    mae = "0"
else:
    mae = "1"
b = 0
for i in range(n):
    if s[i] == mae:
        b += 1
    else:
        ans.append(b)
        if mae == "0":
            mae = "1"
        else:
            mae = "0"
        b = 1
else:
    if b:
        ans.append(b)
rui = [0]*(len(ans)+1)
for i in range(len(ans)):
    rui[i+1] = ans[i] + rui[i]
MAX = 0
if len(ans[1::2]) <= k:
    print(n)
    exit()
for i in range(len(ans)+1):
    try:
        if i %2 == 0:
            MAX = max(rui[i+2*k+1]-rui[i],MAX)
        else:
            pass
    except:
        if i %2 == 0:
            MAX = max(rui[len(ans)]-rui[i],MAX)    
print(MAX)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

# N個整数
n, k = list(map(int, input().split()))

s = input() + '2'

# 1整数
# n = int(input())

ret = 0


##この文字の次の0まで示す
def next0(l: int):
    if l >= n:
        return l
    l += 1
    while s[l] != '2' and s[l] != '0':
        l += 1
    return min(l, n)


##この文字の次の1まで示す
def next1(l: int):
    if l >= n:
        return l
    l += 1
    while s[l] != '2' and s[l] != '1':
        l += 1
    return min(l, n)


start = 0
end = 0
ret = 0
# まずendをKこ進める
end = next0(end)
for i in range(k):
    end = next1(end)
    end = next0(end)

ret = end - start
#print(start, end, ret)

while end < n:
    start = next1(next0(start))
    end = next0(next1(end))
    ret = max(ret, end - start)
    #print(start, end, ret)
print(ret)