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:
# coding: utf-8
# Your code here!

n,k=map(int,input().split())
s=input()
pre=s[0]
cnt=1
st=[]
if s[0]=='0':
    st.append(0)
for i in range(1,n):
    cur=s[i]
    if cur==pre:
        cnt+=1
    else:
        st.append(cnt)
        cnt=1
    pre=cur
if cnt!=0:
    st.append(cnt)
if s[-1]=='0':
    st.append(0)
#print(n,k,s,st)

ac=[]
pre=0
for i in st:
    pre+=i
    ac.append(pre)

ans=0
if 2*k+1>=len(st):
    ans=n
else:
    ans=ac[2*k]
    for i in range(2,len(st)-2*k,2):
        #print(i,i+2*k)
        ans=max(ans,ac[i+2*k]-ac[i-1])
print(ans)

Submission status: Accepted

Solution code:
'''
WA
'''
n,k = map(int,input().split()) 
t = list(str(input()))
t = [int(s) for s in t]
last = t[0]
temp_c = 0
s = []
con_c = 0
temp_con_c = 0
corrent_p = 0
sum_t = []
for i in range(n):
    if last == t[i]:
        temp_c += 1
    else:
        last = t[i]
        s.append(temp_c)
        temp_c = 1
s.append(temp_c)
if t[n-1] == 0:
    s.append(0)
l = len(s)
if k*2 <= l:
    sum_t.append(0)
    for i in range(l):
        sum_t.append(sum_t[i]+s[i])
    l = len(sum_t)
    if t[0] == 0:
        for i in range(l-k*2-1):
            if i%2 == 0:
                temp_con_c = sum_t[i+k*2]-sum_t[i]
            else:
                temp_con_c = sum_t[i+k*2+1]-sum_t[i]
            if temp_con_c > con_c:
                con_c = temp_con_c
    else:
        for i in range(l-k*2-1):
            if i%2 ==0:
                temp_con_c = sum_t[i+k*2+1]-sum_t[i]
            else:
                temp_con_c = sum_t[i+k*2]-sum_t[i]
            if temp_con_c > con_c:
                con_c = temp_con_c
else:
    con_c = n

print(con_c)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math


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

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

if cnt!=0:
    Nums.append(cnt)

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

#累積和
"""
Sums = [0]
tmp = 0
for i in range(len(Nums)):
    tmp += Nums[i]
    Sums.append(tmp)

ans = 0
Add = 2*K+1
for i in range(len(Sums)):
    if i%2==0:
        left = i
        right = min(i+Add,len(Sums)-1)
        tmp = Sums[right]-Sums[left]
        ans = max(tmp,ans)
"""
# 尺取り法
ans = 0
add = 2*K+1
left = 0
right = min(0+add,len(Nums))
pre = sum(Nums[left:right])
ans = pre
for i in range(len(Nums)-add):
    if i%2==0:
        left = i
        right = min(i+add,len(Nums)-1)
        pre += sum(Nums[right:right+2])-sum(Nums[left:left+2])
        ans = max(pre,ans)

print(ans)

Submission status: Accepted

Solution code:
# 良さげだけどバグが取れない！！！！


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = read()[:-1]
sum_0 = [0]
# 0のブロックの累積和を作成する
#  1 1 0 1 0 0 1だったら
# 0 0 0 1 1 2 2 2みたいな
now = '1'
for s_next in S:
    if s_next == '0' and now == '1':
        sum_0.append(sum_0[-1] + 1)
    else:
        sum_0.append(sum_0[-1])
    now = s_next

sum_0_2 = [0]
#  1 1 0 1 0 0 1だったら
# 0 0 0 1 1 1 2 2みたいな
# もし0で終わっていたら後ろに追加する。
for s_now, s_next in zip(S[:-1], S[1:]):
    if s_next == '1' and s_now == '0':
        sum_0_2.append(sum_0_2[-1] + 1)
    else:
        sum_0_2.append(sum_0_2[-1])

if S[-1] == '0':
    sum_0_2.append(sum_0_2[-1] + 1)
else:
    sum_0_2.append(sum_0_2[-1])

# print(S)
# print(sum_0)
# print(sum_0_2)

