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:
# solution

nim,mike=map(int,input().split())
data=input()
X=[]
Y=[0]
_s='2'
for i,s in enumerate(data):
  if _s!=s:
    _s=s
    X.append(i)
    Y.append((int(s)+1)%2)
import itertools
Y=list(itertools.accumulate(Y))
ans=[]
for i,x in enumerate(X):
  if Y[-1]-Y[i]<=mike:
    ans.append(nim-x)
    break
  else:
    if data[x]=='0':
      ans.append(X[i+2*mike]-x)
    else:
      ans.append(X[i+2*mike+1]-x)
print(max(ans))

Submission status: Accepted

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

key = [0]
for i in range(1, n):
  if s[i] != s[i-1]:
    key.append(i)
key.append(n)

m, r = 0, len(key)-1
ans = 0
while True:
  if m == 0 and s[0] == "0":
    p = m+2*k
    if ans < key[min([p, r])] - key[m]:
      ans = key[min([p, r])] - key[m]
    m += 1
  else:
    p = m+2*k+1
    if ans < key[min([p, r])] - key[m]:
      ans = key[min([p, r])] - key[m]
    m += 2
  if p >= r:
    break

print(ans)

Submission status: Accepted

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

def main():
    N, K = map(int, readline().rstrip().split())
    S = list(map(int, list(readline().rstrip())))

    cnt = []
    pre = S[0]
    S.append(-1)
    c = 1
    for s in S[1:]:
        if s == pre:
            c += 1
        else:
            cnt.append(c)
            pre = s
            c = 1
    
    if S[0] == 0:
        cnt = [0] + cnt
    if S[-2] == 0:
        cnt.append(0)
    
    K = K * 2 + 1
    ans = sum(cnt[:K])
    sc = ans
    for i in range(2, len(cnt)-K+1, 2):
        sc = sc - cnt[i-1] - cnt[i-2] + cnt[i+K-1] + cnt[i+K-2]
        ans = max(ans, sc)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# https://drken1215.hatenablog.com/entry/2019/04/14/222900
# 1が連続する個数の列に直す

SS = []
if S[0] == '0':
    SS.append(0)
i = 0
while i < len(S):
    j = i
    while j < len(S) and S[j] == S[i]:
        j += 1
    SS.append(j - i)
    i = j
if S[-1] == '0':
    SS.append(0)

# print(SS)

# 累積和
sums = [0 for _ in range(len(SS) + 1)]
for i in range(len(SS)):
    sums[i + 1] = sums[i] + SS[i]
# print(sums)

# 偶数番目からはじまる長さ (2K + 1) 区間の総和
ans = 0
for left in range(0, len(sums), 2):
    right = left + K * 2 + 1
    if right >= len(sums): # 飛び越したら末尾まで
        right = len(sums) - 1
    ans = max(ans, sums[right] - sums[left])
print(ans)

Submission status: Accepted

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

starts = [0]
ends = []

for i in range(1, n-1):
    if s[i] == '1' and s[i-1] == '0':
        starts.append(i)
    if s[i] == '1' and s[i+1] == '0' and len(starts) == len(ends) + 2:
        ends.append(i)

ends.append(n-1)

ans = 0
m = len(ends)
for i in range(m-k+1):
    ans = max(ans, ends[i+k-1] - starts[i] + 1)

if k >= m:
    ans = n

print(ans)

Submission status: Accepted

Solution code:
import sys

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

# zero[i] = [左からi番目連続した0の数, 左の連続した1の数,右の連続した1の数]
# s=00010 の時、zero=[[3, 0, 1], [1, 1, 0]]
zero = []
string = s[0]
count = 0; left = 0; right = 0; num = 0
for i in range(n):
	if s[i] == string:
		count += 1
	else:
		if string == '0':
			num = count
			string = '1'
		else:
			if num != 0:
				zero.append([num,left,count])
			string = '0'
			left = count
			num = 1
		count = 1

# 右端の数字が0か1かで処理が変わる
if string == '0':
	zero.append([count,left,0])
