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 -*-

def solve():
    N, K = list(map(int, input().split(" ")))
    S = input()

    # 累積和で解く
    i = 0
    ruiseki = [0]
    while True:
        if i >= N:
            break
        
        num = 0
        if S[i] == "1":
            while i < N and S[i] == "1":
                num += 1
                i += 1
            ruiseki.append(num + ruiseki[-1])
        else:
            while i < N and S[i] == "0":
                num += 1
                i += 1
            ruiseki.append(num + ruiseki[-1])

    import math
    if S[0] == "1":
        zero_num = math.floor((len(ruiseki)-1)/2)
    else:
        zero_num = math.ceil((len(ruiseki)-1)/2)

    if K >= zero_num:
        print(ruiseki[-1])
        return

    ans = 0
    if S[0] == "1":
        for i in range(2, len(ruiseki), 2):
            end = i + 2*(K-1)
            if end >= len(ruiseki):
                break
            if end+1 < len(ruiseki):
                # 後ろが"1"のとき
                end += 1

            ans = max(ruiseki[end]-ruiseki[i-2], ans)

    else:
        for i in range(1, len(ruiseki), 2):
            end = i + 2*(K-1)
            if end >= len(ruiseki):
                break
            if end+1 < len(ruiseki):
                end += 1

            if i-2 >= 0:              
                ans = max(ruiseki[end]-ruiseki[i-2], ans)
            else:
                ans = max(ruiseki[end]-ruiseki[i-1], ans)

    print(ans)            




if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

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

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

left = defaultdict(int)
right = defaultdict(int)
index = 0
for i in range(1, N):
    if S[i-1] == 0 and S[i] == 1:
        right[index] = i
        index += 1
    elif S[i-1] == 1 and S[i] == 0:
        left[index] = i-1

    if i == N-1:
        if S[i] == 0:
            right[index] = i
            left[index+1] = i
        if S[i] == 1:
            left[index] = i

ans = 0
for ind in range(index+1):
    a = left[ind+1] - right[ind-K] + 1
    if ans < a:
        ans = a


print(ans)

Submission status: Accepted

Solution code:
n, k = [int(item) for item in input().split()]
s = [int(item) for item in list(input())]

dp = [0] * (n + 1)
dp[0] = [0, 0, 0]
for i in range(1, n + 1):
    if s[i - 1]:
        dp[i] = [dp[i - 1][0], dp[i - 1][1] + 1, dp[i - 1][2] + 1]
    elif i == 1 or s[i - 1 - 1]:
        dp[i] = [dp[i - 1][0] + 1, dp[i - 1][1] + 1, 0]
    else:
        dp[i] = [dp[i - 1][0], dp[i - 1][1] + 1, 0]

K = [[0] * 2 for _ in range(max((n + 1), k + 1))]
for x in dp:
    K[x[0]] = [x[1], x[2]]

# print(K, dp, dp[-1][0])
ans = 0

for i in range(dp[-1][0] + 1):
    if k + i <= dp[-1][0]:
        ans = max(ans, K[i + k][0] - K[i][0] + K[i][1])
    else:
        ans = max(ans, K[dp[-1][0]][0] - K[i][0] + K[i][1])

# for i in range(n + 1):
#     if dp[i][0] + k > dp[-1][0]:
#         ans = max(ans, K[dp[-1][0]][0] - dp[i][1] + K[dp[-1][0]][1])
#     else:
#         ans = max(ans, K[dp[i][0] + k][0] - dp[i][1] + K[dp[i][0] + k][1])

print(ans)

Submission status: Accepted

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

s = []

cnt = 1
current = S[0]

for i in range(1, N):
    if S[i] == current:
        cnt += 1
    else:
        current = S[i]
        s += [cnt]
        cnt = 1
s += [cnt]

# k: K=∞のときの反転可能回数
if S[0] == '0':
    k = (len(s)+1)//2
else:
    k = len(s)//2

if k <= K:
    print(N)
    
else:
    
    n = len(s)
    
    first = 0
    if S[0] == '0':
        end = K*2
    else:
        end = K*2+1
    m = sum(s[first:end])
    current = m
    
    if S[0] == '0':
        first = 1
    else:
        first = 2
    end += 2
    
    while(end < n):
        current = current - s[first-1] + s[end-2] + s[end-1]
        if first != 1:
            current -= s[first-2]
            
        if m < current:
            m = current
        first += 2
        end += 2
        
    current = sum(s[first:])
    if m < current:
        m = current
        
    print(m)

