Problem:


Score : 400 points

Problem Statement

N people are arranged in a row from left to right.

You are given a string S of length N consisting of 0 and 1, and a positive integer K.

The i-th person from the left is standing on feet if the i-th character of S is 0, and standing on hands if that character is 1.

You will give the following direction at most K times (possibly zero):

Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.

Find the maximum possible number of consecutive people standing on hands after at most K directions.

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of consecutive people standing on hands after at most K directions.

Sample Input 1

5 1
00010

Sample Output 1

4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:

Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
X = []
cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        X.append(cnt)
        cnt = 0
    cnt += 1
    if i == N-1:
        X.append(cnt)
l = len(X)

if S[0] == '0' and (l+1)//2 <= K:
    print(N)
    exit()
if S[0] ==  '1' and l//2 <= K:
    print(N)
    exit()

ans = 0
result = 0
if S[0] == '0':
    for j in range(2*K):
        result += X[j]
    ans = result
    for j in range(2*K, l):
        if j == 2*K:
            result -= X[0]
        elif j%2 == 0:
            result = result - X[j-2*K] - X[j-2*K-1]
        result += X[j]
        ans = max(ans,result)
else:
    for j in range(2*K+1):
        result += X[j]
    ans = result
    for j in range(2*K+1, l):
        if j%2 == 1:
            result = result - X[j-2*K-1] - X[j -2*K]
        result += X[j]
        ans = max(ans, result)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
tmp = s[0]
cnt = 1
ss = []
if s[0] == '0':
    ss.append(0)

for i in range(1,n):
    if s[i] == tmp:
        cnt += 1
    else:
        tmp = s[i]
        ss.append(cnt)
        cnt = 1
ss.append(cnt)
if s[-1] == '0':
    ss.append(0)
ll = len(ss)

l = 0
r = k*2
tt = sum(ss[l:r+1])
ans = tt
while True:
    l += 2
    r += 2
    if r > ll:
        break
    tt += ss[r] + ss[r-1]
    tt -= ss[l-1] + ss[l-2]
    ans = max(ans, tt)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
tmp = s[0]
cnt = 1
ans = 0
ss = []
res = [0]
sum = 0
if s[0] == '0':
    ss.append(0)

for i in range(1,n):
    if s[i] == tmp:
        cnt += 1
    else:
        tmp = s[i]
        ss.append(cnt)
        cnt = 1
ss.append(cnt)
if s[-1] == '0':
    ss.append(0)
ll = len(ss)
for i in range(ll):
    sum += ss[i]
    res.append(sum)

if ll//2 <= k:
    print(n)
else:
    for i in range(ll-k*2)[::2]:
        ans = max(ans, res[i+k*2+1]-res[i])
    print(ans)

Submission status: Accepted

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

list10 = {'0':[],'1':[]}
pre_c='1'
c_c = 0
cur_sum = 0
cur_max = 0
for c in s:
    if c==pre_c:
        c_c += 1
    else:
        list10[pre_c].append(c_c)
        cur_sum += c_c
        c_c = 1
        pre_c = c
    if len(list10['1'])== k+1:
        cur_max = max(cur_max,cur_sum)
        cur_sum -= (list10['0'].pop(0) + list10['1'].pop(0))
print(max(cur_max,cur_sum+c_c))

Submission status: Accepted

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

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

key = int(s[0])
for i in range(n):
    if int(s[i]) == key :
        A[-1] += 1
    else:
        A.append(1)
        key = (key+1) % 2

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

#print(A)

la = len(A)

le = -1
ri = k*2
ans = sum(A[:ri])
mans = ans
while ri < la:
    minus = A[le] if le >= 0 else 0
    plus = A[ri+1] if ri+1 <= la-1 else 0
    ans = ans - minus - A[le+1] + A[ri] + plus 
    mans = max(mans, ans)
    #print(A[le+2:ri+2],mans)
    le += 2
    ri += 2

A = [A[-(i+1)] for i in range(la)]
#print(A)

le = -1
ri = k*2
ans = sum(A[:ri])
mans = max(mans, ans)
while ri < la:
    minus = A[le] if le >= 0 else 0
    plus = A[ri+1] if ri+1 <= la-1 else 0
    ans = ans - minus - A[le+1] + A[ri] + plus 
    mans = max(mans, ans)
    #print(A[le+2:ri+2],mans)
    le += 2
    ri += 2

