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(map(int,input()))
s_list = list()
num = s[0]
temp_streak = 0
# temp_max = 0
# temp_sum = 0
[s_list.append(0) for i in range(1+s[0])]

for i in s:
    if i == num:
        temp_streak += 1
    else:
        s_list.append(temp_streak)
        temp_streak = 1
        num = i

s_list.append(temp_streak)
[s_list.append(0) for i in range(1+s[-1])]
# odd = len(s_list)%2
num_i = len(s_list) // 2 
# print(s_list)
temp_max = sum(s_list[0:min(k*2+1,len(s_list) + 1)])
temp_sum = temp_max
temp_max_debug = temp_max
# print(temp_max)
for i in range(1,max(num_i+1-k,1)):
    temp_sum = temp_sum - s_list[i*2-2] - s_list[i*2-1] + s_list[i*2+k*2-1] + s_list[i*2+k*2]
    temp_max = max(temp_max,temp_sum)
    # temp_max_debug = max(temp_max_debug,sum(s_list[i*2:i*2+k*2+1]))
print(temp_max)
# print(temp_max_debug)



#print(s_list)

Submission status: Accepted

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

if S.count('1') == N or S.count('0') == N:
  print(N)
  exit()

S += '2'
s = S[0]
L0 = []
if s == '0':
  L1 = [0]
else:
  L1 = []
c = 1
for i in range(1,N+1):
  if S[i] != s:
    if s == '0':
      L0.append(c)
    else:
      L1.append(c)
    s = S[i]
    c = 1
  else:
    c += 1
L1 += [0]
#print(L0)
#print(L1)

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

SL0 = [0 for _ in range(len(L0)+1)]
for i in range(1,len(L0)+1):
  SL0[i] = SL0[i-1] + L0[i-1]
SL1 = [0 for _ in range(len(L1)+1)]
for i in range(1,len(L1)+1):
  SL1[i] = SL1[i-1] + L1[i-1]

ans = 0
for i in range(len(L0)-K+1):
    #ans = max(ans,sum(L0[i:i+K])+sum(L1[i:i+K+1]))
    ans = max(ans,SL0[i+K]-SL0[i] + SL1[i+K+1]-SL1[i])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, S: str):
    seq = []
    if(S[0] == '0'): seq.append(0)
    f = S[0]
    c = 1
    for i in range(1, N):
        if(S[i] == f):
            c += 1
        else:
            seq.append(c)
            f = S[i]
            c = 1
    seq.append(c)
    
    rseq = [0] * (len(seq)+1)
    for i in range(1,len(seq)+1):
        rseq[i] = rseq[i-1] + seq[i-1]

    ans = 0
    # cumulative sum
    for i in range(len(rseq)):
        # print(ans, rseq[min(len(rseq)-1,i*2+2*K+2)], rseq[min(len(rseq)-1, i*2)])
        ans = max(ans, rseq[min(len(rseq)-1,i*2+2*K+1)] - rseq[min(len(rseq)-1, i*2)])


    # naive
    # for i in range(len(seq)):
    #     for j in range(K):
    #         # print(seq[i*2:i*2+2*K+1])
    #         ans = max(ans, sum(seq[i*2:i*2+2*K+1]))

    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s = input()
cnt = 0
d = s[0]
ss = []
for i in range(N):
  if s[i] == d:
    cnt += 1
  else:
    ss.append(cnt)
    cnt = 1
    d = s[i]
ss.append(cnt)
ss.append(0)
ss.append(0)
ss.append(0)

cs = [0]
if s[0]=="0":
  cs.append(0)
for x in ss:
  cs.append(cs[-1]+x)

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

Submission status: Accepted

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

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

count=0
for si in s:
  if count==0:
    flag = si
    count=1
  elif flag == si:
    count+=1
  else:        
    sp.append(count)
    flag = si
    count=1
if count>0:
  sp.append(count)
if s[-1]=='0':
  sp.append(0)

ss=[0]
ss.append(sp[0])
count = 0
for spi in sp[1:]:
  ss.append(ss[-1]+spi)  

