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 = input()

nums = []
now = 1 # 今見ている値
cnt = 0 # 今見ている値の連続する個数
for i in range(n):
    if s[i] == str(now): # 今見ているもの同じ場合
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1
        cnt = 1
# 最後の部分を追加
nums.append(cnt)
# 配列の大きさが奇数でないなら，0を追加
if len(nums) % 2 == 0:
    nums.append(0)

# 尺取法
left, right = 0, 0
tmp = 0 # [left, right)の総和

res = 0
for i in range(0, len(nums), 2): # 1のところを見ていく
    nextleft, nextright = i, min(i + 2 * k + 1, len(nums))
    while nextleft > left:
        tmp -= nums[left]
        left += 1
    while nextright > right:
        tmp += nums[right]
        right += 1
    res = max(res, tmp)
    
print(res)

Submission status: Accepted

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

nums = []
now = 1 # 今見ている数
cnt = 0 # nowが並んでいる個数
for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt) # 切り替わりで追加
        now = 1 - now # 0と1を切り替える
        cnt = 1 # 新しいものをカウントし始める
# 最後
if cnt != 0:
    nums.append(cnt)

# 調整
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * k + 1

# 累積和を作る
acc = [0] * (len(nums) + 1)
for i in range(len(nums)):
    acc[i + 1] = acc[i] + nums[i]

res = 0
# 偶数番目だけ見る
for i in range(0, len(nums), 2):
    # [left, right)
    left = i
    right = min(i + add, len(nums))
    tmp = acc[right] - acc[left]
    res = max(res, tmp)

print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate

def runlength(S):
    cnt = 1
    A = []
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            cnt += 1
        else:
            A.append(cnt)
            cnt = 1
    else:
        A.append(cnt)

    return A


def main():
    N, K = map(int, input().split())
    S = input()
    T = []
    prev = '1'
    cnt = 0
    for c in S:
        if prev == c:
            cnt += 1
        else:
            T.append(cnt)
            cnt = 1
        prev = c
    
    T.append(cnt)    
    if prev == '0':
        T.append(0)

    w = 2 * K + 1
    if len(T) <= w:
        print(N)
        exit()

    acc = [0] + list(accumulate(T))
    ans = 0
    for i in range(0, len(T) - w + 1, 2):
        ans = max(ans, acc[i+w] -acc[i])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

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

n_group = len(l) // 2
sum_ = 0
k = min(K, n_group)
for i in range(k):
    sum_ += l[2*i] + l[2*i+1]
sum_ += l[2*k]
max_ = sum_
for i in range(k, n_group):
    sum_ -= l[2*i-2*K] + l[2*i+1-2*K]
    sum_ += l[2*i+1] + l[2*i+2]
    max_ = max(max_, sum_)
print(max_)

Submission status: Accepted

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

S += '1' if S[N-1] == '0' else '0'
sumz = [0]*(N+2)
right = 1
cnt = 1
maxlen = 0
left = 0
if K == 0:
    for i in range(N):
        if S[i] == S[i+1] and S[i] == 1:
            cnt += 1
        else:
            if maxlen < cnt:
                maxlen = cnt
            cnt = 1
else:
    cnt = 0
    while True:
        if left >= N: break
        if right <= left: right = left+1
        while (right <N) and ((cnt < K) or ((cnt == K) and ((S[right] == S[right-1]) or S[right] == '1'))):
            if (S[right] != S[right - 1]) and (S[right-1] == '0'):
                cnt += 1
            right += 1

        if not( S[right-1] == '0' and (K == 0)):
            if maxlen < right - left:
                maxlen = right - left
        #next
        while left < N and S[left] == S[left+1]:
            left += 1
        if S[left] == '0':
            cnt -= 1

        left += 1

print(maxlen)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    S = input()
    nums = []
    # 1の個数、0の個数を交互に記録していく
    if S[0] == '0': nums.append(0)
    i = 0
    while i < N:
        j = i
        while j < N and S[i]==S[j]:
            j += 1
        nums.append(j-i)
        i = j
    if S[-1] == '0': nums.append(0)
    # print(nums)
    nums = [0] + list(accumulate(nums))
    # print(nums)
    ans = 0
    
    for i in range(0,len(nums),2):
        # print(i)
        ans = max(ans,nums[min(i+2*K+1,len(nums)-1)]-nums[i])
    print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

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