else:
	zero.append([num,left,count])

# kが十分に大きければ全員逆立ちする
if len(zero) <= k:
	print(len(s))
	sys.exit()

# 左からk個の連続した0を全て1にしたときの、
# 連続した1の個数をresに格納
res = 0
for i in range(k):
	res += zero[i][0] + zero[i][1]
res += zero[i][2]

# 左端を削除し、右端に1つ追加する
# 多分しゃくとり法
ans = res
for i in range(len(zero)-k):
	res -= zero[i][0] + zero[i][1]
	res += zero[i+k][0] + zero[i+k][2]
	ans = max(ans,res)

print(ans)

Submission status: Accepted

Solution code:
import sys

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

zero = []
string = s[0]
count = 0
left = 0
right = 0
num = 0
for i in range(n):
	if s[i] == string:
		count += 1
	else:
		if string == '0':
			num = count
			string = '1'
		else:
			if num != 0:
				zero.append([num,left,count])
			string = '0'
			left = count
			num = 1
		count = 1

if string == '0':
	zero.append([count,left,0])
else:
	zero.append([num,left,count])

if len(zero) <= k:
	print(len(s))
	sys.exit()
res = 0
for i in range(k):
	res += zero[i][0] + zero[i][1]
res += zero[i][2]

ans = res
for i in range(len(zero)-k):
	res -= zero[i][0] + zero[i][1]
	res += zero[i+k][0] + zero[i+k][2]
	ans = max(ans,res)

print(ans)

Submission status: Accepted

Solution code:
import sys

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

zero = []
one = []
string = s[0]
if string == '0':
	flag = True
else:
	flag = False
count = 0
left = 0
right = 0
num = 0
for i in range(n):
	if s[i] == string:
		count += 1
	else:
		if string == '0':
			num = count
			string = '1'
		else:
			one.append(count)
			if num != 0:
				zero.append([num,left,count])
			string = '0'
			left = count
			num = 1
		count = 1

if string == '0':
	zero.append([count,left,0])
else:
	zero.append([num,left,count])
	one.append(count)
#print(zero)
#print(one)
if len(zero) <= k:
	print(len(s))
	sys.exit()
res = 0
for i in range(k):
	res += zero[i][0] + zero[i][1]
res += zero[i][2]
#print(res)
ans = res
for i in range(len(zero)-k):
	res -= zero[i][0] + zero[i][1]
	#print(res)
	res += zero[i+k][0] + zero[i+k][2]
	#print(res)
	ans = max(ans,res)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = "#" + input()
B = []
L = []
for i in range(n):
  if s[i] != s[i+1]:
    B.append(int(s[i+1]))
    L.append(i+1)
ans = 0
for j, b in enumerate(B):
  if b == 0:
    if j+2*k >= len(L):
      ans = max(ans, n+1 - L[j])
    else:
      ans = max(ans, L[j+2*k] - L[j])
  else:
    if j+2*k+1 >= len(L):
      ans = max(ans, n+1 - L[j])
    else:
      ans = max(ans, L[j+2*k+1] - L[j])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
cnt=[]
now=s[0]
p=0
for i in range(n):
	if s[i]==now:
		p+=1
	else:
		cnt.append(p)
		now=s[i]
		p=1
cnt.append(p)
ans=0
r=[]
cum_sum=0
for i in range(len(cnt)):
	cum_sum+=cnt[i]
	r.append((cnt[i],cum_sum))
for i in range(len(r)):
	if s[r[i][1]-r[i][0]]=="1":
		e=r[min(i+2*k,len(r)-1)][1]-r[i][1]+r[i][0]
	else:
		e=r[min(i+2*k-1,len(r)-1)][1]-r[i][1]+r[i][0]
	ans=max(ans,e)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
s = readline().rstrip().decode()
cumsum = []
check = []
flag = True
for i in range(n):
    if s[i] == '0':
        if flag:
            cumsum.append(i)
        flag = False
    else:
        if not flag:
            check.append(i)
        flag = True