print(mans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
s = input()
s = s + "2"
li_0 = []
li_1 = []
ct = 1
for i in range(n):
    if s[i] != s[i+1]:
        if s[i] == '0':
            li_0.append(ct)
            ct = 1
        else:
            li_1.append(ct)
            ct = 1
    else:
        ct += 1
if len(li_0) <= k:
    print(len(s)-1)
else:
    li_0 = deque(li_0)
    li_1 = deque(li_1)
    if s[0] == "0":
        li_1.appendleft(0)
    li_1.append(0)
    Sum_0 = sum(li_0[i] for i in range(k))
    Sum_1 = sum(li_1[i] for i in range(k+1))
    Max = Sum_0 + Sum_1
    for i in range(len(li_0)-k):
        Sum_0 = Sum_0 - li_0[i] + li_0[i+k]
        Sum_1 = Sum_1 - li_1[i] + li_1[i+k+1]
        Max = max(Max, Sum_0 + Sum_1)
    print(Max)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
count = 0
l = []
count1 = 0
for i in range(n):
    if s[i] == "0":
        if count > 0:
            l.append(count)
            count = -1
        else:
            count -= 1
    else:
        if count < 0:
            l.append(count)
            count = 1
            count1 += 1
        else:
            count += 1
l.append(count)
if count < 0:
    count1 += 1
m = len(l)
count2 = 0
ans = []
if l[0] < 0:
    p = 0
else:
    p = 1
if count1 > k:
    x = 0
    ans1 = 0
    while count2 < k:
        if l[x] > 0:
            ans1 += l[x]
            x += 1
        else:
            ans1 += abs(l[x])
            x += 1
            count2 += 1
    ans1 += abs(l[x])
    ans.append(ans1)
    while x < m-2:
        if p > 0:
            ans1 = ans1 - abs(l[p]) - abs(l[p-1]) + abs(l[x+1]) + abs(l[x+2])
            p += 2
            x += 2
        else:
            ans1 = ans1 - abs(l[p]) + abs(l[x+1]) + abs(l[x+2])
            p += 2
            x += 2
        ans.append(ans1)
    if x == m-2:
        if p > 0:
            ans1 = ans1 - abs(l[p]) - abs(l[p-1]) + abs(l[x+1])
            p += 2
            x += 2
        else:
            ans1 = ans1 - abs(l[p]) + abs(l[x+1])
            p += 2
            x += 2
        ans.append(ans1)
    print(max(ans))
else:
    print(n)

Submission status: Accepted

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
s = S()

left_List = [0]
left = 0
flag = ""
cnt = 0
j = 0
ans = 0
for i in range(N):
  if i != 0:
    if flag == 0:
      if s[i] == "1":
        left_List.append(i)
        cnt += 1
    else:
      if cnt >= K:
        if s[i] == "0":
          ans = max(ans, i-left_List[j])
          j += 1

  if s[i] == "0":
    flag = 0
  else:
    flag = 1

else:
  ans = max(ans, N-left_List[j])

print(ans)

Submission status: Accepted

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

compress = []
now = '1'
count = 0
for s in S:
    if s != now:
        compress.append(count)
        now = s
        count = 1
    else:
        count += 1
compress.append(count)

length = len(compress)
candidate = sum(compress[:2*k+1])
ans = candidate
if length <= 2*k+1:
    print(ans)
    exit()

for i in range(0, length-2*k-1, 2):
    if 2*k+2+i < length:
        candidate += compress[2*k+1+i] + compress[2*k+2+i] - compress[i] - compress[i+1]
    else:
        candidate += compress[2*k+1+i] - compress[i] - compress[i+1]
    ans = max(ans, candidate)

print(ans)

Submission status: Accepted

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

A=[]

if s[0]!='1':A.append(0)

cnt=1
pre=s[0]
for i in s[1:]:
	if pre!=i:
		A.append(cnt)
		cnt=1
		pre=i
	else:
		cnt+=1

if (s[-1]=='1' and len(A)%2==0) or (s[-1]=='0' and len(A)%2!=0):
	A.append(cnt)


if s[-1]!='0':
	A.append(0)
A.append(0)

dp=[0]*(len(A)//2-K+1)

if (2*K+1)>=len(A):print(sum(A))
else:
	for i in range(2*K+1):dp[0]+=A[i]
	
	i=1
	idx=0
	while len(dp)>i:
		dp[i]=dp[i-1]-A[idx]-A[idx+1]+A[idx+2*(K+1)]+A[idx-1+2*(K+1)]
		idx+=2
		i+=1
	
	print(max(dp))

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    A = []
    for j in range(N):
        if j == 0:
            cur = S[j]
            i = 0
        else:
            if S[j] != cur:
                A.append([j-i, cur])
                i = j
                cur = S[j]
    A.append([N-i, cur])
    queue = []
    count = 0
    tot = 0
    ans = 0
    # print(S)
    # print(A)
    for i in range(len(A)):
        c, s = A[i]
        if count < K:
            if s == "0": count += 1
        elif count == K:
            if s == "0":
                c1, s1 = queue.pop(0)
                tot -= c1
                if s1 == "1":
                    c2, s2 = queue.pop(0)
                    tot -= c2
        queue.append([c, s])
        tot += c
        # print(tot)
        ans = max(ans, tot)
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

import copy

def main(): 

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

    list_01 = []
    now=1
    count=0
    for i in range(N):
        if int(S[i]) != now:
            list_01.append(count)
            now=1-now
            count=1
        else:
            count+=1
    if count != 0: list_01.append(count)
    if len(list_01)%2==0: list_01.append(0)
    
    Add = 2*K+1
    left = 0
    right = 0
    ans=0
    i=0
    tmp = 0
    while i < len(list_01):
        nextleft = i
        nextright = min(i+Add,len(list_01))

        while left < nextleft:
            tmp-=list_01[left]
            left+=1
        while right < nextright:
            tmp+=list_01[right]
            right+=1
        ans=max(tmp,ans)
        i+=2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N,K = map(int, input().split())
    S = input()
    flag = S[0]
    count = 0
    A = [1]
    count0 = 0
    if S[0] == "0":
        count0 += 1
    
    for i in range(1,len(S)):
        if S[i] == flag:
            A[count] += 1
        else:
            A.append(1)
            count += 1
            flag = S[i]
            if S[i] == "0":
                count0 += 1
    
    if count0 <= K:
        answer = N
        print(answer)
    else:
        head = 0
        tail = 0
        if S[0] == "0":
            head = sum(A[:2*K])
            if A != []:
                A.pop(0)
        if S[-1] == "0":
            tail = sum(A[::-1][:2*K])
            if A != []:
                A.pop(-1)
        g = min(len(A),2*K+1)
        tmp = sum(A[:g])
        MAX = sum(A[:g])
        s = 0
        while g  < len(A):
            tmp += - A[s] - A[s+1] + A[g] + A[g+1]
            if MAX < tmp:
                MAX = tmp
            s += 2
            g += 2
        print(max(MAX,head,tail))
    
main()

Submission status: Accepted

Solution code:
from itertools import groupby

N, K = [int(i) for i in input().split()]
S = input()

A = [(int(k), len(tuple(v))) for k, v in groupby(S)]
M = len(A)

ans, count = 0, 0
r = 0
for l, (kl, al) in enumerate(A):
    bound = 2 * K + kl
    while r < M and r - l < bound:
        count += A[r][1]
        r += 1
    ans = max(ans, count)
    count -= al

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

N, K = [int(i) for i in input().split()]
S = input()

A = [(k, len(tuple(v))) for k, v in groupby(S)]
M = len(A)

ans, count = 0, 0
l, r = 0, 0
while l < M:
    bound = 2 * K + int(A[l][0] == '1')
    while r < M and r - l < bound:
        count += A[r][1]
        r += 1
    ans = max(ans, count)
    count -= A[l][1]
    l += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate

N, K = [int(i) for i in input().split()]
S = input()

A = [(k, len(tuple(v))) for k, v in groupby(S)]
M = len(A)

ans, count = 0, 0
l, r = 0, 0
while l < M:
    bound = 2 * K
    if A[l][0] == '1':
        bound += 1
    while r < M and r - l < bound:
        count += A[r][1]
        r += 1
    ans = max(ans, count)
    count -= A[l][1]
    l += 1

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
zeros = []
count = 1
if S[0] == "0":
    zeros.append(0)
for i in range(N):
    if i + 1 == N or S[i] != S[i + 1]:
        zeros.append(count)
        count = 1
    elif S[i] == S[i + 1]:
        count += 1
if S[-1] == "0":
    zeros.append(0)
M = len(zeros)
ans = sum(zeros[0:2 * K + 1])
temp = ans
for l in range(2, M - 2 * K, 2):
    temp += zeros[l + 2 * K - 1] + zeros[l + 2 * K] - zeros[l - 2] - zeros[l - 1]
    ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
array = []
count = 1
if S[0] == "0":
  array.append(0)
for i in range(N):
  if i+1 == N or S[i] != S[i+1]: 
    array.append(count)
    count = 1
  elif S[i] == S[i+1]:
    count += 1
if S[-1] == "0":
  array.append(0)
M = len(array)
ans = sum(array[0:2*K+1])
tmp = ans
for l in range(2,M-2*K,2):
  tmp -= array[l-2] + array[l-1]
  tmp += array[l+2*K-1] + array[l+2*K]
  ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def main(s, k, n):
    candidate = []
    prev = "1"
    count = 0
    for char in s:
        if prev == char:
            count += 1
        else:
            candidate.append(count)
            count = 1
        prev = char

    candidate.append(count)
    if prev == "0":
        candidate.append(0)

    w = 2 * k + 1
    if len(candidate) <= w:
        return len(s)

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

    return score


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

print(main(s, k, n))

Submission status: Accepted

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


    cnt = 0
    right = 0
    flag = 1
    j = k + 1 if s[0] == '1' else k
    for i in range(n - 1):
        if s[i]  == '1' and s[i + 1] == '0':
            cnt += 1
        if cnt == j:
            right = i + 1
            flag = 0
            break


    if flag:
        return n


    left = 0
    ret = right - left
    flag = 0

    while True:
        while True:
            if right + 1 >= n:
                flag = 1
                break
            if s[right] == '1' and s[right + 1] == '0':
                right += 1
                break
            right += 1
        while True:
            if s[left] == '0' and s[left + 1] == '1':
                left += 1
                break
            left += 1
        if flag:
            right += 1
        ret = max(ret, right - left)
        if flag:
            break
    return ret


print(main())

Submission status: Accepted

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値

L=1
count=0
L2=[1]
for i in range(n):
    if i>=1:
        count-=1
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1):
            if s[j-1]==str(0):
                L2.append(j)
                
            
        if count==k+1:
            
            ans=max(ans,j-L2[i])
            #次はｊ+１から始める
            L=j+1
            break
            
        if s[j]=='E':
            ans=max(ans,j-L2[i])
            print(ans)
            exit()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
l = []
count = 0
for i in range(n):
  count += 1
  if i == n-1:
    l.append(count)
  elif s[i] != s[i+1]:
    l.append(count)
    count = 0
if s[0] =="0":
  l = [0] + l
left = 0
count = 0
point = 0
ans = 0
for i in l:
  point += i
  count += 1
  ans = max(ans, point)
  if count > k*2:
    point -= (l[left]+l[left+1])
    left += 2
    if left >= len(l)-1:
      break
    count-=2
print(ans)

Submission status: Accepted

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

sp = "1"
count = 0
cu = []
cd = []
for i in range(n):
    if sp == s[i]:
        count += 1
    else:
        if sp == "1":
            cu.append(count)
        else:
            cd.append(count)
        count = 1
    sp = s[i]
if sp == "1":
    cu.append(count)
else:
    cd.append(count)
ans = 0
for i in range(len(cd)):
    ld = i
    rd = min(i + k - 1, len(cd)-1)
    lu = i
    ru = min(rd+1,len(cu)-1)        
    if i == 0:
        sn = 0
        sn += sum(cd[ld:rd+1])
        sn += sum(cu[lu:ru+1])
    else:
        if ldp < ld:
            sn-=cd[ldp]
        if rdp < rd:
            sn+=cd[rd]
        if lup < lu:
            sn-=cu[lup]
        if rup < ru:
            sn+=cu[ru]
    ans = max(ans,sn)
    ldp,rdp,lup,rup = ld,rd,lu,ru
if len(cd)==0:
    ans = n
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
S = input().replace("01", "0 1").replace("10", "1 0").split()
S = [""]*("0" in S[0])+S+[""]*("0" in S[-1])
*L, = map(len, S)
A = [sum(L[:2*k+1])]
for i in range(0, len(S)-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:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,K = II()
S = str(input())

num = 0
for i in range(N):
    if i==N-1:
        print(N)
        exit()
    if S[i]=='0' and S[i+1]=='1':
        num += 1
        place = i+1
    if num==K:
        break

if num<K:
    print(N)
    exit()

for i in range(place+1,N):
    if i==N-1 and S[i]=='1':
        print(N)
        exit()
    if S[i]=='0':
        break

place = i-1

ans = place+1

for i in range(1,N):
    if S[i-1]=='0' and S[i]=='1':
        val = N-1
        for j in range(place+2,N):
            val = j
            if j==N-1:
                break
            if S[j]=='1' and S[j+1]=='0':
                break
        if val-i+1>ans:
            ans = val-i+1
        place = val

print(ans)

Submission status: Accepted

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

mxl = []
Sl = []
c = 0
if S[0] == "0":
  Sl.append(0)
for i in range(N-1):
  c += 1
  if S[i] != S[i+1]:
    Sl.append(c)
    c = 0
if S[N-1] == "0":
  c += 1
  Sl.append(c)
  Sl.append(0)
else:
  c += 1
  Sl.append(c)

Kl = K*2+1

Ru = [0 for i in range(len(Sl)+1)]

if len(Sl) ==1:
  mxl.append(Sl[0])
else:
  for i in range(1,len(Sl)+1):
    Ru[i] = Ru[i-1]+Sl[i-1] 
  mxl.append(Ru[min(Kl,len(Ru)-1)])
  
for i in range(2,min(len(Sl)+1-Kl,len(Ru)-1),2):
  mxl.append(Ru[Kl+i]-Ru[i])

print(max(mxl))

Submission status: Accepted

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

  from itertools import groupby

  tmp = []
  num = []
  for ke, v in groupby(s):
    num.append(ke)
    tmp.append(len(list(v)))
  
  num += [0]
  tmp += [0]

  nt = len(tmp)
  wa = [0] * (nt+1)
  for i in range(nt):
    wa[i+1] = wa[i] + tmp[i]

  ans = 0
  for i in range(len(wa)):
    x = k*2
    if num[i] == "1":
      x += 1
    try:
      ans = max(ans, wa[i+x] - wa[i])
    except:
      break
  if not ans:
    ans = len(s)
  print(ans)

main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return

#B
def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return

#C
def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return

#D
def D():
    h,w = LI()
    n = I()
    a = LI()
    ans = [0]*h*w
    p = 0
    for i in range(n):
        for j in range(a[i]):
            ans[p+j] = i+1
        p += a[i]
    for i in range(h):
        s = ans[i*w:(i+1)*w]
        if i%2:
            print(*s[::-1])
        else:
            print(*s)
    return

#E
def E():
    n,k = LI()
    s = [int(x) for x in input()]
    f = [0]*n
    j = 0
    su = 1
    p = s[0]
    for i in range(1,n):
        if s[i] != p:
            f[j] = su
            j += 1
            su = 1
            p = s[i]
        else:
            su += 1
    f[j] = su
    f.append(0)
    if s[0]:
        m = sum(f[:2*k+1])
        ans = m
        for i in range(2*k+1,n):
            m -= f[i-2*k-1]
            if not i%2:
                m += f[i-1]
                m += f[i]
            ans = max(m,ans)
    else:
        m = sum(f[:2*k])
        ans = m
        for i in range(2*k,n):
            m -= f[i-2*k]
            if not i%2:
                m += f[i]
                m += f[i+1]
            ans = max(m,ans)
    print(ans)
    return

#F
def F():

    return

#G
def G():

    return

#H
def H():

    return

#I
def I_():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
# ABC124D - Handstand
def main():
    N, K = tuple(map(int, input().split()))
    S = input()
    A = [i for i in range(1, N) if S[i] != S[i - 1]]
    # change to start and end with length of "1"
    A = [0] + A if S[0] == "1" else [0, 0] + A
    A += [N] if S[-1] == "1" else [N, N]
    
    l, x = len(A), K * 2 + 1
    if l <= x:  # possible to change all to "1"
        print(N)
    else:
        # check all sections of the length x
        ans = max(A[i + x] - A[i] for i in range(0, l - x + 1, 2))
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

judge=[0]
max_=0
for i in range(n-1):
  if s[i]!=s[i+1]:
    judge.append(i+1)
judge.append(n)

if len(judge)//2<=k:
  print(len(s))
else:
  for i in range(len(judge)-1):
    if s[judge[i]]=='0':
      ans=judge[min(i+2*k,len(judge)-1)]-judge[i]
    else:
      ans=judge[min(i+2*k+1,len(judge)-1)]-judge[i]
    if ans>max_:
      max_=ans
  print(max_)

Submission status: Accepted

Solution code:

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

    counts = [0]
    last = "1"
    for s in S:
        if s == last:
            counts[-1] += 1
        else:
            counts += [1]
            last = s
    if S[-1] == "0":
        counts += [0]
    l, r = 0, K * 2 + 1
    max_c = sum(counts[l:r])
    current_c = max_c
    while r < len(counts):
        current_c -= (counts[l] + counts[l + 1])
        l += 2
        current_c += (counts[r] + counts[r + 1])
        r += 2
        max_c = max(max_c, current_c)
    print(max_c)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, K: int, S: int):
    A = []
    c = ''
    for i, s in enumerate(S):
        if s != c:
            A.append(i)
        c  = s
    m = []
    for k, ik in enumerate(A):
        if S[ik] == '0':
            if k+2*K >= len(A):
                h = N
            else:
                h = A[k+2*K]
            m.append(h-ik)
        else:
            if k+2*K+1 >= len(A):
                h = N
            else:
                h = A[k+2*K+1]
            m.append(h-ik)
    print(max(m))
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = list(map(int,input().split()))
S = input()
 
n = 1
c = []
if S[0]=='0':
  c.append(0)
for i in range(1,N):
    if S[i]!=S[i-1]:
        c.append(n)
        n=1
    else:
        n+=1
c.append(n)
if S[-1]=='0':
  c.append(0)

# print(c)

t = sum(c[:2*K+1])
m = t
# print(t)
for i in range(2*K+1, len(c), 2):
  t += c[i] + c[i+1] - c[i-(2*K+1)] - c[i+1-(2*K+1)]
  # print(t)
  m = max(m,t)

print(m)

Submission status: Accepted

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

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

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

X = []
for i in range(len(p)):
    if s[p[i]] == "1":
        li = i
        ri = i + 2 * k + 1
    else:
        li = i-1
        if li < 0:
            li = 0
        ri = i + 2 * k
    if ri > len(p)-1:
        x = n - p[li]
    else:
        x = p[ri] - p[li]
    X.append(x)
print(max(X))

Submission status: Accepted

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

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

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

X = []
for i in range(len(p)-1):
    if s[p[i]] == "1":
        li = i
        ri = i + 2 * k + 1
        if ri >= len(p)-1:
            ri = len(p)-1
        x = p[ri] - p[li]
    else:
        li = i-1
        if li < 0:
            li = 0
        ri = i + 2 * (k-1) + 1
        if ri >= len(p)-1:
            x = n - p[li]
        else:
            x = p[ri] - p[li] + 1
    X.append(x)
print(max(X))

Submission status: Accepted

Solution code:
# coding:utf-8
import sys
from collections import deque
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = False

def main():
    N,K = LMIIS()
    S = input().strip()
    nums = []
    count = 0
    conti = '0'
    for s in S:
        if s == conti:
            count += 1
        else:
            conti = s
            nums.append(count)
            count = 1
    nums.append(count)
    nums.append(0)
    

    i = 0
    tmpsum = sum(nums[:2*K])
    max_c = tmpsum
    for i in range(2*K+1,len(nums),2):
        tmpsum = tmpsum - nums[i- 2*K -1] - nums[i- 2*K] + nums[i-1] + nums[i]
        max_c = max(max_c,tmpsum)
    
    tmpsum = sum(nums[1:2*K+2])
    max_c = max(max_c,tmpsum)
    for i in range(2*K+3,len(nums),2):
        tmpsum = tmpsum - nums[i- 2*K -2] - nums[i-2*K -1] + nums[i-1] + nums[i]
        max_c = max(max_c,tmpsum)

    print(max_c)
        


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if s[0] == '1':
    length_01 = [0]
else:
    length_01 = [0,0]

for i in range(n-1):
    if s[i] != s[i+1]:
        length_01.append(i+1)

if s[n-1] == '1':
    length_01.append(n)
else:
    length_01.append(n)
    length_01.append(n)

num_0 = int(len(length_01)/2)
if num_0 - k >= 1:
    answer = 0
    for i in range(num_0 - k):
        if answer < length_01[2*(i+k)+1] - length_01[2*i]:
            answer = length_01[2*(i+k)+1] - length_01[2*i]
else:
    answer = n

print(answer)