# [left,right)で考える
left = 0
right = 1
ans = 1  # 解初期値

# right-leftが答え
# sum_0[right]-sum0[left]がKを超えたらleftを進める
# print(sum_0)
# しゃくとり法で溶けそうでは？
for left in range(N - 1):
    while right < N:
        nextright = right+1
        # ここにバグの原因がここにあった。半端な00..00の途中から半端な00..00の途中までの引き算は正しく行われない
        if sum_0[nextright] - sum_0_2[left] > K:
            break
        right += 1
    #print(right, right < N)
    ans = max(ans, right - left)  # 大きい方に更新
    #print(left, right, ans, sum_0[nextright] - sum_0_2[left])

print(ans)

Submission status: Accepted

Solution code:

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

ones = []
t = 0
for i in range(N):
    if i == 0:
        t += 1
        pass
    elif (S[i - 1] != S[i]):
        ones.append(t)
        t = 1
    else:
        t += 1
ones.append(t)

if S[0] == '0':
    t = ones
    ones = [0]
    ones.extend(t)

res = 0
if len(ones) >= (2 * K + 1):
    for k in range(2 * K + 1):
        res += ones[k]
else:
    print(sum(ones))
    res = -1

ans = res
if res >= 0:
    for i in range(2 * K + 1, len(ones), 2):
        res += ones[i]
        if i + 1 < len(ones):
            res += ones[i + 1]

        res -= ones[i - 2 * K] + ones[i - 2 * K - 1]
        if ans < res:
            ans = res
    print(ans)

Submission status: Accepted

Solution code:
import sys

N, K = [int(x) for x in input().split()] # N:Sの長さ K:操作を行える回数の最大値
S = [int(x) for x in list(input())] # S:0と1から成る列
index = [0] # index:Sにおいて0と1が切り替わる部分の添字を集めたリスト
length = [0] # length:1が連続して並んでいる長さの最大値の候補を集めたリスト
zeros = 0 # zeros:Sにおいて0が連続して並んでいる箇所がいくつあるか

for i in range(0, len(S) - 1): # indexの要素を取得
    if S[i] != S[i + 1]: # 0と1の変わり目を探索
        index.append(i + 1) 

if S[0] == 0: # Sが0から始まる場合
    
    for i in range(len(index)): # zerosの値を取得
        if len(index) % 2 == 0: # indexの長さが偶数である場合
            zeros = int(len(index) / 2)
        else: # indexの長さが奇数である場合
            zeros = int((len(index) + 1) / 2) 
            
    for i in range(len(index)): # max(length)の初期値を取得
        if S[len(S) - 1] == 0: # Sが0で終わっている場合
            if i % 2 == 1:
                length.append(index[i + 1] - index[i])
        else: # Sが1で終わっている場合
            if (i % 2 ==1 and (i + 1) < len(index)):
                length.append(index[i + 1] - index[i])
            elif (i % 2 ==1 and (i + 1) == len(index)): # 最後の1の連続を処理
                length.append((len(S) - 1) - index[i] + 1)

    for i in range(len(index)): # Sのindex[i]番目を左端としたときの1の連続回数の最大値をそれぞれ求める
        if K >= zeros: # Kがzeros以上なら0の連続を全て1に置き換えて終了
            print(len(S))
            sys.exit()
        
        elif i + (2 * K) <= (len(index) - 1): # 添字が飛び出ないように注意（飛び出るようなやつはそもそも最大値の候補にならない）
            if i % 2 == 0: # 左端が0の場合
                length.append(index[(i + (2 * K) - 1) + 1] - index[i])
            else: # 左端が1の場合
                if i + (2 * K) < (len(index) - 1):
                    length.append(index[i + (2 * K) + 1] - index[i])
                elif i + (2 * K) == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)
        elif (i + (2 * K) == len(index) and i % 2 == 1):
            length.append(len(S) - index[i])
                
                
    print(max(length))
    sys.exit()