if not flag:
    check.append(n)
cumsum.append(n)
if len(cumsum) - 1 <= k:
    print(n)
else:
    ans = cumsum[k]
    for i in range(k, len(cumsum) - 1):
        ans = max(ans, cumsum[i + 1] - check[i - k])
    print(ans)

Submission status: Accepted

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

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

sub = []
for j in range(1, len(lst)):
    sub.append(S[lst[j - 1]:lst[j]])
# print(sub)
diff = [lst[i + 1] -lst[i] for i in range(len(lst) - 1)]
# print(diff)

if S[0] == '1' and len(lst) - 1 <= 2 * K + 1:
    print(N)
elif S[0] == '0' and len(lst) - 1 <= 2 * K:
    print(N)
else:
    candicate = []
    for i in range(len(lst) - 1 - K * 2):
        if S[lst[i]] == '1':
            candicate.append(lst[i + K * 2 + 1] - lst[i])
    if S[-1] == '0':
        candicate.append(lst[-1] - lst[-1 - K * 2])
    for i in range(len(lst) - K * 2):
        if S[lst[i]] == '0':
            candicate.append(lst[i + K * 2] - lst[i])
    # print(candicate)
    print(max(candicate))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
X=[]
Y=[0]
_s='2'
for i,s in enumerate(S):
  if _s!=s:
    _s=s
    X.append(i)
    Y.append((int(s)+1)%2)
import itertools
Y=list(itertools.accumulate(Y))
ans=[]
for i,x in enumerate(X):
  if Y[-1]-Y[i]<=K:
    ans.append(N-x)
    break
  else:
    if S[x]=='0':
      ans.append(X[i+2*K]-x)
    else:
      ans.append(X[i+2*K+1]-x)
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
    n, k = map(int, input().split())
    s = input()
    z = [len(i) for i in s.split("1") if i]
    o = [0] * (s[0] == "0") + [len(i) for i in s.split("0") if i] + [0]
    az = [0] + list(accumulate(z))
    ao = [0] + list(accumulate(o))
    if k < len(z):
        print(max(ao[i + k + 1] - ao[i] + az[i + k] - az[i] for i in range(len(z) - k + 1)))
    else:
        print(n)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 0か1の連続している人数のリスト、累積和
streak = [0, 0]
N, K = lr()
S = sr() + '2'
cur = 1
for i in range(N):
    if S[i] != S[i+1]:
        streak.append(cur)
        cur = 1
    else:
        cur += 1

streak_cum = list(itertools.accumulate(streak))
streak_cum.extend([streak_cum[-1], streak_cum[-1]])
if S[0] == '0':
    start = 0
else:
    start = 1
answer = 0

limit = len(streak_cum) - 1
for i in range(start, len(streak_cum), 2):
    result = streak_cum[min(limit, i+2*K+1)] - streak_cum[i]
    if result > answer:
        answer = result

print(answer)
# 52

Submission status: Accepted

Solution code:
from functools import reduce


def main():
    n, k = tuple(map(int, input().split()))
    s = input().strip()
    start = 0
    count_zero = {}

    for i, c in enumerate(s):
        if c == "0":
            if i == start:
                count_zero[start] = 0

            count_zero[start] += 1
        elif c == "1":
            start = i + 1

    if len(count_zero) <= k:
        print(n)
        return

    count_zero[-1] = 1
    count_zero[n] = 1

    count_zero_list = sorted(count_zero.items(), key=lambda pair: pair[0])

    print(reduce(lambda ans, i:
        max(ans, count_zero_list[i + k + 1][0] - (count_zero_list[i][0] + count_zero_list[i][1])),
        range(0, len(count_zero) - k - 1), 0))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
S = (stdin.readline().rstrip())
zero = []
one = []
tmp = 1
S += "@"

for i in range(N):
    if S[i] == S[i+1]:
        tmp += 1
    else:
        if S[i] == "0":
            zero.append(tmp)
        else:
            one.append(tmp)
        tmp = 1
        