ans = 0
for left in range(0,len(ss),2):
  right = left+2*k+1
  if right >= len(ss): #!!
    right = len(ss)-1
  ans = max(ans,ss[right]-ss[left])    

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
Nums = []
now = 1
now_cnt = 0
for i in range(N):
    if S[i] == str(now):
        now_cnt += 1
    else:
        Nums.append(now_cnt)  # S[0] = 0のとき、1の数は0なので、Numsの左に0が来る
        now = 1 - now
        now_cnt = 1
Nums.append(now_cnt)

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

Add = 2 * K + 1  # 足す要素数
sum_ = 0
sum_max = 0
sum_list = [0] * (len(Nums)+1)
for i in range(len(Nums)):  # 累積和
    sum_list[i+1] = sum_list[i] + Nums[i]

for i in range(0, len(Nums), 2):
    left = i
    right = min(i + Add, len(Nums))  # 指示はなくても良い
    sum_ = sum_list[right] - sum_list[left]
    sum_max = max(sum_, sum_max)

print(sum_max)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
Nums = []
now = 1
now_cnt = 0
for i in range(N):
    if S[i] == str(now):
        now_cnt += 1
    else:
        Nums.append(now_cnt)  # S[0] = 0のとき、1の数は0なので、Numsの左に0が来る
        now = 1 - now
        now_cnt = 1
Nums.append(now_cnt)

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

Add = 2 * K + 1  # 足す要素数
left = 0
right = 0
sum_ = 0
sum_max = 0

for i in range(0, len(Nums), 2):  # 尺取法
    Nextleft = i
    Nextright = min(i + Add, len(Nums))  # 指示はなくても良い
    while Nextleft > left:
        sum_ -= Nums[left]
        left += 1
    while Nextright > right:
        sum_ += Nums[right]
        right += 1
    sum_max = max(sum_, sum_max)

print(sum_max)

Submission status: Accepted

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

i = 0
count = 0
while i != len(S):
    if S[i] != S[i-1] and i != 0:
        X.append(count)
        Y.append(S[i-1])
        count = 1
    else:
        count += 1
    i += 1
X.append(count)
Y.append(S[-1])

ans = 0
zero_counter = 0
val = 0
j = 0 
for i in range(len(X)):
    if Y[i] == '0':
        zero_counter += 1
    val += X[i]
    while zero_counter > K:
        val -= X[j]
        if Y[j] == '0':
            zero_counter -= 1
        j += 1
    if ans < val:
        ans = val
print(ans)

Submission status: Accepted

Solution code:
def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, cs = 2*k, [l[0]]

    for i in range(1, len(l)):
        cs.append(cs[i-1]+l[i])
    a = cs[0]
    for i in range(0, len(l), 2):
        tmp = cs[min(i+r, len(l)-1)]-cs[i]+l[i]
        a = max(a, tmp)
    print(a)

if __name__ == "__main__":
    f_d()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 1
00010"""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """14 2
11101010110011"""
        output = """8"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """1 1