else: # Sが1から始まる場合
    
    for i in range(len(index)): # zerosの値を取得
        if len(index) % 2 == 0: # indexの長さが偶数である場合
            zeros = int(len(index) / 2)
        else: # indexの長さが奇数である場合
            zeros = int((len(index) - 1) / 2) 
            
    for i in range(len(index)): # max(length)の初期値を取得
        if S[len(S) - 1] == 0: # Sが0で終わっている場合
            if i % 2 == 0:
                length.append(index[i + 1] - index[i])
        else: # Sが1で終わっている場合
            if (i % 2 ==0 and (i + 1) < len(index)):
                length.append(index[i + 1] - index[i])
            elif (i % 2 ==0 and (i + 1) == len(index)): # 最後の1の連続を処理
                length.append((len(S) - 1) - index[i] + 1)

    for i in range(len(index)): # Sのindex[i]番目を左端としたときの1の連続回数の最大値をそれぞれ求める
        if K >= zeros: # Kがzeros以上なら0の連続を全て1に置き換えて終了
            print(len(S))
            sys.exit()
        
        elif i + (2 * K) <= (len(index) - 1): # 添字が飛び出ないように注意（飛び出るようなやつはそもそも最大値の候補にならない）
            if i % 2 == 0: # 左端が1の場合
                if i + (2 * K) < (len(index) - 1):
                    length.append(index[i + (2 * K) + 1] - index[i])
                elif i + (2 * K) == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)
                
            else: # 左端が0の場合
                length.append(index[(i + (2 * K) - 1) + 1] - index[i])
        elif (i + (2 * K) == len(index) and i % 2 == 0):
            length.append(len(S) - index[i])

                
    print(max(length))
    sys.exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, S):
    s1 = list(map(lambda x: len(x), filter(lambda x: x != '', S.split('0'))))
    s0 = list(map(lambda x: len(x), filter(lambda x: x != '', S.split('1'))))
    if len(s0) <= K:
        return N

    if S[0] == '0':
        s1.insert(0, 0)
    if S[-1] == '0':
        s1.append(0)

    q = deque()
    q.append(s1.pop())
    q.append(s0.pop())
    q.append(s1.pop())
    tmp = sum(q)
    ans = tmp
    while s1 or s0:
        if len(q) >= 2*K + 1:
            tmp -= q.popleft()
            tmp -= q.popleft()
        q.append(s0.pop())
        tmp += q[-1]
        q.append(s1.pop())
        tmp += q[-1]
        ans = max(ans, tmp)

    return ans


def main():
    N, K = read_int_n()
    S = read_str()
    print(slv(N, K, S))

    # N = 20
    # K = random.randint(1, 10)
    # S = ''.join(random.choices('01', k=N))
    # rS = ''.join(['0' if c == '1' else '1' for c in S])
    # print(max(slv(N, K, S), slv(N, K-1, rS)))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = read()[:-1]


# 偶数番目に0の個数を格納するようなデータ構造を構築する
num_cnts = []
now = '1'  # 0から考慮する
cnt = 0
for s in S:
    if s == now:
        cnt += 1
    if s != now:  # もしいまカウントしている文字と異なったらカウントを格納して、カウントをリセットする。
        num_cnts.append(cnt)
        now = s
        cnt = 1
num_cnts.append(cnt)
# もしSが0で終わっていたら0個の1を付け足す
if S[-1] == '0':
    num_cnts.append(0)

assert len(num_cnts) % 2 == 1, '奇数個じゃない！'

# しゃくとり法で実装
add = min(2*K+1, len(num_cnts))  # Kで指定するよりも短い場合はそっちに合わせる
ans = 1

# forの外にleft, rightを持つ
left = 0
right = 0
tmp = 0  # num_cnt[left:right]のsum

# しゃくとりしながら最大長の探索
for next_left in range(0, len(num_cnts) - add + 1, 2):
    # 次のleft,rightを計算する #今回はあまりしゃくとりのありがたみがない
    next_left = next_left  # あえてこう書いてる
    next_right = next_left+add

    # 左端を移動する (左側の移動によって減る分を計算する)
    while (next_left > left):
        tmp -= num_cnts[left]
        left += 1

    # 右端を移動する
    while (next_right > right):
        tmp += num_cnts[right]
        right += 1

    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
block = []
prev = 1
cnt = 0

for s in S:
    if str(prev) != s:
        prev = 1 - prev
        block.append(cnt)
        cnt = 1
    else:
        cnt += 1