if K >= len(zero):
    print(N)
else:
    if S[0] == "1":
        tmp = sum(zero[:K]) + sum(one[:K+1])
        ans = sum(zero[:K]) + sum(one[:K+1])

        for i in range(0,len(zero)-K):
            tmp -= zero[i]
            tmp += zero[i+K]
            tmp -= one[i]
            if not i+K+1 >= len(one):
                tmp += one[i+K+1]
            ans = max(ans,tmp)
        print(ans)
    else:
        tmp = sum(zero[:K]) + sum(one[:K])
        ans = sum(zero[:K]) + sum(one[:K])

        for i in range(0,len(zero)-K):
            tmp -= zero[i]
            tmp += zero[i+K]
            if i != 0:
                tmp -= one[i-1]
            if not i+K >= len(one):
                tmp += one[i+K]
            ans = max(ans,tmp)
        print(ans)

Submission status: Accepted

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

counts = []
_hd = head
_cnt = 0
for _s in s:
  if _s == _hd:
    _cnt += 1
  else:
    counts.append(_cnt)
    _hd = _s
    _cnt = 1
else:
  counts.append(_cnt)

acc = [0]
for c in counts:
  acc.append(acc[-1] + c)
if s[-1] == '0':
  acc.append(acc[-1])

ans = 1
if len(counts) <= 2*k:
  ans = len(s)
else:
  if head == '1':
    for i in range(2*k+1, len(acc)+1, 2):
      p = acc[i] - acc[i - (2*k+1)]
      ans = max(ans, p)
  else:
    for i in range(2*k, len(acc)+1, 2):
      p = acc[i] - acc[max(0, i-(2*k+1))]
      ans = max(ans, p)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
cnt = 1
arr0 = []
if s[0]=="1":
  arr = [0]
else:
  arr = [0,0]
for i in range(n-1):
  if s[i] == s[i+1]:
    cnt += 1
  else:
    arr0.append(cnt)
    cnt = 1
arr0.append(cnt)
arr += arr0
if s[n-1] == "0":
  arr.append(0)