i = 0
a = []
while i < n:
    l = 1
    while i+1 < n and s[i]==s[i+1]:
        l+=1
        i+=1
    a.append(l)
    i+=1

if s[0] == 0:
    a = [0] + a
if s[-1] == 0:
    a = a + [0]
n = len(a)

acum = [0]*(n+1)
for i in range(n):
    acum[i+1] = acum[i]+a[i]

ans = 0
for i in range(0, n, 2):
    end = min(i+2*k+1, n)
    ans = max(ans, acum[end] - acum[i])
print(ans)

Submission status: Accepted

Solution code:
def compress(S):
    res = []
    prev = "aa"
    for c in S:
        if c != prev:
            res.append([c, 1])
        else:
            res[-1][1] += 1
        prev = c
    return res


N, K = map(int, input().split())
S = list(map(int, input()))
S_comp = compress(S)
M = len(S_comp)
ans = 0
total = 0
right = 0
zero_chunks_cnt = 0
for left in range(M):
    while right < M and zero_chunks_cnt + 1 - S_comp[right][0] <= K:
        zero_chunks_cnt += 1 - S_comp[right][0]
        total += S_comp[right][1]
        right += 1
    ans = max(ans, total)
    if right == left:
        right += 1
    else:
        zero_chunks_cnt -= 1 - S_comp[left][0]
        total -= S_comp[left][1]
print(ans)

Submission status: Accepted

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

now = -1
count = 0
for i in range(0,N,1):
    if now == S[i]:
        count+=1
    else:
        if now != -1:count01.append([count,S[i-1]])
        now = S[i]
        count=1
count01.append([count,S[N-1]])

for i in range(1,len(count01),1):
    count01[i][0]+=count01[i-1][0]#累積和とする。区間[a,b]の和はruiseki[b]-ruiseki[a-1]

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

Submission status: Accepted

Solution code:
inp = input
out = print
N, K = map(int, inp().split())
S = inp().rstrip('\n')

S += '1' if S[N-1] == '0' else '0'

#count
lenz = []
valz = []
cnt = 1
for i in range(1, N+1):
    if S[i] == S[i-1]:
        cnt += 1
    else:
        #add to lenz
        lenz.append(cnt)
        valz.append(1 if S[i-1] == '1' else 0)
        cnt = 1

M = len(lenz)
sumz = 0#[0]*(M+1)
maxsum = 0
right = 0
cnt = 0
left = 0
while left < M:
    while right < M:
        if valz[right] == 0:
            cnt += 1
        if cnt > K: break
        sumz += lenz[right]
        right += 1
    if maxsum < sumz: maxsum = sumz

    if right >= M:
        #finish, no more longer series
        break

    tmp = left
    cnt -= 1
    while left < M and valz[left] != 0:
        sumz -= lenz[left]
        left += 1
    if left < M:
        sumz -= lenz[left]
        cnt -= 1
        left += 1

out(maxsum)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
A = {}
if S[0] == "1":
    A[1] = 0
    c = 1
else:
    A[0] = 0
    c = 0
for i in range(N-1):
    if S[i] == "0" and S[i+1] == "1":
        c += 1
        A[c] = i+1
B = {}
c = 1
for i in range(N-1):
    if S[i] == "1" and S[i+1] == "0":
        B[c] = i
        c += 1

ans = 0
for p, v in A.items():
    t = B.get(p+K, N-1)
    ans = max(t-v+1, ans)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
ban=[]
if s[0]=="0": ban.append(0)
cnt=1
for i,val in enumerate(s[:-1]):
    if val!=s[i+1]:
        ban.append(cnt)
        cnt=0
    cnt+=1
if cnt>0: ban.append(cnt)
if s[n-1]=="0": ban.append(0)
ans=sum(ban[0:2*k+1])
su=ans
now=0
while now+2*k+2<=len(ban):
    su-=ban[now]+ban[now+1]
    su+=ban[now+2*k+1]+ban[now+2*k+2]
    if su>ans: ans=su
    now+=2
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    s = list(input())
    l = []
    if s[0] == "0":
        l.append(["1", 0])
    l.append([s[0], 1])
    for i in range(1, n):
        if s[i] == l[-1][0]:
            l[-1][1] += 1
        else:
            l.append([s[i], 1])
    if s[-1] == "0":
        l.append(["1", 0])
    count = []
    for standing, c in l:
        count.append(c)
    count = list(accumulate(count))
    count = [0] + count
    answer = 0
    for i in range(0, len(count), 2):
        j = i + 2 * k + 1
        if j >= len(count):
            j = len(count) - 1
        answer = max(answer, count[j] - count[i])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = input()