else:
    if cnt != 0:
        block.append(cnt)
if len(block) %2 == 0:
    block.append(0)

length = 2 * K + 1
left = 0
right = min(length, len(block))
tmp = sum(block[left:right])
ans = tmp

for i in range(2,len(block),2):
    new_left = left + 2
    tmp -= sum(block[left:new_left])
    left = new_left
    new_right = min(right+2, len(block))
    tmp += sum(block[right:new_right])
    right = new_right
    ans = max(tmp, ans)
print(ans)

Submission status: Accepted

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

num = s.replace('10', '1,0')
num = num.replace('01', '0,1').split(',')
num = list(map(len, num))

if s[0] == '0':
    num.insert(0, 0)
if s[-1] == '0':
    num.append(0)

left = 0
right = 2*k + 1
length = sum(num[left:right])
ans = length
for i in range(2, len(num)-k, 2):
    length -= sum(num[left:left+2])
    left = i
    right = i + 2*k + 1
    length += sum(num[right-2:right])
    ans = max(ans, length)
    
print(ans)

Submission status: Accepted

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = read()[:-1]


# 偶数番目に0の個数を格納するようなデータ構造を構築する
num_cnts = []
now = '1'  # 0から考慮する
cnt = 0
for s in S:
    if s == now:
        cnt += 1
    if s != now:  # もしいまカウントしている文字と異なったらカウントを格納して、カウントをリセットする。
        num_cnts.append(cnt)
        now = s
        cnt = 1
num_cnts.append(cnt)
# もしSが0で終わっていたら0個の1を付け足す
if S[-1] == '0':
    num_cnts.append(0)

assert len(num_cnts) % 2 == 1, '奇数個じゃない！'

# 累積和で実装
from itertools import accumulate
num_accums = [0]+list(accumulate(num_cnts))

# 最大長の探索
add = min(2*K+1, len(num_cnts))  # Kで指定するよりも短い場合はそっちに合わせる
ans = 1

# print(num_cnts)
for left in range(0, len(num_cnts) - add+1, 2):
    right = left + add
    ans = max(ans, num_accums[right] - num_accums[left])
    # print(left, right, ans)

print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math


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

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

if cnt!=0:
    Nums.append(cnt)

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

#累積和
Sums = [0]
tmp = 0
for i in range(len(Nums)):
    tmp += Nums[i]
    Sums.append(tmp)
# print(Nums)
# print(Sums)
ans = 0
Add = 2*K+1
for i in range(len(Sums)):
    if i%2==0:
        left = i
        right = min(i+Add,len(Sums)-1)
        tmp = Sums[right]-Sums[left]
        ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
#ABC124 D
N, K = list(map(int, input().split()))
S = list(input())
ones = [0]
zeros = []
flag = '1'
for s in S:
    if s == '1':
        if flag == '1':
            ones[-1] += 1
        else:
            ones.append(1)
    else:
        if flag == '1':
            zeros.append(1)
        else:
            zeros[-1] += 1
    flag = s
ones.append(0)

tmp = sum(ones[0:K+1]) + sum(zeros[0:K])
ans = tmp
for i in range(len(zeros) - (K + 1) + 1):
    tmp = tmp + ones[i + K + 1] + zeros[i + K] - ones[i] -zeros[i]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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

#K回範囲を選択して反転、を繰り返し、1の連続数を最大にする
#連続した0を１度しか含まないK+1個の1の連続を探して範囲を出力する……？

change = [0]
for i in range(1,N):
    if S[i] == '1' and S[i-1] != '1':
        change.append(i)
    elif S[i] == '0' and S[i-1] != '0':
        change.append(i)

result = 0
for i, point in enumerate(change):
    if S[point] == '1':
        if i + 2 + K*2 > len(change):
            if result < N - point:
                result = N - point
            break
        if result < change[i + 1 + K*2] - 1 - point:
            result = change[i + 1 + K*2] - 1 - point
    else:
        if i + 1 + K*2 > len(change):
            if result < N - point:
                result = N - point
            break
        if i == 0:
            result = change[i + K*2]
        if result < change[i + K*2] - change[i-1]:
            result = change[i + K*2] - change[i-1]