1"""
        output = """1"""
        self.assertIO(input, output)

def resolve():
    (N,K) = (int(i) for i in input().split())
    S=input()
    l=[]
    flg=False
    if S[0]=='0':
        l.append([0,0])
    for i in range(len(S)):
        if flg==True and S[i]=='0':
            l[-1].append(i)
            flg=False
        if flg==False and S[i]=='1':
            l.append([i])
            flg=True
    if S[-1]=='0':
        l.append([len(S),len(S)])
    else:
        l[-1].append(len(S))
    if K>=len(l)-1:
        print(len(S))
        return()

    print(max( [ l[i+K][1]-l[i][0] for i in range(len(l)-K)] ) )
       

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, a = 2*k+1, 0
    li = ri = tmp = 0
    for i in range(0, len(l), 2):
        nli, nri = i, min(i+r, len(l))
        while li<nli:
            tmp -= l[li]
            li += 1
        while ri<nri:
            tmp += l[ri]
            ri += 1
        a = max(a, tmp)
    print(a)

if __name__ == "__main__":
    f_d()

Submission status: Accepted

Solution code:
#D
from collections import deque
n,k=map(int,input().split())
s=input()
if n==1:
    print(1)
elif "1" not in s:
  	print(len(s))
else:
    a=deque([])
    if s[0]=="1":
        a.append([0])
    for i in range(1,n):
        if s[i-1:i+1]=="01":
            a.append([i])
        elif s[i-1:i+1]=="10":
            a[-1].append(i-1)
    if s[n-1]=="1":
        a[-1].append(n-1)
    if a[0][0]!=0:
        a.appendleft([0,0])
    if a[-1][1]!=n-1:
        a.append([n-1,n-1])
    if len(a)-1<=k:
        print(n)
    else:
        t=0
        for i in range(len(a)-k):
            t=max(t,a[i+k][1]-a[i][0]+1)
        print(t)

Submission status: Accepted

Solution code:
N, K = map(int,input().split(' '))
S = input()
S2=[]
key=S[0]
tmpcnt=1
if key=='0':
    S2.append(0)
S2.append(0)
S2.append(0)
for i in range(1,len(S)):
    if key!=S[i]:
        if key == '0':
            S2.append(-1*tmpcnt)
        else:
            S2.append(tmpcnt)
        key=S[i]
        tmpcnt=1
    else:
        tmpcnt+=1
if key == '0':
    S2.append(-1*tmpcnt)
    S2.append(0)
    S2.append(0)
else:
    S2.append(tmpcnt)
    S2.append(0)
    S2.append(0)
#print(S2)
max=0
tmp=S2[0]
maxj=len(S2)-1
for j in range(1,K*2+1):
    tmp+=abs(S2[min(0+j,maxj)])
    #print(S2[i],S2[min(i+j,maxj)])
if tmp >= max:
    max=tmp
    #print(tmp)

for i in range(2,len(S2),2):
    tmp-=abs(S2[i-1])
    tmp-=abs(S2[i-2])
    tmp+=abs(S2[min(i+j-1,maxj)])
    tmp+=abs(S2[min(i+j,maxj)])
    #print(i-1,i-2,i+j-1,i+j)
    #print(tmp)
    if tmp>= max:
        max=tmp
print(max)

Submission status: Accepted

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


human = []
humancount = []
for key, group in itertools.groupby(S):
    human.append(key)
    humancount.append(len(list(group)))

humancount_ac = [0] + list(itertools.accumulate(humancount))

ans = 0
j = 0
count = 0

for i in range(N):
    while j <= len(human)-1:
        if human[j] == "0" and count < K:
            count += 1
            j += 1
            ans = max(ans, humancount_ac[j] - humancount_ac[i])
        elif human[j] == "1":
            j += 1
            ans = max(ans, humancount_ac[j] - humancount_ac[i])
        else:
            if human[i] == "0":
                count -= 1
            break
print(ans)

Submission status: Accepted

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

if(s[0] == '0'):
  arr.append(0)
for i in range(n-1):
  if(s[i] != s[i+1]):
    arr.append(i+1)
arr.append(n)
if(s[-1] == '0'):
  arr.append(n)
    
width = 2*k + 1
len_arr = len(arr)

if(2*k >= len_arr):
  ans = arr[-1]
else:
  ans = arr[2*k]
  left = 2
  while True:
    if(left + width > len_arr):
      break
    tmp = arr[left + width - 1] - arr[left - 1]
    ans = max(ans, tmp)
    left += 2
print(ans)

Submission status: Accepted

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

bl = []
if S[0] == "0":
    bl.append(0)
bl.append(0)
for i in range(1, N):
    if S[i-1] != S[i]:
        bl.append(i)
bl.append(N)
bl.append(N)

nbl = len(bl)
m = [bl[i+2 * K+1] - bl[i] 
     for i in range(nbl - 2*K-1) if i%2 == 0]
if len(m) == 0:
    print(N)
else:
    print(max(m))

Submission status: Accepted

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

l = 0
r = 0
change = 0 if S[0] == '1' else 1
ans = 0
while l < N and r < N:
    #print(l, r, change)
    ans = max(ans, r-l+1)
    if r == N-1:
        break
    if S[r] == '0':
        r += 1
    else:
        if S[r+1] == '0':
            if change < K:
                change += 1
                r += 1
            else:
                if S[l] == '0' and S[l+1] == '1':
                    r += 1
                l += 1
        else:
            r += 1
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
tmp = 1
spl = []
for i in range(1,n):
  if s[i-1] == s[i]:
    tmp += 1
  else:
    spl.append(tmp)
    tmp = 1
spl.append(tmp)
#print(spl)
l = len(spl)
acu = [0]
for m in range(l):
  acu.append(acu[-1]+spl[m])
acu = [0] + acu + [acu[-1]]
#print(acu)
can = []
if s[0] == '0':
  st = 0
else:
  st = 1
while True:
  try:
    can.append(acu[st+2*k+1]-acu[st])
    st += 2
  except:
    break
try:
  print(max(can))
except:
  print(n)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = '0'+input()+'0'
Handstands = [(1,1)]
for i in range(1,n+2):
    if s[i-1]=='0' and s[i]=='1':
        left = i
    if s[i-1]=='1' and s[i]=='0':
        right = i
        Handstands += [(left,right)]
Handstands += [(n+1,n+1)]
if k<=len(Handstands)-1:
    ans = 0
    for i in range(len(Handstands)-k):
        ans = max(ans,Handstands[i+k][1]-Handstands[i][0])
    print(ans)
else:
    print(n)

Submission status: Accepted

Solution code:
def solve(N, K, S):
    X = [0]
    for i in range(1, N):
        if S[i-1] != S[i]:
            X.append(i)
    X.append(N)

    m = None
    for i in range(len(X)-1):
        j = i + 2 * K
        if S[X[i]] == '1':
            j += 1
        j = min(j, len(X)-1)
        #print("    ",repr(S[X[i]]), j, "m=%d"%(X[j]-X[i]),"X[%d]:%d-X[%d]"%(j,X[j],i))
        m = max(0 if m is None else m, X[j] - X[i])
    if m is None:
        return N
    return m

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

Submission status: Accepted

Solution code:
from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
t=r=sum(a[:k+1]+b[:k]) 
for w,x,y,z in zip(a,b,a[k+1:],b[k:]):
	t+=-w-x+y+z
	r=max(r,t)
print(r)

Submission status: Accepted

Solution code:
import math
N,K = map(int,input().split())
S = input()
seq = 1
v_seq = 1
down_list = []
count = 0
down_num = 0
ans = 0
chk = 0
for i in range(N-1):
    if S[i] == S[i+1]:
        seq += 1
        v_seq += 1
    elif S[i] == "0":
        down_list.append(seq)
        seq = 1
        v_seq += 1
        count += 1
        if count == K:
            chk = 1
    else:
        if chk == 2:
            v_ans = v_ans + v_seq-down_list[v_count]
            v_count += 1
            ans = max(ans,v_ans)
        v_seq = 1
        seq += 1
        if chk == 1:
            ans = i+1
            v_ans = i+1
            v_count = 0
            chk = 2
if ans == 0:
    print(N)
else:
    v_ans = v_ans + v_seq-down_list[v_count]
    print(max(ans,v_ans))

Submission status: Accepted

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

if '0' not in S:
    print(N)
    sys.exit()

S += '2'
count_lis = []
cnt_1 = 0
first_one = True
for n in range(N):
    if S[n] == '1':
        if first_one:
            tmp = n
            first_one = False
        cnt_1 += 1
        if S[n + 1] == '0' or n == N - 1:
            #始まったところ、終わるところ、何回1があるか
            count_lis.append([tmp, n, cnt_1])
            cnt_1 = 0
            first_one = True

length = len(count_lis)
ans = 0

if length >= K:
    if S[0] == '0':
        ans = max(count_lis[K - 1][1] + 1, ans)
    if S[N - 1] == '0':
        ans = max(N - count_lis[len(count_lis) - K][0], ans)
    for j in range(length - K):
        tmp_ans = count_lis[j + K][1] - count_lis[j][0] + 1
        #print(tmp_ans)
        if ans < tmp_ans:
            ans = tmp_ans
else:
    ans = N
#print(count_lis)
print(ans)

Submission status: Accepted

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

right = 0
res = 0
zero_area = 1 if s[0] == '0' else 0
for left in range(n):
    if left > 0:
        if s[left-1] == '0' and s[left] == '1':
            zero_area -= 1
    while right < n-1:
        if s[right] == '1' and s[right+1] == '0':
            if zero_area + 1 > k:
                break
            zero_area += 1
        right += 1
    res = max(res, right - left + 1)

print(res)

Submission status: Accepted

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

right = 0
res = 0
zero_area = 1 if s[0] == '0' else 0
for left in range(n):
    if left > 0:
        if s[left-1] == '0' and s[left] == '1':
            zero_area -= 1
    while right < n-1:
        if s[right] == '1' and s[right+1] == '0':
            if zero_area + 1 > k:
                break
            zero_area += 1
        right += 1
    res = max(res, right - left + 1)

print(res)

Submission status: Accepted

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

l = []
now = 1 # 今見ている数(1から見る配列を作りたいので1で初期化)
cnt = 0

# lには(1の個数),(0の個数),(1の個数),(0の個数),...(1の個数)という感じのリストを入れたい(両端が0から始まるとしても1が0こあるとしてカウントしたい)
for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now # 0と1を切り替える(now ^= 1でも良い)
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: # (1の個数),(0の個数),(1の個数),(0の個数),...(0の個数)となってしまっていたら最後に0を入れておく
    l.append(0)
#print(l)

ans = 0
width = 2 * K + 1

# 累積和
# 元のリストが[0, 1, 2, 3, 4, 5]の時に[0, 1, 2, 3, 4, 5, 6]のように個数は+1になる(つまり最初は0)
lsum = [0 for _ in range(len(l) + 1)] # len(l)+1個の要素
for i in range(len(l)): # 0からlen(l)まで
    lsum[i + 1] = lsum[i] + l[i]
#print(lsum)

for i in range(0, len(l), 2): # ここを2ごとにすることで1の個数を数えられる
    left = i
    right = min(i + width, len(l))
    tmp = lsum[right] - lsum[left] # [left, right)
    ans = max(ans, tmp)

"""
# しゃくとり法