Submission status: Accepted

Solution code:
read = input
n,k = map(int, read().split())
a = read()
a = '1' + a + '1'
# -1 if use 0, -1 if use len(a) -1
pstart = 0
pcnt = 0
ptype = '1'
b = []
# (start, end, cnt)
for tp in enumerate(a):
    i, c = tp
    if ptype == c:
        pcnt = pcnt + 1
    else :
        b.append((pstart, i-1, pcnt))
        pstart = i
        ptype = c
        pcnt = 1
b.append((pstart, i, pcnt))
# print(b)
if k >= len(b)//2:
    print(sum(map(lambda tp:tp[2], b)) - 2)
else :
    start = 0
    end = k * 2
    ans = 0
    S = [0 for i in range(len(b)+10)]
    S[0] = b[0][2]
    for i in range(1, len(b)):
        S[i] = S[i-1] + b[i][2]
    while(end <= len(b) - 1):
        tmp = S[end] - (S[start - 1] if start - 1>=0 else 0)
        if b[start][0] == 0:
            tmp = tmp - 1
        if b[end][1] == len(a)-1:
            tmp = tmp -1
#         print(start, end ,tmp)
        ans = max(ans, tmp)
        start = start + 2
        end = end + 2
    print(ans)

Submission status: Accepted

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

if s[0] == "0":
    r.append(0)

c = 1
for i in range(1, n):
    if s[i - 1] == s[i]:
        c += 1
    else:
        r.append(c)
        c = 1
    
if s[n - 1] == "0":
    r.append(c)
    r.append(0)
else:
    r.append(c)

if (len(r) - 1) // 2 <= k:
    print(n)
else:
    rs = [0] * (len(r) + 1)
    for i in range(1, len(r) + 1):
        rs[i] = rs[i - 1] + r[i - 1]
    s_max = 0
    m = 0
    while m + 2 * k + 1 < len(rs):
        if s_max < rs[m + 2 * k + 1] - rs[m]:
            s_max = rs[m + 2 * k + 1] - rs[m]
        m += 2
    print(s_max)

Submission status: Accepted

Solution code:
import collections
n, k = map(int, input().split())
s = input()
zero =[]
cnt = 0
d = collections.deque()
for i, j in enumerate(s):
    if j == '0':
        cnt += 1
    if j == '1' and i > 0:
        if cnt > 0:
            zero.append((cnt, i-1))
            cnt = 0
if cnt > 0:
    zero.append((cnt, n-1))
idx = n-1
one= []
while zero:
    d.append(zero.pop())
    if len(d) < k:
        continue
    if zero:    
        i, j = zero[-1]
        one.append(idx-j)
    else:
        one.append(idx +1)
    k, l = d.popleft()
    idx = l-k
if one == []:
    one.append(n)