sakidata = [1]
lastdata = [0]
#data... わける.

mode = False
for cnt, i in enumerate(s):
	if mode:
		if i == "0":
			lastdata.append(cnt)
			mode = False
	else:
		if i == "1":
			sakidata.append(cnt+1)
			mode = True

if mode:
	lastdata.append(cnt+1)

sakidata.append(n)
lastdata.append(n)

ans = 0

#print(sakidata)
#print(lastdata)

for i in range(len(lastdata)-k):
	targ = lastdata[i+k]-sakidata[i]+1
	ans = max(targ, ans)
	
if len(lastdata)-k < 1:
	ans = n

print(ans)

Submission status: Accepted

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

flag=1
i=0
ans=[0]*(n+1)
for ss in s:
    if int(ss)==flag:
        ans[i]+=1
    else:
        i+=1
        ans[i]+=1
        flag=(flag+1)%2

result=(sum(ans[:min(2*k+1,n)]))

tmp=result

l=0
r=2*k
#print(ans)
while 1:
    if r+2<(n+1):
        tmp=tmp-ans[l]-ans[l+1]+ans[r+1]+ans[r+2]
        l+=2
        r+=2
        result=max(result,tmp)
        #print(ans[l:r])
    else:
        break

    #print(tmp)
print(result)

Submission status: Accepted

Solution code:
def m():
    N, K = map(int, input().split())
    S = input()
    comp = []
    prev = S[0]
    cnt = 1
    for i in range(1, N):
        if prev == S[i]:
            cnt += 1
            prev = S[i]
        else:
            comp.append(cnt)
            prev = S[i]
            cnt = 1
    comp.append(cnt)
    comp_n = len(comp)
    acum = [0] * (comp_n + 1)
    acum[0] = 0
    if comp_n < (2*K):
        return N
    for i in range(comp_n):
        acum[i + 1] = comp[i] + acum[i]
    ans = 0
    if S[N - 1] == '0':
        ans = max(acum[comp_n] - acum[comp_n - (2 * K)], ans)

    if S[0] == '0':
        ans = max(acum[2 * K], ans)
    left = 1 if S[0] == '0' else 0
    right = left + (K*2+1)
    while right <= comp_n:
        t = acum[right] - acum[left]
        ans = max(ans, t)
        right +=2
        left +=2
    return ans


print(m())

Submission status: Accepted

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

l_01 = []
l_10 = []
if s[0] == '1':
    l_01.append(0)
for i in range(n-1):
    if s[i] == '0' and s[i+1] == '1':
        l_01.append(i+1)
    elif s[i] == '1' and s[i+1] == '0':
        l_10.append(i+1)
if s[-1] == '1':
    l_10.append(n)

cnt_0 = len(l_01) - 1
if s[0] == '0':
    cnt_0 += 1
if s[-1] == '0':
    cnt_0 += 1
cnt_1 = len(l_01)

if k >= cnt_0:
    print(n)
else:
    res = 0
    i = 0
    while i + k < cnt_1:
        res = max(res, l_10[i+k] - l_01[i])
        i += 1
    if s[0] == '0':
        res = max(res, l_10[k-1])
    if s[-1] == '0':
        res = max(res, n - l_01[-k])
    print(res)

Submission status: Accepted

Solution code:
import numpy as np

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

memo = np.zeros(10 ** 5 + 1, dtype=np.int64)
W = min(2 * k, 10 ** 5)

current = 1
p = 0

for x in s:
    if x == current:
        memo[p] += 1
    else:
        current = 1 - current
        p += 1
        memo[p] += 1

ans = memo[:W + 1].sum()
x = ans

for r in range(2, 10 ** 5 + 1, 2):
    if r + W > 10 ** 5:
        break
    x = x - memo[r - 2] - memo[r - 1] + memo[r + W] + memo[r + W - 1]
    if x > ans:
        ans = x
print(ans)

Submission status: Accepted

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

prev = S[0]
lst = []
cnt = 1
for s in S[1:]:
    if prev != s:
        lst.append(cnt)
        cnt = 0

    cnt += 1
    prev = s

lst.append(cnt)