# ①forループの外側にleft,rightを持っておく
left = 0
right = 0
tmp = 0 # [left, right)の総和

for i in range(0, len(l), 2):
    # ②次のleft,rightを計算する
    nextleft = i # 0,2,4,...
    nextright = min(i + width, len(l)) # 0+width,2+width,...

    # ③左端の移動
    while nextleft > left:
        tmp -= l[left]
        left += 1

    # ③右端の移動
    while nextright > right:
        tmp += l[right]
        right += 1

    ans = max(ans, tmp)
"""

"""
# 愚直に足し算を繰り返すとTLE

for i in range(0, len(l), 2): # ここを2ごとにすることで1の個数を数えられる
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): # leftからright-1まで
        tmp += l[j]
    ans = max(ans, tmp)
"""

print(ans)

Submission status: Accepted

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

l = []
now = 1 # 今見ている数(1から見る配列を作りたいので1で初期化)
cnt = 0

# lには(1の個数),(0の個数),(1の個数),(0の個数),...(1の個数)という感じのリストを入れたい(両端が0から始まるとしても1が0こあるとしてカウントしたい)
for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now # 0と1を切り替える(now ^= 1でも良い)
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: # (1の個数),(0の個数),(1の個数),(0の個数),...(0の個数)となってしまっていたら最後に0を入れておく
    l.append(0)
# print(l)

ans = 0
width = 2 * K + 1

left = 0
right = 0
tmp = 0 # [left, right)の総和
for i in range(0, len(l), 2):
    nextleft = i # 0,2,4,...
    nextright = min(i + width, len(l)) # 0+width,2+width,...
    while nextleft > left:
        tmp -= l[left]
        left += 1
    while nextright > right:
        tmp += l[right]
        right += 1
    ans = max(ans, tmp)

"""
# 愚直に足し算を繰り返すとTLE
for i in range(0, len(l), 2): # ここを2ごとにすることで1の個数を数えられる
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): # leftからright-1まで
        tmp += l[j]
    ans = max(ans, tmp)