print(max(one))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, K: int, S: str):
    s = []
    buf = 0
    mode = S[0]
    for c in S:
        if c == mode:
            buf += 1
        else:
            s.append(buf)
            buf = 1
            mode = c
    s.append(buf)

    # 1始まり1終わり
    if S[0] == "0":
        s = [0]+s
    if S[-1] == "0":
        s = s+[0]
    # print(s)

    tot = [0]+list(itertools.accumulate(s))
    w = 2*K+1
    hint = [tot[i+w]-tot[i] for i in range(0, len(tot)-w, 2)]
    if len(hint) == 0:
        print(len(S))
    else:
        print(max(hint))
    return


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: int
    solve(N, K, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
st = input()
num = 0
state = 0
cumsum = []
for s in st:
    if int(s) == state:
        num += 1
    else:
        cumsum.append(num)
        state = [1, 0][state]
        num = 1
cumsum.append(num)
cumsum = [0] + cumsum + [0, 0]
if (len(cumsum) % 2) == 0:
    cumsum += [0]
l = min(k * 2, len(cumsum) - 1 - (len(cumsum) % 2))
sumsum = sum(cumsum[:l + 1])
max_sum = sumsum
start_idx = 0
end_idx = l + 1
if len(cumsum) - l + 1 > 3:
    for n in range(2, len(cumsum) - l + 1, 2):
        sumsum = (
            sumsum - sum(cumsum[start_idx: start_idx + 2])
            + sum(cumsum[end_idx: end_idx + 2])
        )
        start_idx += 2
        end_idx += 2
        max_sum = max(max_sum, sumsum)

print(max_sum)

Submission status: Accepted

Solution code:
N,K=map(int,input().split(' '))
S=input()
left=[]
right=[]
for i in range(len(S)):
	#len(left)>len(right)のとき1区間が開いていると呼ぶ
	#開いているときにS[i]=='1'なら何もしない
	#開いているときにS[i]=='0'ならrightにi-1を追加
	#閉じているときにS[i]=='1'ならleftにiを追加
	#開いているときにS[i]=='0'なら何もしない
	if len(left)>len(right):
		if S[i]=='0':
			right.append(i-1)
	elif len(left)==len(right):
		if S[i]=='1':
			left.append(i)
#右端の通常処理を行なう
#S[-1]=='0'なら区間はすでに閉じているはずなので何もしない
#S[-1]=='1'なら区間はまだ開いているはずなのでrightにN-1を追加して閉じる
if len(left)>len(right):
	right.append(N-1)

section=[ [left[i],right[i]] for i in range(len(left)) ]

section=[[0, 0]] + section + [[N-1, N-1]]
#print(section)

length=[]

if K+1>=len(section):
	print(N)
else:
	for i in range(len(section)-K):
		length.append(section[i+K][1] - section[i][0] + 1)
	print(max(length))

Submission status: Accepted

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

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

counts = [0] if S[0] == '0' else []
s = '1' if S[0] == '1' else '0'
c = 0
for i in range(N):
    if S[i] != s:
        counts.append(c)
        c = 0
        if s == '1':
            s = '0'
        else:
            s = '1'
    c += 1
counts.append(c)

ans = 0
cumsum = [0] * (len(counts) + 1)
for i in range(len(counts)):
    cumsum[i + 1] = cumsum[i] + counts[i]
for i in range(len(counts)):
    if i % 2 == 1:
        continue
    # ans = max(ans, sum(counts[i: i + 2 * K + 1]))
    r = min(i + 2 * K + 1, len(counts))
    l = i
    if r == l:
        ans = max(ans, counts[i])
    else:
        ans = max(ans, cumsum[r] - cumsum[l])
    # ans = max(ans, cumsum[r] - cumsum[l])
    # print(l, r, cumsum[r] - cumsum[l])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(map(int,input()))
lis_one=[]
lis_zero=[]
if s[0]!=1:
    lis_one.append(0)
i=0
if n==1:
    print(1)
    exit()
while i<n-1:
    cnt=1
    while s[i]==s[i+1]:
        cnt+=1
        i+=1
        if i==n-1:
            break
    if s[i]==0:
        lis_zero.append(cnt)
    else:
        lis_one.append(cnt)
    i+=1
ans=0
lis_one.append(0)
lis_zero.append(0)
oone=[]
zzero=[]
oone.append(sum(lis_one[0:k+1]))
zzero.append(sum(lis_zero[0:k]))
for i in range(len(lis_one)-k-1):
    oone.append(oone[i]-lis_one[i]+lis_one[i+k+1])
    zzero.append(zzero[i]-lis_zero[i]+lis_zero[i+k])
for i in range(len(oone)):
    ans=max(ans,oone[i]+zzero[i])
print(ans)

Submission status: Accepted

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

l = [["",1]]
for c in s:
    if c!=l[-1][0]:
        l.append([c,1])
    else:
        l[-1][1]+=1
      
l.pop(0)
cnt0 = 0
dp = []
z = []
for i in range(len(l)):
    if l[i][0] == '0':
        cnt0 += 1
        z.append((i,l[i][1]))
#print(z)
if len(z)==0:
    print(n)
    exit(0)
for i in range(cnt0):
    idx,cnt = z[i]
    currcnt = 0
    if idx-1>=0:
        currcnt += l[idx-1][1]
    if i >0:
        currcnt += dp[-1][1]
    currcnt+=cnt
    dp.append((idx,currcnt))
#print(dp) 
res = 0

for i in range(len(dp)):
    tmp = 0
    if i-k>=0:
        tmp = dp[i][1]-dp[i-k][1]
    else:
        tmp = dp[i][1]
    if dp[i][0]+1<len(l):
        tmp += l[dp[i][0]+1][1]
    res = max(res,tmp)
print(res)

Submission status: Accepted

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

def solve():
    N, K = list(map(int, input().split(" ")))
    S = input()

    # 左から順に考える
    # 累積和
    ruiseki = []
    i = 0
    while True:
        if i >= N:
            break
        
        num = 0
        if S[i] == "1":
            while i < N and S[i] == "1":
                num += 1
                i += 1
            ruiseki.append(["1", num])
        else:
            while i < N and S[i] == "0":
                num += 1
                i += 1
            ruiseki.append(["0", num])
    
    if ruiseki[0][0] == "0":
        i = 0
    else:
        i = 1

def solve2():
    N, K = list(map(int, input().split(" ")))
    S = input()

    i = 0
    ruiseki = [0]
    while True:
        if i >= N:
            break
        
        num = 0
        if S[i] == "1":
            while i < N and S[i] == "1":
                num += 1
                i += 1
            ruiseki.append(num + ruiseki[-1])
        else:
            while i < N and S[i] == "0":
                num += 1
                i += 1
            ruiseki.append(num + ruiseki[-1])

    import math
    if S[0] == "1":
        zero_num = math.floor((len(ruiseki) - 1) / 2)
    else:
        zero_num = math.ceil((len(ruiseki)-1)/2)

    if K >= zero_num:
        print(ruiseki[-1])
        return

    ans = 0
    if S[0] == "1":
        for i in range(2, len(ruiseki), 2):
            end = i + 2*(K-1)
            if end >= len(ruiseki):
                break
            if end+1 < len(ruiseki):
                # 後ろが"1"のとき
                end += 1

            ans = max(ruiseki[end] - ruiseki[i-2], ans)

    else:
        for i in range(1, len(ruiseki), 2):
            end = i + 2*(K-1)
            if end >= len(ruiseki):
                break
            if end+1 < len(ruiseki):
                end += 1

            if i-2 >= 0:              
                ans = max(ruiseki[end]-ruiseki[i-2], ans)
            else:
                ans = max(ruiseki[end]-ruiseki[i-1], ans)

    print(ans)            




if __name__ == "__main__":
    solve2()

Submission status: Accepted

Solution code:
def mark_zero1(s):
    index = [i for i, s_ in enumerate(s) if s_ == "0" and safe_get(s, i - 1) != "0"]
    return index


def mark_zero2(s):
    index = [i for i, s_ in enumerate(s) if s_ == "0" and safe_get(s, i + 1) != "0"]
    return index


def safe_get(lis, index):
    if index < 0:
        return -1
    elif index >= len(lis):
        return len(s)
    else:
        return lis[index]


def get_score(a, b, i, j):
    return safe_get(a, j + 1) - safe_get(b, i - 1) - 1


n, k = list(map(int, input().split(" ")))
s = input()
a = mark_zero1(s)
b = mark_zero2(s)


try_num = min(len(a), k)
ij_list = [(idx, idx + try_num - 1) for idx in range(len(a) - try_num + 1)]

print(max([get_score(a, b, i, j) for i, j in ij_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()
zero = 0
flag = 0
for i in s:
    if i == "0":
        flag = 1
    else:
        if flag:
            zero += 1
        flag = 0
if flag:
    zero += 1
k = min(zero, k)
renzoku = []
count = 0
flag = 0
for i in range(n):
    if s[i] == "1":
        if flag:
            count += 1
        else:
            renzoku.append(count)
            count = 1
        flag = 1
    else:
        if flag:
            renzoku.append(count)
            count = 1
        else:
            count += 1
        flag = 0
renzoku.append(count)
renzoku_t = [0]
for i in range(len(renzoku)):
    renzoku_t.append(renzoku[i] + renzoku_t[i])
ans = 0
if k == zero:
    print(n)
    exit()
if s[0] == "0":
    ans = renzoku_t[0 + k + k] - renzoku_t[0]
for i in range(1, len(renzoku) - k - k + 1, 2):
    if i == 0 or i == len(renzoku) - k - k:
        ans = max(ans, renzoku_t[i + k + k] - renzoku_t[i])
    else:
        ans = max(ans, renzoku_t[i + k + k + 1] - renzoku_t[i])
print(ans)

Submission status: Accepted

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

sentous = []
sentou = 0
counts = [0]
count = 0
prev = 0
for s in S:
    count += 1
    sentou += 1
    if s != prev and s == '1':
        if count > 1:
            sentous.append(sentou - 1)
        sentou = 1
    elif s != prev and s == '0':
        # sentou = 0
        if K > 0:
            K -= 1
        else:
            counts.append(count - 1)
            count -= sentous.pop(0)
    prev = s

print(max(max(counts), count))

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()
    s = '0' + SI() + '0'

    L = []
    R = []
    if s[1] == '0':
        L.append(1)
        R.append(1)
    for i in range(n + 1):
        if s[i] == '1' and s[i + 1] == '0':
            R.append(i)
        if s[i] == '0' and s[i + 1] == '1':
            L.append(i + 1)

    if s[-2] == '0':
        L.append(n)
        R.append(n)

    res = R[0] - L[0] + 1
    k = min(len(R) - 1, k)
    for i in range(len(R) - k):
        res = max(res, R[i + k] - L[i] + 1)

    # print(R)
    # print(L)

    return res


print(main())

Submission status: Accepted

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

ans = 0
fpos = []
p = '0'
for i in range(len(S)):
    if p == '0' and S[i] == '1':
        fpos.append(i)
    if p == '1' and S[i] == '0':
        fi = len(fpos) - 1 - K
        if fi >= 0:
            l = (i-1) - (fpos[fi]-1)
            if l > ans:
                ans = l
    p = S[i]
#print('ans: ', ans)
            
# top
p = '1'
cnt = 0
for i in range(len(S)):
    if p == '0' and S[i] == '1':
        cnt += 1
    if p == '1' and S[i] == '0':
        if cnt == K:
            l = i
            if l > ans:
                ans = l
            break
    if i == len(S) - 1:
        l = len(S)
        if l > ans:
            ans = l
        break
    p = S[i]

# tail
p = '1'
cnt = 0
for i in range(len(S)-1, -1, -1):
    if p == '0' and S[i] == '1':
        cnt += 1
    if p == '1' and S[i] == '0':
        if cnt == K:
            l = (len(S)-1) - i
            if l > ans:
                ans = l
            break
    if i == 0:
        l = len(S)
        if l > ans:
            ans = l
        break
    p = S[i]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))

n,k =  words(int)
s = input()

stt = s[0]

cnts = []
cur = stt
lcnt = 0
for c in s:
    if c == cur:
        lcnt += 1
    else:
        cnts.append(lcnt)
        lcnt = 1
        if cur == '0':
            cur = '1'
        else:
            cur = '0'
cnts.append(lcnt)
zsum = 0
if stt == '0':
    sumstt = 1
    for i in range(min(k*2,len(cnts))):
        zsum += cnts[i]
else:
    sumstt = 0

#print(cnts)
sum = 0
#print("ss",sumstt, len(cnts),sumstt+(k*2+1))
for i in range(sumstt, min(len(cnts),sumstt+(k*2+1))):
    sum += cnts[i]

#print(zsum, sum)
maxsum = max(zsum,sum)

l = sumstt + 2
r = sumstt + k*2+1 + 2
#print("first lr",l,r)
while r <= len(cnts):
    sum = sum - cnts[l-2] - cnts[l-1] + cnts[r-2] + cnts[r-1]
    #print(l,r, sum)
    maxsum = max(maxsum, sum)
    l += 2
    r += 2

#print(l,r)
if s[-1] == '0' and r-2 < len(cnts):
    sum = sum - cnts[l-2] - cnts[l-1] + cnts[r-2]
    #print("last 0", l, r,sum)
    maxsum = max(maxsum, sum)

print(maxsum)

Submission status: Accepted

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

first_one = S[0] == '1'
cnts = []
cnt = 1
for i, e in enumerate(S):
    if i == 0:
        pass
    else:
        if e != S[i-1]:
            cnts.append(cnt)
            cnt = 1
        else:
            cnt += 1
cnts.append(cnt)


zero_obj = []
for i, c in enumerate(cnts):
    if first_one:
        if i % 2 == 1:
            left = 0
            if i - 1 >= 0:
                left = cnts[i-1]
            right = 0
            if i + 1 < len(cnts):
                right = cnts[i+1]
            zero_obj.append((left, c, right))
    else:
        if i % 2 == 0:
            left = 0
            if i - 1 >= 0:
                left = cnts[i-1]
            right = 0
            if i + 1 < len(cnts):
                right = cnts[i+1]
            zero_obj.append((left, c, right))

if len(zero_obj) <= K:
    print(len(S))
else:
    m = -1
    tmp = zero_obj[0][0]
    for i in range(K):
        tmp += zero_obj[i][1] + zero_obj[i][2]
    m = tmp
    for i in range(len(zero_obj) - K):
        tmp -= zero_obj[i][0] + zero_obj[i][1]
        tmp += zero_obj[i+K][1] + zero_obj[i+K][2]
        if tmp > m:
            m = tmp
    print(m)

Submission status: Accepted

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


l=[]
p="1"
q=0
for i in s:
    if i==p:
        q+=1
    else:
        l.append(q)
        q=1
        if p=="1":
            p="0"
        else:
            p="1"
l.append(q)

r=[0]
def ruiseki(a):
    for i in range(len(a)):
        r.append(r[i]+a[i])
ruiseki(l)
ans=0

if len(r)-(2*k+2)+1<=0:
    print(r[-1])
    import sys
    sys.exit()
    
for i in range(len(r)-(2*k+2)+1):
    if (i+2*k+1)%2==1:
        ans=max(ans,r[i+2*k+1]-r[i])
ans=max(ans,r[-1]-r[len(r)-(2*k+2)+1])
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
start = [0]
ret = 0
first = False
for i in range(len(s)):
    if s[i] == '1' and first:
        start.append(i)
        first = False
    if s[i] == '0' and not first:
        ret = max(ret, i - start[max(0, len(start) - k - 1)])
        first = True
if first:
    start.append(len(s))
ret = max(ret, len(s) - start[max(0, len(start) - k - 1)])
print(ret)

Submission status: Accepted

Solution code:
N , K = map(int,input().split())
S = list(input())
row = []
for i in range(N):
	if i == 0:
		judge = S[i]
		row.append(1)
	else:
		if judge == S[i]:
			row[-1] += 1
		else:
			judge = S[i]
			row.append(1)
if S[-1] == "0":
	row.append(0)
if S[0] == "0":
	row.insert(0,0)
max_row = 2 * K + 1

if max_row >= len(row):
	print(N)
else:
	sum_count = []
	temp_sum = 0
	for i in range(max_row):
		temp_sum += row[i]
	sum_count.append(temp_sum)
	i = max_row
	while i < len(row):
		sum_count.append(sum_count[-1] + row[i] + row[i+1] - row[i-max_row] - row[i-max_row+1])
		i += 2
	print(max(sum_count))

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
    # error_print(N, K)
    # error_print(S)
    # error_print(s1)
    # error_print(s0)

    ans = 0
    s0_top = None
    if S[0] == '0':
        s0_top = s0.pop(0)
        ans = s0_top + sum(s1[:K]) + sum(s0[:K-1])
    
    l1o = 1
    l0o = 0
    l1 = sum(s1[:K+l1o])
    l0 = sum(s0[:K+l0o])
    k = 0
    
    while True:
        tmp = l1 + l0
        # if k == 0 and S[0] == '0':
        #     tmp -= s1[K]
        ans = max(ans, tmp)
        if k+K < len(s1) and k+K < len(s0):
            l1 -= s1[k]
            if k+K+l1o < len(s1):
                l1 += s1[k+K+l1o]
            l0 -= s0[k]
            if k+K+l0o < len(s0):
                l0 += s0[k+K+l0o]
        else:
            break
        k += 1
    

    return ans


def main():
    N, K = read_int_n()
    S = read_str()
    rS = ''.join(['0' if c == '1' else '1' for c in S])
    print(max(slv(N, K, S), slv(N, K-1, rS)))

    # 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:
n, k = map(int, input().split())
s = input()

aa = []
prev = None
for c in s:
    if prev != c:
        aa.append((c, 1))
        prev = c
    else:
        _, count = aa[-1]
        aa[-1] = (prev, count + 1)

kk = 0
candidate = 0
total = 0
i = 0
if aa[i][0] == '1':
    total = aa[i][1]
    candidate = total
    i += 1


while i < len(aa):
    if aa[i][0] == '0':
        if kk < k:
            kk += 1
            total += aa[i][1]
            if i < len(aa) - 1:
                i += 1
                total += aa[i][1]
            candidate = max(candidate, total)
        else:
            total -= aa[i - k * 2][1]
            if i - k * 2 - 1 >= 0:
                total -= aa[i - k * 2 - 1][1]

            total += aa[i][1]
            if i < len(aa) - 1:
                i += 1
                total += aa[i][1]
            candidate = max(candidate, total)

    i += 1

print(candidate)

Submission status: Accepted

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

from itertools import chain
from functools import reduce
from collections import OrderedDict, Counter, deque
import operator

IS = lambda: int(input())
IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]

N, K = IA()
S = input()

l = 0
c = S[0]
con = [0] if S[0] == '0' else []
for s in S:
    if c == s:
        l += 1
    else:
        con.append(l)
        l = 1
        c = s
con.append(l)
if S[-1] == '0':
    con.append(0)

lc = len(con)
if lc <= K * 2 + 1:
    print(sum(con))
else:
    tl = K * 2 + 1
    cur = sum(con[:tl])
    ans = cur
    turn = False
    for l, r in zip(con[:lc - tl], con[tl:]):
        cur -= l
        cur += r
        if turn:
            ans = max(ans, cur)
        turn = not turn
    print(ans)

Submission status: Accepted

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

T = [0]
now = S[0]
start = now
for i in range(1,N):
    if S[i]!=now:
        now=S[i]
        T.append(i)

T.append(N)
max_score = 0
for i in range(len(T)):
    if start=="0":
        if i%2==0:
            r=min(2*K+i,len(T)-1)
            l=max(0,i-1)
            max_score = max(T[r]-T[l],max_score)
    else:
        if i%2==1:
            r=min(2*K+i,len(T)-1)
            l=max(0,i-1)
            max_score = max(T[r]-T[l],max_score)
            
print(max_score)

Submission status: Accepted

Solution code:
import numpy as np
import sys

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

consecutive_ones = [len(x) for x in s.split("0") if x != '']
consecutive_zeros = [len(x) for x in s.split("1") if x != '']

if len(consecutive_zeros) == 0:
    print(n)
    sys.exit(0)

if len(consecutive_ones) == 0:
    if k > 0:
        print(n)
    else:
        print(0)
    sys.exit(0)

cumsum_ones = list(np.convolve(consecutive_ones, np.ones(k+1), mode='valid'))
cumsum_zeros = list(np.convolve(consecutive_zeros, np.ones(k), mode='valid'))

if s[0] == "0":
    cumsum_ones.insert(0, sum(consecutive_ones[:k]))

if s[-1] == "0":
    cumsum_ones.append(sum(consecutive_ones[-k:]))

z = [x + y for x,y in zip(cumsum_ones, cumsum_zeros)]
result = int(max(z))
print(result)

Submission status: Accepted

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

# 100101 => [1,2,1,1,1]
# 011000 => [0,1,2,3,0]
human = []

is_handstood = False
cnt = 0

for ch in s:
    if ch == "0" and not is_handstood:
    	human.append(cnt)
    	is_handstood = True
    	cnt = 1
    elif ch == "1" and is_handstood:
    	human.append(cnt)
    	is_handstood = False
    	cnt = 1
    else:
        cnt += 1
human.append(cnt)
if is_handstood:
    human.append(0)

total_human = [0 for i in range(len(human))]
total_human[0] = human[0]
for i in range(1, len(human)):
    total_human[i] = total_human[i - 1] + human[i]

if len(human) <= 2 * k + 1:
    max_human = n
else:
    max_human = total_human[k * 2]
    for i in range(k * 2 + 2, len(total_human), 2):
        if total_human[i] - total_human[i - k * 2 - 1] > max_human:
        	max_human = total_human[i] - total_human[i - k * 2 - 1]

print(max_human)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
n, k = map(int, input().split())
s_list = list(map(int, list(input()[:-1])))
new_list = []
tmp = 0
for s in s_list:
    if s == 1:
        if tmp < 0:
            new_list.append(tmp)
            tmp = 1
        else:
            tmp += 1
    else:
        if tmp > 0:
            new_list.append(tmp)
            tmp = -1
        else:
            tmp -= 1
new_list.append(tmp)
q = deque([]) 
new_len = len(new_list)
if new_list[0] < 0:
    flag = 0
else:
    flag = 1
check = 0
cnt = 0
tmp = 0
for p in new_list:
    if p > 0:
        q.append(p)
        tmp += p
    else:
        if check < k:
            q.append(p)
            check += 1
            tmp += abs(p)
        else:
            pop_p = q.popleft()
            if pop_p > 0: 
                tmp -= pop_p
                tmp -= abs(q.popleft())
            else:
                tmp -= abs(pop_p)
            q.append(p)
            tmp += abs(p)
    cnt = max(cnt, tmp)
print(cnt)

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)