print(result)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
S = input()
lstS = list(S)
block = [0]

cnt = 1
for i in range(len(S)):
    if S[i:i+1] == S[i+1:i+2]:
        cnt += 1
    else:
        block.append(cnt)
        cnt = 1
block.append(0)

acc = [0, 0]
for i in range(1, len(block)):
    wa = acc[-1]+block[i]
    acc.append(wa)

if S[0] == '0':
    start = 0
else:
    start = 1
end = len(acc) - (2*K+1)

max = 0
for i in range(start, end, 2):
    if max < acc[i+(2*K+1)] - acc[i]:
        max = acc[i+(2*K+1)] - acc[i]

if start >= end:
    max = N

if len(S) == 1:
    if K == 0 and S =='0':
        max = 0
    else:
        max = 1

print(max)

Submission status: Accepted

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


#n, k = 5, 3
#s = "00010"

m = 0
cur_s = cur_e = 0

while True:
  while cur_e < n and s[cur_e] == '1':
    cur_e+=1
  
  if k <= 0 or cur_e >= n:
    wm = cur_e - cur_s
    if wm > m:
      m = wm
      
    if cur_e >= n:
      break
 
    while cur_s < n and s[cur_s] == '1':
      cur_s+=1
    while cur_s < n and s[cur_s] == '0':
      cur_s+=1
    k+=1

  if k > 0:
    while cur_e < n and s[cur_e] == '0':
      cur_e+=1
    k-=1
    
print(m)

Submission status: Accepted

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

def readInts():
  return [int(s) for s in input().split(" ")]

def solve(N, K, S):
  chunks = []
  current = '1'
  count = 0
  for i, c in enumerate(S):
    if c != current:
      chunks.append(count)
      current = '0' if current == '1' else '1'
      count = 0
    count += 1
  chunks.append(count)
  if current == '0':
    chunks.append(0)

  if len(chunks) < 2 * K + 1:
    return N

  cSums = [0 for _ in range(len(chunks) + 1)]
  for i, c in enumerate(chunks):
    cSums[i + 1] = cSums[i] + c

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

  return ans

def main():
  N, K = readInts()
  S = input()

  print(solve(N, K, S))

if __name__ == "__main__":
  main()

Submission status: Accepted

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

current_length = 1
sections = []  # (start_i, end_i)
current_section = (S[0], 1)

max_length = 0

k = 0


# def display_section(sections, current_section):
#     a = sections[:]
#     b = current_section[:]
#     a += b
#     s = ''
#     for section in a:
#         s += section[0] * section[1]
#     return s


for i in range(1, len(S)):
    # t = display_section(sections, [current_section, (S[i], 1)])
    # print(t)
    if S[i - 1] == S[i]:
        current_section = (S[i], current_section[1] + 1)
        current_length += 1
    else:
        if current_section[0] == '0':
            if len(sections) > 0 and sections[-1][0] == '1':
                pop = sections.pop(-1)
                sections.append((0, pop[1] + current_section[1]))
            else:
                sections.append(current_section)
            k += 1
            if k > K:
                current_length -= sections[0][1]
                sections.pop(0)
        else:
            sections.append(current_section)

        if current_length > max_length:
            max_length = current_length

        current_section = (S[i], 1)
        current_length += 1

print(max_length)

Submission status: Accepted

Solution code:
N, k = map(int, input().split())                                                                               
s = input()
l, accum = len(s), []
zeros, ones = [], []
if s[0] == '0':
    ones = [0]
i = 0
while i < l:
    ch = s[i]
    if ch == '0':
        count = 0
        while i < l and s[i] == ch:
            count += 1
            i += 1
        zeros.append(count)
    elif ch == '1':
        count = 0
        while i < l and s[i] == ch:
            count += 1
            i += 1
        ones.append(count)
mx = sum(zeros[:k]) + sum(ones[:k+1])
ones+=[0]
for i in range(1, len(zeros)): zeros[i] += zeros[i-1]
for i in range(1, len(ones)): ones[i] += ones[i-1]
for i in range(1, len(zeros)-k+1):
    mx = max(zeros[k+i-1] + ones[k+i] - zeros[i-1] - ones[i-1], mx)