"""

print(ans)

Submission status: Accepted

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

change = [0] # 開始地点も連続文字列の始点なので
for i, (a, b) in enumerate(zip(S,S[1:])):
    if a != b: # 01の切り替わりの個数を調べる
        change.append(i+1)

ans = 0
for i in range(len(change)):
    if S[change[i]] == "0":
        if i == 0:
            if 2*K >= len(change):
                print(N)
                exit()
            tmp = change[2*K]
        else:
            if i+2*K >= len(change):
                tmp = N-(change[i-1])
            else:
                tmp = (change[i+2*K] - 1) - (change[i-1] - 1)
        ans = max(ans, tmp)
    else:
        if i+2*K+1 >= len(change):
            tmp = N - change[i]
        else:
            #if i == 1:
            #print("qqqqq",len(change), i+2*K+1 )
            tmp = (change[i+2*K+1]-1) - (change[i]-1)
        ans = max(ans, tmp)
    #print("---",i, ans,  N - change[i])

print(ans)
#print(change)

Submission status: Accepted

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

previous = S[0]
counter = 1

new_S = []

#1の人が並んでいる個数 +整数、0の人が並んでいるとき -整数とする
#→同じ人が3人並んでいたら+3などと表記する

for i in range(1,N):
    if S[i] == previous:
        counter += 1

        if i == N-1:
            if previous == '0':
                counter *= -1
            new_S.append(counter)

    else:
        if previous == '0':
            counter *= -1

        new_S.append(counter)

        previous = S[i]
        counter = 1

        if i == N-1:
            if previous == '0':
                counter *= -1
            new_S.append(counter)

if S[0] == '1' and len(S) == 1:
    new_S = [1]
elif S[0] == '0' and len(S) == 1:
    new_S = [0]

#以下、尺取り法
length = len(new_S)
l = 0

score = 0
ans = 0
minus = 0

# #l,rの区間の間で-がK個となる区間を探せば良い
for r in range(length):

    if new_S[r] < 0:
        minus += 1

    score += abs(new_S[r])

    if minus > K:
        #次のマイナスが出てくるまで減らし続ける
        for i in range(l,r+1):
            l += 1
            score -= abs(new_S[i])
        
            if new_S[i] < 0:
                minus -= 1
                break

    ans = max(score,ans)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
Is = []
i = 0
while i < N:
  j = S.find("0", i)
  if j < 0: j = N
  k = S.find("1", j)
  if k < 0: k = N
  Is.append((i, j, k))
  i = k
Is.append((N, N, N))
#print(Is)
if len(Is) <= K:
  r = N
  print(r)
  exit()
rs = []
for i in range(len(Is)-K):
  r = Is[i+K][1]-Is[i][0]
  rs.append(r)
#print(rs)
r = max(rs)
print(r)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input()
ls = []
for i in range(N):
  if i != N-1 and s[i]!=s[i+1]:
    ls += [i]
length = len(ls)
ls += [N-1]*(2*K+2)
m = 0
if s[0]=='0':
  for i in range(0,length,2):
    x = ls[i+2*K+1]-ls[i]
    if x>m:
      m = x
  x = ls[2*K-1]+1
  if x>m:
    m = x
else:
  for i in range(1, length, 2):
    x = ls[i+2*K+1]-ls[i]
    if x>m:
      m = x
  x = ls[2*K]+1
  if x>m:
    m = x
print(m)

Submission status: Accepted

Solution code:
def to_cumsum(arr):
    """
    1次元配列を累積和の1次元配列に変換する
    """
    cumsum = 0
    new = list()
    for e in arr:
        cumsum += e
        new.append(cumsum)
    return new


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

# 連続する1の数、連続する0の数を交互に並べた配列を計算
# 両端に1がない場合は"0個の1"があるものとして、必ず両端は1を示す要素にしておく

nums = list()
if S.startswith('0'):
    nums.append(0)

cnt = 0
cur = S[0]
for c in S:
    if c == cur:
        cnt += 1
    else:
        nums.append(cnt)
        cnt = 1
        cur = '1' if cur == '0' else '0'
nums.append(cnt)

if S.endswith('0'):
    nums.append(0)

# 要素の和のうち最大のものを求めるので累積和を計算して高速化する
cumsum = to_cumsum(nums)

# 0, 2, 4,...番目から始まる2K + 1要素の和で最大のものを求める
l = -1
ans = 0
while l < len(cumsum):
    r = l + (2 * K) + 1
    if r >= len(cumsum):
        r = len(cumsum) - 1
    if l == -1:
        ans = cumsum[r]
    else:
        ans = max(ans, cumsum[r] - cumsum[l])
    l += 2
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(input())
S = list(map(int,S))
A = []
cnt1 = 0
for i in range(N):
    if S[i]==1:
        cnt1 += 1
    else:
        if cnt1>0:
            A.append(cnt1)
            cnt1 = 0
if S[N-1]==1:
    A.append(cnt1)
B = []
cnt0 = 0
for i in range(N):
    if S[i]==0:
        cnt0 += 1
    else:
        if cnt0>0:
            B.append(cnt0)
            cnt0 = 0
if S[N-1]==0:
    B.append(cnt0)
if S[0]==1:
    B.insert(0,0)
if S[-1]==1:
    B.append(0)
k = min(len(B),K)
a = sum(A[:k])+sum(B[:k])
d = a
for i in range(k,len(B)):
    if i==len(B)-1 and i-k-1>=0:
        d = d-A[i-k-1]+B[i]-B[i-k]
    elif i==len(B)-1 and i-k-1<0:
        d = d+B[i]-B[i-k]
    elif i==k:
        d = d+A[i]+B[i]-B[i-k]
    else:
        d = d+A[i]-A[i-k-1]+B[i]-B[i-k]
    a = max(a,d)
print(a)

Submission status: Accepted

Solution code:
n,k = map(int,input().split(" "))
s = list(input())
a = [1]
for i in range(1,n):
    if s[i] != s[i-1]:
        a.append(i+1)
m = len(a)
ans = 1
i = 1
for i in range(m):
    if s[a[i]-1] == "1":
        if 2*k + i +1 < m:        
            ans = max(ans,a[2*k+i+1]-a[i])
        else:
            ans = max(ans,n+1- a[i])
    else:
        if 2*k+i< m:        
            ans = max(ans,a[2*k+i]-a[i])
        else:
            ans = max(ans,n+1-a[i])
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input()) + [-1]
bw = [0] * N
ind = 0
for i in range(N):
  bw[ind] += S[i] == S[i + 1]
  if S[i] != S[i + 1]:
    bw[ind] += 1
    ind += 1
ind = 0
res = 0
cumsumbw = [0] + [bw[0]] + [0] * (N - 1)
for i in range(1, N):
  cumsumbw[i + 1] = cumsumbw[i] + bw[i]
if N - 2 * K <= 0:
  print(N)
  exit(0)
for i in range(N - 2 * K):
  if S[cumsumbw[i]] == "1":
    res = max(res, cumsumbw[i + 2 * K + 1] - cumsumbw[i])
  else:
    res = max(res, cumsumbw[i + 2 * K] - cumsumbw[i])
  #print(res)
print(res)
#print(bw)
#print(cumsumbw)

Submission status: Accepted

Solution code:
import numpy as np
if __name__ == '__main__':
    N, K = map(int, input().split())
    S = list(map(int, list(str(input()))))
    #S = list(np.array(S)*2 - 1)
    start = [1]
    for i in range(1, N):
        if S[i] != S[i-1]:
            start.append(i+1)
    X = []
    for i in range(len(start)):
        if S[start[i]-1] == 0:
            if i+2*K < len(start):
                X.append(start[i+2*K] -start[i])
            else:
                X.append(N+1 -start[i])
        else:
            if i+2*K+1 < len(start):
                X.append(start[i+2*K+1] -start[i])
            else:
                X.append(N+1 -start[i])
    print(max(X))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(map(int, input()))
j = 1
r = 0
t = []
for i in range(n):
  if s[i] == j:
    r += 1
  else:
    t.append(r)
    r = 1
    j ^= 1
t.append(r)
if j == 0:
  t.append(0)
if k >= (len(t) - 1) // 2:
  print(sum(t))
else:
  result = sum(t[:2 * k + 1])
  j = sum(t[:2 * k + 1])
  i = 2
  while i + 2 * k < len(t):
    j += t[i + 2 * k - 1] + t[i + 2 * k] - (t[i - 2] + t[i - 1])
    result = max(result, j)
    i += 2
  print(result)

Submission status: Accepted

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

streaks = []
c = s[0]
i = 1
count = 1
while True:
    if i == n:
        streaks.append(count)
        break
    if s[i] == c:
        i += 1
        count += 1
    else:
        streaks.append(count)
        c = s[i]
        i += 1
        count = 1

accs = [0]
for num in streaks:
    accs.append(accs[-1] + num)
if accs[-1] != n:
    accs.append(n)

flag = s[0] == '0'
res = []
for i in range(len(accs)):
    if flag:
        index = i + 2 * k
    else:
        index = i + 2 * k + 1
    index = min(index, len(accs) - 1)
    res.append(accs[index] - accs[i])
    flag = not flag

print(max(res))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()+'22'
change = []
cnt = 0
for i in range(1,n+2):
  if s[i] == s[i-1]:
    cnt += 1
  else:
    cnt += 1
    change.append(cnt)
    cnt = 0


l = len(change)
ans = [0]*(l)
zero = [0]*(2*k)
change.extend(zero)

if s[0] == '0':
  ans[0] = sum(change[0:2*k])
  for i in range(1,l):
    if i%2 == 1:
      ans[i] = ans[i-1]-change[i-1]+change[i+2*k-1]+change[i+2*k]
    else:
      ans[i] = ans[i-1]-change[i-1]
else:
  ans[0] = sum(change[0:2*k+1])
  for i in range(1,l):
    if i%2 == 1:
      ans[i]= ans[i-1] -change[i-1]
    else:
      ans[i]= ans[i-1]-change[i-1]+change[i+2*k-1]+change[i+2*k]
    
print(max(ans))

Submission status: Accepted

Solution code:
#20:03
n,k = map(int,input().split())
s = input()
if s[0] == '1':
  can01 = [0]
  can10 = []
else:
  can01 = [0]
  can10 = [0]
for i in range(1,n):
  if s[i-1] == '0' and s[i] == '1':
    can01.append(i)
  elif s[i-1] == '1' and s[i] == '0':
    can10.append(i)
if s[n-1] == '1':
  can10.append(n)
else:
  can10.append(n)
  can01.append(n)
#print(can01,can10)
can01 = [0] * k + can01
can10 = can10 + [n] * k
#print(can01,can10)
ans = []
for i in range(len(can10)):
  ans.append(can10[i] - can01[i])
print(max(ans))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
l = 1
w = 0
a = []
for c in s :
    if l^int(c) :
        l = int(c)
        a.append(w)
        w = 1
    else :
        w += 1
else :
    a.append(w)

m = 2*k+1
ans = [sum(a[0:m])]
i = 2
while i+m <= len(a) :
    ans.append(-sum(a[i-2:i])+ans[-1]+sum(a[i+m-2:i+m]))
    i += 2
else :
    ans.append(-sum(a[i-2:i])+ans[-1]+sum(a[i+m-2:]))

print(max(ans))