right = 0
cnt = 0
l = len(lst)
sum_ = 0
max_ = 0
for i in range(l):
    if S[0] == '0':
        target_cnt = 2 * K + i % 2
    else:
        target_cnt = 2 * K + (i + 1) % 2

    while right < l and cnt < target_cnt:
        sum_ += lst[right]
        cnt += 1
        right += 1

    max_ = max(max_, sum_)
    sum_ -= lst[i]
    cnt -= 1


print(max_)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n,k = lr()
s = sr()
length1 = 0
tmp1 = 0
one = []
for c in s:
    if c == '1':
        tmp1+=1
    else:
        if tmp1 != 0:
            length1 += 1
            one.append(tmp1)
            tmp1 = 0
if tmp1 != 0:
    length1 += 1
    one.append(tmp1)

if length1 == 0:
    print(len(s))
    sys.exit()

zero = [0 for i in range(length1+1)]
ind = 0
while ind != n and s[ind] == '0':
    zero[0]+=1
    ind+=1
tmp0 = 0
ind0 = 1
while ind != n:
    while ind != n and s[ind] == '1':
        if tmp0 != 0:
            zero[ind0] = tmp0
            tmp0 = 0
            ind0+=1
        ind+=1
    while ind != n and s[ind] == '0':
        tmp0+=1
        ind+=1
if tmp0 != 0:
    zero[-1] = tmp0

a2 = [0 for i in range(len(zero)+1)]
a2[1] = zero[0]+one[0]
for i in range(2,len(zero)):
    a2[i] = a2[i-1]+zero[i-1]+one[i-1]
a2[len(zero)] = a2[len(zero)-1]+zero[len(zero)-1]

def sumArea(l,r):
    if l == 0:
        return a2[r]-a2[l]
    else:
        return a2[r]-a2[l]+one[l-1]

if len(zero)-k+1 < 1:
    print(len(s))
    sys.exit()
ans = 0
for i in range(len(zero)-k+1):
    ans = max(ans, sumArea(i,i+k))
print(ans)

Submission status: Accepted

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

    ans=0
    pre="1"
    right,SUM=0,0
    for left in range(n):
        while right<n and SUM+int(pre=="1" and s[right]=="0")<=k:
            SUM+=int(pre=="1" and s[right]=="0")
            pre=s[right]
            right+=1

        while right<n and s[right]=="1":
            right+=1
        if ans<max(ans,right-left):
            ans=right-left

        if right==left:right+=1;pre="1"
        elif left<n-1:SUM-=int(s[left]=="0"and s[left+1]=="1")
    print(ans)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:

import itertools

def countstrs(s):
    return [(k, len(list(g))) for k, g in itertools.groupby(s)]

n, k = map(int, input().split())
s = input()
c = countstrs(s)

total = [0] * (len(c) + 1)
cur = 0
for i in range(len(c)):
    cur += c[i][1]
    total[i+1] = cur


res = 0
l = 0
r = (2*k) + 0
while l < len(c):
    if c[l][0] == "0":
        rr = r
    else:
        rr = r+1
    if rr > len(c):
        rr = len(c)
    res = max(res, total[rr] - total[l])
    l += 1
    r += 1

print(res)

Submission status: Accepted

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

def calculate(n, k, s):
    s = list(s)

    result = [{'start': 0, 'end': 0}]
    for i in range(n):

        previous = s[i - 1]
        current = s[i]

        if i == 0:
            if s[i] == '1':
                result.append({'start': 0})
        else:
            if (current == '0') and (previous == '1'):
                res = result[-1]
                res.__setitem__('end', i)
                result[-1] = res

            if (current == '1') and (previous == '0'):
                result.append({'start': i})

        if i == n - 1 and s[i] == '1':
            res = result[-1]
            res.__setitem__('end', i + 1)
            result[-1] = res

    result.append({'start': n, 'end': n})


    # print(result)
    maxValue = 0
    if len(result) > k:
        for i in range(len(result) - k):
            val = result[i + k]['end'] - result[i]['start']
            maxValue = max(val, maxValue)
    else:
        maxValue = max(maxValue, result[-1]['end'] - result[0]['start'])


    print(maxValue)


calculate(N, K, S)

Submission status: Accepted

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

#圧縮（正の数が直立，負の数が逆立ち）
people = []
tmp = 0
for s in S:
    if s == "0":#直立
        if tmp >= 0:
            tmp += 1
        else:
            people.append(tmp)
            tmp = 1
    else:#逆立ち
        if tmp <= 0:
            tmp -= 1
        else:
            people.append(tmp)
            tmp = -1