print(mx)

Submission status: Accepted

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

def press(array):
    pressed = []
    cnts = []
    remark = array[0]
    cnt = 0
    for i in range(len(array)):
        cnt += 1
        if i == N-1:
            pressed.append(remark)
            cnts.append(cnt)
        elif S[i] != S[i+1]:
            pressed.append(remark)
            cnts.append(cnt)
            remark = S[i+1]
            cnt = 0
    return pressed,cnts

pressed, cnts = press(list(S))
if pressed[0] == "0":
    pressed = ["1"] + pressed
    cnts = [0] + cnts
if pressed[-1] == "0":
    pressed = pressed + ["1"]
    cnts = cnts + [0]

acc = [0]*(len(cnts)+1)
for i in range(len(cnts)):
    acc[i+1] = acc[i] + cnts[i]

ans = 0

for l in range(0,len(cnts),2):
    r = min(l + 2*K,len(acc)-2)
    res = acc[r+1] - acc[l]
    ans = max(ans,res)

print(ans)

Submission status: Accepted

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

one_list = []
zero_list = []

cur_char = S[0]
char_num = 0
for i in range(N):
    if S[i] == cur_char:
        char_num += 1
    else:
        if cur_char == '0':
            zero_list.append(char_num)
        else:
            one_list.append(char_num)
        cur_char = S[i]
        char_num = 1
if cur_char == '0':
    zero_list.append(char_num)
else:
    one_list.append(char_num)

len_zero_list = len(zero_list)
len_one_list = len(one_list)
# print(len_one_list)
# print(len_zero_list)

cont_length_list = []

if K >= len(zero_list):
    ans = N
else:
    if S[0] == '1':
        tmp_length = sum(one_list[:K+1])+sum(zero_list[:K])
        cont_length_list.append(tmp_length)
        for i in range(min(len_zero_list,len_one_list)-K):
            if K+1+i<len_one_list:
                tmp_length += one_list[K+1+i]+zero_list[K+i]
            else:
                tmp_length += zero_list[K+i]
            tmp_length -= one_list[i]+zero_list[i]
            cont_length_list.append(tmp_length)
        # print(cont_length_list)
    else:
        tmp_length = sum(one_list[:K])+sum(zero_list[:K])
        cont_length_list.append(tmp_length)
        if K == len_one_list:
            tmp_length+=zero_list[K]
            tmp_length -= zero_list[0]
            cont_length_list.append(tmp_length)
        if K < len_zero_list-1:
            tmp_length += zero_list[K]+one_list[K]
            tmp_length -= zero_list[0]
            cont_length_list.append(tmp_length)
            for i in range(1, len_zero_list-K):
                if K+i<len_one_list and K+i < len_zero_list:
                    tmp_length += one_list[K+i]+zero_list[K+i]
                else:
                    tmp_length += zero_list[K+i]
                tmp_length -= one_list[i-1]+zero_list[i]
                cont_length_list.append(tmp_length)
        # print(cont_length_list)
    # print(cont_length_list)
    ans = max(cont_length_list)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input().replace('\n', '')


def solve(S, K):
    record = []
    temp = []
    for i in range(len(S) - 1):
        if S[i:i+2] == '01':
            temp.append(i + 1)
        elif S[i:i+2] == '10':
            if not temp: temp = [0, i]
            else: temp.append(i)
            record.append(temp)
            temp = []
    if len(temp) > 0:
        temp.append(len(S) - 1)
        record.append(temp)
    if S[0] == '0':
        record = [[0, 0]] + record
    if S[-1] == '0':
        record = record + [[len(S) - 1, len(S) - 1]]
    if len(record) <= K + 1: return(len(S))
    else:
        cnt = 0
        for i in range(len(record) - K):
            cnt = max(cnt, record[i + K][1] - record[i][0] + 1)
        return(cnt)
print(solve(S, K))

Submission status: Accepted

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

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

if S[0]=='0':
    L.insert(0,0)
if S[-1]=='0':
    L.append(N)

max_r = 0
step = K*2+1
if len(L)-step<1:
    step=len(L)-1
for i in range(0, len(L)-step,2):
    max_r = max(max_r, L[i+step]-L[i])

print(max_r)