lsum = [0]*(len(arr)//2)
lsum[0] = arr[0]+arr[1]
for i in range(1,len(arr)//2):
  lsum[i] = lsum[i-1]+arr[2*i]+arr[2*i+1]
arr = [0,0]+[0]*(s[0]=="0")+arr0+[0]*(s[n-1]=="1")
rsum = [0]*(len(arr)//2)
for i in range(1,len(arr)//2):
  rsum[i] = rsum[i-1]+arr[2*i]+arr[2*i+1]
ans = 0
if k >= len(lsum)-1:
  print(n)
  quit()
for i in range(k,len(lsum)):
  ans = max(ans,lsum[i]-rsum[i-k])
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s= input()
if n==1:
    print(1)
    exit()

ls = []
cnt=[0,0]
prev=int(s[0])
if prev==0:
    ls.append(0)
cnt[prev]+=1
for i in range(1,n):
    now= int(s[i])
    cnt[now] +=1
    if now!=prev:
        ls.append(cnt[prev])
        cnt[prev]=0
    prev = now
if cnt[now]!=0:
    ls.append(cnt[now])
if s[-1] =="0":
    ls.append((0))

##ls --> 1010..101の順

l=len(ls)//2+1
p = 0
idx = 0
ans =ls[0]
temp=ls[0]
for i in range(1,l):
    temp+= ls[2*i]+ls[2*i-1]
    ans = max(temp,ans)
    p+=1
    if p>=k:
        temp -= (ls[2*idx]+ls[2*idx+1])
        idx+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = str(input())
s += "2"
if int(s[0]) == 0:
  a = [0]
  prev = "0"
  count = 1
else:
  a = []
  flag = False
  prev = "1"
  count = 1
ap = a.append
for i in range(1,n+1):
  if s[i] == prev:
    count += 1
  else:
    ap(count)
    count = 1
    prev = s[i]
if s[-2] == "0":
  ap(0)
if 2*k+1 >= len(a):
  print(sum(a))
  exit()
g = sum(a[0:2*k+1])
mx = g
i = 1
while 2*i+2*k < len(a):
  g -= (a[2*i-2]+a[2*i-1])
  g += (a[2*i+2*k-1]+a[2*i+2*k])
  if g > mx:
    mx = g
  i += 1
print(mx)

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline
import numpy as np

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
S = input().rstrip() + "x"

# 連続する0,1の数を調べる
A = []
cnt = 1
for i in range(N):
    if S[i] == S[i+1]:
        cnt += 1
    else:
        A.append(cnt)
        cnt = 1

# 両端が1だと計算が楽、端が1でない場合、[0] を加えることで「偶数番目は1」になるようにする
if S[0] != "1":
    A = [0] + A
if S[N-1] != "1":
    A = A + [0]

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

from itertools import accumulate

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

S = input()

num = []

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

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

cnt = 1

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

if S[-2] == '0':
    num.append(0)

num = [0] + num

cum_sum = list(accumulate(num))


ans = 0
for i in range(0, len(cum_sum), 2):
    right = i + K * 2 + 1

    if right > len(cum_sum)-1:
        right = len(cum_sum) - 1

    ans = max(ans, cum_sum[right]-cum_sum[i])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,k = map(int,input().split())
sl = list(input())

d = deque([])
ans = 0
before = "1"
tmp = 0
p = 0
for s in sl:
    if before == s:
        p += 1
    else:
        d.append(p)
        tmp += p
        p = 1
        before = s
    if len(d) == 2 * k + 1:
        ans = max(tmp, ans)
        tmp -= d.popleft()
        tmp -= d.popleft()
else:
    d.append(p)
    tmp += p
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

t = []
c = '0'
v = 0
for i in range(n):
    if c != s[i]:
        t.append(v)
        v = 1
        c = s[i]
    else:
        v += 1
t.append(v)

r = 0
temp = 0
result = 0
for l in range(0, len(t), 2):
    while (r - l) // 2 + 1 <= k and r < len(t):
        temp += t[r]
        if r + 1 < len(t):
            temp += t[r + 1]
        r += 2
    result = max([temp, result])

    if r == l:
        r += 2
        if r - l < len(t):
            temp += t[r - 1] 
    else:
        temp -= t[l]
        if l - 1 > 0:
            temp -= t[l - 1]

print(result)

Submission status: Accepted

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

state = '1'
cnt = 0
start = 0
ret = 0

for i in range(len(s)):
    if state == '1' and s[i] == '0':
        cnt += 1
        if cnt <= k:
            length = i - start + 1
            ret = max(ret, length)
        else:
            has_zero = False
            while True:
                if has_zero and s[start] == '1':
                    break
                else:
                    if s[start] == '0':
                        has_zero = True
                    start += 1
            length = i - start + 1
            ret = max(ret, length)
        state = '0'
    elif state == '1' and s[i] == '1':
        length = i - start + 1
        ret = max(ret, length)
    elif state == '0' and s[i] == '0':
        length = i - start + 1
        ret = max(ret, length)
    else:
        state = '1'
        length = i - start + 1
        ret = max(ret, length)

print(ret)

Submission status: Accepted

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

now=S[0]
cnt=1
A=[] #個数配列
for i in range(n-1):
    if S[i+1]==now:
        cnt+=1
    else:
        A.append(cnt)
        cnt=1
        now=S[i+1]
if cnt>0:
    A.append(cnt)
l=len(A)
    
if S[0]=="0":
    if l<=2*k:
        ans=n
    elif 2*k+1<=l<=2*k+2:
        ans=max(sum(A[:2*k]),sum(A[1:]))
    else:
        ans=max(sum(A[:2*k]),sum(A[1:2*k+2]))
        cnt=sum(A[1:2*k+2])
        for i in range((l-2*k-2)//2):
            cnt-=A[2*i+1]+A[2*i+2]
            cnt+=A[2*k+2*i+2]+A[2*k+2*i+3]
            ans=max(cnt,ans)
        if l%2!=0:
            ans=max(sum(A[l-2*k:]),ans)
else:
    if l<=2*k+1:
        ans=n
    else:
        ans=sum(A[:2*k+1])
        cnt=ans
        for i in range((l-2*k-1)//2):
            cnt-=A[2*i]+A[2*i+1]
            cnt+=A[2*k+2*i+1]+A[2*k+2*i+2]
            ans=max(cnt,ans)
        if l%2==0:
            ans=max(sum(A[l-2*k:]),ans)
print(ans)

Submission status: Accepted

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

zero = []
tmp_zero_cnt = 0
tmp_zero_idx = -1
for i in range(N):
    if S[i] == "0":
        if tmp_zero_cnt == 0:
            tmp_zero_idx = i
        tmp_zero_cnt += 1
    else:
        if tmp_zero_cnt != 0:
            zero.append([tmp_zero_idx, tmp_zero_cnt])
            tmp_zero_cnt = 0
if tmp_zero_cnt != 0:
    zero.append([tmp_zero_idx, tmp_zero_cnt])

if len(zero) <= K:
    print(N)
else:
    zero = [[-1, 1]] + zero + [[N, 1]]
    M = len(zero)
    ans = 0
    for i in range(1, M - K):
        num = (zero[i + K][0] - 1) - (zero[i - 1][0] + zero[i - 1][1]) + 1
        if num > ans:
            ans = num
    print(ans)

Submission status: Accepted

Solution code:
N, K=map(int, input().split())
zeros=[0]
ones=[0]
S=list(input())
now=S[0]
one=0
zero=0
for i,s in enumerate(S):
  if s==now:
    if s=="0":
      zero+=1
    else:
      one+=1
  else:
    if s=="0":
      zero+=1
      ones.append(one)
      now=s
    else:
      one+=1
      zeros.append(zero)
      now=s
  if i==N-1:
    if s=="0":
      zeros.append(zero)
    else:
      ones.append(one)
#print(zeros, ones)
ans=0
lone=len(ones)
lzero=len(zeros)
if lzero==0:
  print(N)
  exit()
if lzero<=K:
  print(N)
  exit()

if S[0]=="0":
  
  for i in range(lzero-K+1):
    idx=min(i+K, lzero-1)
    idx2=min(idx, lone-1)
    idx3=max(i-1, 0)
    ans=max(ans, zeros[idx]-zeros[i]+ones[idx2]-ones[idx3])
    
else:
  for i in range(lzero-K+1):
    idx=min(i+K, lzero-1)
    idx2=min(idx+1, lone-1)
    
    ans=max(ans, zeros[idx]-zeros[i]+ones[idx2]-ones[i])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import accumulate

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

S = input()


num = []

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

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

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

num = [0] + num
cum_sum = list(accumulate(num))

ans = 0

for i in range(0, len(cum_sum), 2):
    right = i + K * 2 + 1
    if i + K * 2 >= len(cum_sum): 
        right = len(cum_sum) - 1

    ans = max(ans, cum_sum[right] - cum_sum[i])
print(ans)

Submission status: Accepted

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

data = [[],[]]
key = 1
cnt = 0
for i in range(n):
    if s[i] == key:
        cnt += 1
    
    else:
        data[key].append(cnt)
        key ^= 1
        cnt = 1
        
    if i == n-1:
        data[key].append(cnt)
    
if len(data[0]) == len(data[1]):
    data[1].append(0)

m = len(data[0])


if m <= k:
    print(n)
    exit()

tmp = data[1][0]
for i in range(k):
    tmp += data[0][i]
    tmp += data[1][i+1]

ans = tmp

for i in range(k,m):
    tmp -= data[0][i-k]
    tmp -= data[1][i-k]
    tmp += data[0][i]
    tmp += data[1][i+1]
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=list(input())
A=[]
a=1
c=0
for i in range(n):
  if int(S[i])==a:
    c=c+1
  else:
    A.append(c)
    a=(a+1)%2
    c=1
A.append(c)
if S[-1]=="0":
  A.append(0)
aa=len(A)
if k>=((aa-1)//2):
  print(n)
else:
  ans=0
  a=0
  for i in range(2*k+1):
    a=a+A[i]
  if a>ans:
    ans=a
  for i in range((aa-1)//2-k):
    a=a-A[2*i]-A[2*i+1]+A[2*(i+k)+1]+A[2*(i+k)+2]
    if a>ans:
      ans=a
  print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = str(input())
v = [0]
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    v.append(i+1)
ans = 0
arr = v + [n] *(2*k+1)
for i, j in enumerate(v):
  if s[j] == "0":
    ans = max(ans, arr[i+2*k]-arr[i])
  else:
    ans = max(ans, arr[i + 2*k +1] -arr[i])
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
n, k = map(int, input().split())
S = input().strip()
L = [len(list(g)) for v, g in groupby(S)]
if S[0] == '0':
    L = [0] + L
if S[-1] == '0':
    L = L + [0]

A = [sum(L[:2*k+1])]
for i in range(0, len(L)-2*k-1, 2):
    A += A[-1]-L[i]-L[i+1]+L[i+2*k+1]+L[i+2*k+2],
print(max(A))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
idx=[]
idx.append(0)
for i in range(1,n):
  if s[i]!=s[i-1]:
    idx.append(i)
arr=idx+[n]*(2*k+1)
ans=-10**18
z=0
for m in idx:
    if s[m]=='0':
      ans=max(ans,arr[z+2*k]-arr[z])
    else:
      ans=max(ans,arr[z+2*k+1]-arr[z])
    z+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7
    N,K = map(int, input().split())
    s = list(input().rstrip())
    l = []
    for k,v in groupby(s):
        l.append(len(list(v)))

    res = 0
    if s[0]=='1':
        start = 0
        stop = 2*K+1
        res = sum(l[:stop])
        ans = res
        while start<len(l):
            res += sum(l[stop:stop+2])-sum(l[start:start+2])
            ans = max(ans, res)
            start += 2
            stop += 2
    else:
        start = 1
        stop = 2*K+2
        res = sum(l[start:stop])
        ans = res
        while start<len(l):
            res += sum(l[stop:stop+2])-sum(l[start:start+2])
            ans = max(ans, res)
            start += 2
            stop += 2
        ans = max(ans, sum(l[:2*K]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

now = "1"
p = 0
l = []

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

l.append(p)

if s[n - 1] == "0":
    l.append(0)

m = len(l) // 2

ans = 1

if m <= k:
    ans = n
else:
    ans = sum(l[:2 * k + 1])
    nowans = ans
    for i in range(m - k):
        nowans += l[2*(k+i)+1] + l[2*(k+i+1)]
        nowans -= l[2*i] + l[2*i+1]
        ans = max(ans, nowans)

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

X = []
for c in S:
    if len(X) >= 1 and X[-1][0] == c:
        X[-1][1] += 1
    else:
        X.append([c, 1])

sm = [0] * (len(X) + 1)
for i in range(len(X)):
    sm[i + 1] = sm[i] + X[i][1]

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N + 1)
for l in range(N):
    if S[l] + S[l-1] == 0:
        continue
    while r < N and used[r] - used[l-1] <= K:
        r += 1
        if S[r-1] == 1 and S[r] == 0:
            used[r] = used[r - 1] + 1
        else:
            used[r] = used[r - 1]
    ans = max(ans, r-l)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
S = [int(s) for s in input()] + [1]

l = 0
r = -1
ans = 0
cnt = 0
tmp = ""
used = [0]*(N + 1)
for l in range(N):
    if S[l] + S[l-1] == 0:
        continue
    while r < N and used[r] - used[l-1] <= K:
        r += 1
        if S[r]:
            used[r] = used[r - 1]
        else:
            if S[r-1]:
                used[r] = used[r - 1] + 1
            else:
                used[r] = used[r - 1]
    ans = max(ans, r-l)

print(ans)