people.append(tmp)

#print(people)

rev = 0#反転回数
ans = 0
#初めの範囲で
for i,num in enumerate(people):
    if num < 0:#元から逆立ちの時
        ans += -num
    else:
        rev += 1
        ans += num
    if rev == K:#それ以上反転できないので，右隣の逆立ち(居れば)の分だけ足して終わる
        try:
            ans += -people[i+1]
            break
        except IndexError:#最後に足した逆立ち群がそもそも右端だったら
            break

#print("initial ans",ans)

#SlidingWindow 右端と左端
right = (i+1)+1
left = 0

tmp = ans
#SlidingWindow
while True:
    #左端の更新
    if people[left] < 0:
        tmp -= abs(people[left])
        try:
            tmp -= abs(people[left+1])
            left += 2
        except IndexError:#len(people)==1のときだけ
            break
    else:
        tmp -= abs(people[left])
        left += 1
    
    #右端の更新
    try:
        tmp += abs(people[right])
        right += 1
    except IndexError:
        break
    
    try:
        tmp += abs(people[right])
        right += 1
    except IndexError:
        break
    ans = max(tmp, ans)

ans = max(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
if s[0] == "0":
    x_1 = [[0,0]]
else:
    x_1 = []
i = 0
while i < n:
    j = 0
    y_s = i
    while s[i] == s[i+j]:
        if i+j >= n-1:
            j += 1
            break
        j += 1
    y_e = i+j
    if s[i] == "1":
        x_1.append([y_s,y_e])
    i += j
if s[-1] == "0":
    x_1.append([n,n])
ans = 0
i = 0
if k >= len(x_1):
    ans = n
while i < n:
    if i+k >= len(x_1):
        break
    ans = max(ans,x_1[i+k][1]-x_1[i][0])
    i += 1
print(ans)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
s=input()
cnt=[[],[]]
st=1
c=0
for i in s:
  if st==int(i):
    c+=1
  else:
    cnt[st].append(c)
    c=1
    st=1-st
cnt[st].append(c)
cnt[0].append(0)
cnt[1].append(0)
sm=[[],[]]
s=0
for i in cnt[0]:
  s+=i
  sm[0].append(s)
s=0
for i in cnt[1]:
  s+=i
  sm[1].append(s)
sm[0][-1]=0
sm[1][-1]=0
if len(cnt[0])<=k+1:
  print(n)
else:
  m=0
  for i in range(len(cnt[0])-k):
    s=sm[0][i+k-1]-sm[0][i-1]+sm[1][min(i+k,len(cnt[1])-2)]-sm[1][i-1]
    m=max(s,m)
  print(m)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
now = 1
cnt = 0
Nums = []
for i in range(n):
    if s[i] == str(now): cnt += 1
    else:
        Nums.append(cnt)
        now = 1-now
        cnt = 1
if cnt != 0: Nums.append(cnt)

if len(Nums)%2 == 0: Nums.append(0)
ad = 2*k+1
# print(Nums)
ans = 0
left = right = 0
tmp = 0
for i in range(0,len(Nums),2):
    nextleft = i
    nextright = min(i+ad, len(Nums))
    while nextleft > left:
        tmp -= Nums[left]
        left += 1
    while nextright > right:
        tmp += Nums[right]
        right += 1
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
import collections
n,k = map(int, raw_input().split(' '))
s = map(int,list(raw_input()))
stack = []
count,i,j = 0,0,0


while(j < len(s)):
	while(j < len(s) and s[j] == s[i]): j += 1
	stack.append((s[i], j - i))
	i = j
r = 0
cl = 0
q = collections.deque([])
for t,l in stack:
	q.append((t,l))
	cl += l
	if t == 0: k -= 1
	while(k < 0 and q):
		tu,tl = q.popleft()
		cl -= tl
		if tu == 0: k +=1

	r = max(cl, r)
print r

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()+"2"
lst0 = [0]
lst1 = [0]
if s[0] == "0": lst1.append(0)
cnt = 0
for i in range(n):
    cnt += 1
    if s[i] != s[i+1]:
        if s[i] == "0": lst0.append(cnt)
        else: lst1.append(cnt)
        cnt = 0
l0 = len(lst0)
l1 = len(lst1)
k = min(k,l0-1)
for i in range(l0-1): lst0[i+1] += lst0[i]
for i in range(l1-1): lst1[i+1] += lst1[i]
# print(lst0)
# print(lst1)
ans = 0
for l in range(l0):
    r = min(l+k,l0-1)
    rr = r if r == l1-1 else r+1
    cnt = lst0[r]-lst0[l] + lst1[rr]-lst1[l]
    ans = max(cnt,ans)
print(ans)

Submission status: Accepted

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

S = S + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）
R=0
L=0
# 立った人の連続の数
if (S[0] == '0'):
    stand = 1
else:
    stand = 0
ans=0

for L in range(N):
    # 右端を進めることが可能（立った人の連続の数がK以下）なら、右端を進める
    while R < N and stand <= K:
        # 立った人の連続の数が増えるなら1足す（回数を消費しないといけない）
        if (S[R] == '1' and S[R + 1] == '0'):
            stand += 1
        R+=1#列を進める
        ans=max(ans,R-L)#答えを更新する
    if L == R:#同じ土俵に来たら
        R += 1
    else:#左だけ進めるとき
        if (S[L] == '0' and S[L + 1] == '1'):
            stand-=1
print(ans)

Submission status: Accepted

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

t = 1
#連続した0と1の人をまとめる
l = [0]

for i in s:
    i = int(i)
    if i == t: 
        l[-1] += 1
    else: 
        l += [1]
        t = i

if t < 1: 
    l += [0]
# print(l)

#累積和をとる
s = [0]

for i in l:
    s += [s[-1]+i]

# print(s)

a = 0

for i in range(0,len(l),2):
    # print("i", i)
    # print("s[i+1]", s[i+1])
    # print("s[i-k*2]", s[i-k*2])
    if i<2*k:
        a = max(a, s[i+1])
    else:
        a = max(a, s[i+1]-s[i-k*2])
print(a)

Submission status: Accepted

Solution code:
N,K = list(map(int, input().split()))
S = input()
# 0の塊をK回返して、1の連結をつくる
# K = 2 のとき
# ... 0:3,1:3,0:2,1:2,0:3,1:4,0:2,... のとき
# 1:2の両端をを返す→1始まりの5個の部分和
# 1の塊をK-1回返して、0の連結をつくり、最後にひっくり返す（端の1ともくっつく…）
# K = 2 のとき
# ... 0:3,1:3,0:2,1:2,0:3,1:4,0:2,... のとき
# 1:2を裏返す、0:2-1:2-0:3を返す　→　あれ一緒…？


# 0が端のときだけ気を付ければよさそう…
# 0が端にあったらひっくり返したA作って、Kを減らしておなじことやりゃよいのか？
# あとKが極端に小さいか、Arrayの数（0/1のパターン数より大きいとき）の考慮
# あとlen(A) = 1

# sequence数を格納するArrayを作る
A = []
pre = S[0]
cnt = 1
for i in range(1,N):
  now = S[i]
  if pre == now:
    cnt += 1
  else:
    A.append(cnt)
    cnt = 1
  pre = now
A.append(cnt)

#print(A)

if len(A) == 1:
  print(sum(A))
  exit(0)

# 貪欲でとってから前2個足して後ろ引く、見たいにやればO(N)でいけるはず…
# 部分和でも仕留められそうではあるけど…
def solve(Ar,Kr):
  l,r = 0, 2*Kr+1
  if len(Ar) < 2*Kr+1:
    #全部でよい
    return sum(Ar)
  wk = sum(Ar[l:r])
  ans = wk
  while r < len(Ar):
    wk = wk - Ar[l] - Ar[l+1] + Ar[r] + (Ar[r+1] if r+1 < len(Ar) else 0)
    ans = max(ans, wk)
    #print(wk,l,r,Ar[l],Ar[r])
    l,r = l+2, r+2
  return ans

if S[0] == '1':
  print(solve(A,K))
else:
  B = A[1:]
  B[0] += A[0] # 1始まりに無理やりする
  print(max(solve(A[1:],K), solve(B,K-1)))

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

prev = S[0]
i = 0
count = 0
run_length = []
if S[0] == '0':
    run_length.append(0)
while i < len(S):
    c = S[i]
    if c == prev:
        count += 1
    else:
        run_length.append(count) 
        count = 1
    prev = c
    i += 1
run_length.append(count) 

acc = [0] * (len(run_length) + 1)
acc[0] = 0

for i in range(len(acc) - 1):
    acc[i + 1] = acc[i] + run_length[i]

ans = 0
for i in range(0, len(acc), 2):
    j = 2 * K + 1
    x = 0
    if j + i >= len(acc):
        x = acc[-1] - acc[i]
    else:
        x = acc[j + i] - acc[i]
    ans = max(ans, x)

# for i in range(0, len(run_length), 2):
#     ans = max(ans, run_length[i])
# print(acc)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

prev = S[0]
i = 0
count = 0
run_length = []
if S[0] == '0':
    run_length.append(0)
while i < len(S):
    c = S[i]
    if c == prev:
        count += 1
    else:
        run_length.append(count) 
        count = 1
    prev = c
    i += 1
run_length.append(count) 

acc = [0] * (len(run_length) + 1)
acc[0] = 0

for i in range(len(acc) - 1):
    acc[i + 1] = acc[i] + run_length[i]

ans = 0
for i in range(0, len(acc), 2):
    j = 2 * K + 1
    x = 0
    if j + i >= len(acc):
        x = acc[-1] - acc[i]
    else:
        x = acc[j + i] - acc[i]
    ans = max(ans, x)

for i in range(0, len(run_length), 2):
    ans = max(ans, run_length[i])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
s = input() + "_"

compressed = []

first = s[0]
prev = s[0]
cnt = 1
for x in s[1:]:
    if prev == x:
        cnt += 1
    else:
        if x == "1":
            compressed.append(cnt)
            cnt = 1
        else:
            compressed.append(cnt)
            cnt = 1
    prev = x


result = [0] + list(accumulate(compressed))

ans = []
if first == "1":
    for i in range(0, len(result), 2):
        ans.append(result[min(i + k * 2 + 1, len(result) - 1)] - result[i])
    for j in range(1, len(result), 2):
        ans.append(result[min(j + k * 2, len(result) - 1)] - result[j])
else:
    for i in range(0, len(result), 2):
        ans.append(result[min(i + k * 2, len(result) - 1)] - result[i])
    for j in range(1, len(result), 2):
        ans.append(result[min(j + k * 2 + 1, len(result) - 1)] - result[j])

print(max(ans))

Submission status: Accepted

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n,k = rl()

s=rs()
now="1"
cnt=0

nums=[]
for i in s:
    if i==now:
        cnt+=1
    else:
        now=str(1-int(now))
        nums.append(cnt)
        cnt=1
if cnt!=0: nums.append(cnt)

if len(nums)%2==0:nums.append(0)
SUM=[0]
for i in range(len(nums)):
    SUM.append(SUM[i]+nums[i])

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

Submission status: Accepted

Solution code:
import sys

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

T=[]
t=1
k=0
for i in range(N):
    if t==S[i]:
        k+=1
    else:
        t^=1
        T.append(k)
        k=1
T.append(k)
if S[-1]==0:
    T.append(0)

X=len(T)
if K>=X//2:
    print(N)
    sys.exit()

M=sum(T[:2*K+1])
F=M
for i in range(X//2-K):
    F=F-(T[2*i]+T[2*i+1])+(T[2*(i+K)+1]+T[2*(i+K+1)])
    M=max(M,F)

print(M)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = str(input())
L = []
cnt = 0
x = '1'
for i in range(n):
    if s[i] == x:
        cnt += 1
    else:
        L.append(cnt)
        x = '0' if x == '1' else '1'
        cnt = 1
else:
    L.append(cnt)
syaku = sum(L[:2*k+1])
ans = syaku
for i in range(len(L)-2*k):
    syaku -= L[i]
    if i % 2:
        syaku += L[i+2*k]
        if i+2*k+1 < len(L):
            syaku += L[i+2*k+1]
    ans = max(ans, syaku)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
def main():
    n, k = list(map(int, input().split()))
    S = list(input())
    T = []
    V = []
    a, c = S[0], 0
    for s in S:
        if s == a:
            c += 1
        else:
            T.append(a)
            V.append(c)
            a = s
            c = 1
    T.append(a)
    V.append(c)

    V = np.cumsum(np.array(V))
    max_v = len(V)
    ans = 0
    for i, t in enumerate(np.array(T)):
        if t == '0':
            r = i + 2 * k - 1
        else:
            r = i + 2 * k
        if i == 0:
            ans = max(ans, V[min(max_v - 1, r)])
        else:
            ans = max(ans, V[min(max_v - 1, r)] - V[i - 1])
    print(ans)


if __name__ == '__main__':
    main()