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: Time Limit Exceeded

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

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

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

ans = 0
for i in range(len(counts)):
    if i % 2 == 1:
        continue
    ans = max(ans, sum(counts[i: i + 2 * K + 1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
S = input()
nowL = 0
if S[0] == '0':
    nowL = 1
L = [0] * N
for i in range(N-1):
    if S[i] == S[i+1]:
        L[nowL] = L[nowL] + 1
    else:
        L[nowL] = L[nowL] + 1
        nowL = nowL + 1
# 終端処理
L[nowL] = L[nowL] + 1

ans = 0
for j in range(N):
    ans = max(ans,sum(L[2*j:2*j+2*K+1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,K = list(map(int,input().split()))
        S = np.asarray(list(map(int,list(str(input())))))
    else:
        pass
    SN = np.asarray([])
    first = S[0]
    tmpnum = first
    if first == 0:
        SN = np.append(SN,0)
    SN = np.append(SN,0)

    count = 0
    for n in range(N)[1:]:
        if S[n] == tmpnum:
            count += 1
        else:
            count += 1
            SN = np.append(SN,count)
            #count = 0
            tmpnum = S[n]
    else:
        count += 1
        SN = np.append(SN,count)
        if tmpnum == 0:
            SN = np.append(SN,count)

    max = 0
    flag = 0
    for n in range(SN.size)[2*K+1::2]:
        if max < SN[n] - SN[n-2*K-1]:
            max = SN[n] - SN[n-2*K-1]
        flag = 1
    if flag == 0:
        print(int(SN[-1]-SN[0]))
    else:
        print(int(max))

if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

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

first = S[0]
sakadachi = [ len(x) for x in S.split('0') if x != '' ]
normal = [ len(x) for x in S.split('1') if x != '' ]

# normal[0] sakadachi[0] normal[1] ... to sakadachi[0] normal[0] sakadachi[1] ...
if first == '0':
    sakadachi = [0] + sakadachi

n_normal = K
n_sakadachi = K+1
res = 0
for i in range(len(sakadachi)):
    people = sum(sakadachi[i:i+n_sakadachi]) + sum(normal[i:i+n_normal])
    if res < people:
        res = people
print(res)

Submission status: Time Limit Exceeded

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

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    if s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        if s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 

anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))

Submission status: Time Limit Exceeded

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

a = []
b = []
before_num = '0'
count = 0
for i in range(N):
  if before_num==S[i]:
    count+=1
  else:
    if before_num=='0':
      a.append(count)
    else:
      b.append(count)
    before_num = S[i]
    count = 1
  if i==N-1:
    if before_num=='0':
      a.append(count)
    else:
      b.append(count)
b += [0]

if len(a)<=K:
  print(N)
  exit()
max_count = 0
for i in range(0,len(a)-K+1):
  count = sum(a[i:i+K])
  if i==0:
    count+=sum(b[i:i+K])
  else:
    count+=sum(b[i-1:i+K])
  max_count = max(count, max_count)
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = '0' + input()
t = s
flag = False
anss = []
for p in range(n):
    ans = 0
    k = m
    s = s[1::]
    for i, char in enumerate(s):
        if char == '1':
            ans += 1
            if flag:
                flag = False
        else:
            if k == 0 and not flag:
                break
            elif not flag:
                k -= 1
                flag = True
                ans += 1
            else:
                ans += 1
    anss.append(ans)
print(max(anss))

Submission status: Time Limit Exceeded

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

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    if s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        if s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
sumlist = []
for i in range(len(li)):
    sumlist.append(sum(li[i:len(li)]))
sumlist.append(0)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = sumlist[i] - sumlist[min(len(li), i+pivot+1)]
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = sumlist[i] - sumlist[min(len(li), i+pivot+1)]
            anslist.append(tmp)
    anslist.append(sumlist[0] - sumlist[min(len(li), pivot)])

print(max(anslist))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

first = s[0]
end = s[-1]
len_list = []

count = 0
pre = first
for i in range(n):
    if s[i] == pre:
        count += 1
    else:
        len_list.append(count)
        pre = s[i]
        count = 1
len_list.append(count)

size = len(len_list)

if size < 2*k + 1:
    print(n)
else:
    ans = 0
    index = 0
    if first == '0':
        index = 1
        ans = sum(len_list[:2*k])
    if end == '0':
        ans = max(sum(len_list[size-2*k:]), ans)

    while index + 2 * k < size:
        ans = max(ans, sum(len_list[index: index+2*k+1]))
        index += 2

    print(ans)

Submission status: Time Limit Exceeded

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

num = [0]
which = s[0]
sign = [which]
for i in s:
  if i != which:
    which = 1-which
    num.append(0)
    sign.append(which)
  num[-1] += 1

if k >= len(sign) - sum(sign):
  print(sum([abs(i) for i in num]))
  exit()

#print(num)
#print(sign)

if sign[0] == 0:
  num = [0] + num

if sign[-1] == 0:
  num.append(0)

#print(num)

ans = 0
for i in range(0,len(num),2):
  ans_tmp = sum(num[i:i+2*k+1])
  #print(i,i+2*k,ans_tmp)
  if ans_tmp > ans:
    ans = ans_tmp
    
print(ans)

Submission status: Time Limit Exceeded

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

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

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

ss = array_count(s)

if ss[0][0] == 0:
    ss = [[1,0]] + ss

if ss[-1][0] == 1:
    ss.append([0,0])

ans = -1
for i in range(int(len(ss) / 2)):
    cnt = 0
    for j in range(k*2+1):
        if i*2 + j >= len(ss):
            break
        cnt += ss[i*2+j][1]
    ans = max(ans,cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, k = map(int, input().split())
s = input()
temp = ""
ans = []
c = 0
for s_ in s:
    if temp != s_:
        if s_ == "0":
            ans.append(c)
            temp = "0"
            c = -1
        else:
            ans.append(c)
            temp = "1"
            c = 1
    else:
        if s_ == "0":
            c -= 1
        else:
            c += 1
ans.append(c)
ans = ans[1:]
c = []
t = [i for i in range(len(ans)) if ans[i] < 0]
aaa = []
for v in itertools.combinations(t, k):
    anst = ans.copy()
    for v_ in v:
        anst[v_] *= -1
    c_ = 0
    for s_ in anst:
        if s_ > 0:
            c_ += s_
        else:
            aaa.append(c_)
            c_ = 0
    aaa.append(c_)
if len(aaa) > 0:
    print(max(aaa))
else:
    print(len(s))

Submission status: Time Limit Exceeded

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

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

is_handstood = False
cnt = 0

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

max_human = 0

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

print(max_human)

Submission status: Time Limit Exceeded

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

change_points = [i for i in range(n) if i == 0 or s[i-1] != s[i]]
max_ = 0
for i in change_points:
    count = 0
    cur_k = 0
    is_zero = False
    for c in s[i:]:
        if len(s[i:]) < max_:
            break
        if c == '1':
            count += 1
            is_zero = False
        else:
            if is_zero:
                count += 1
            elif cur_k < k:
                cur_k += 1
                count += 1
                is_zero = True
            else:
                break
    if count > max_:
        max_ = count
print(max_)

Submission status: Time Limit Exceeded

Solution code:
#D問題
N,K=map(int,input().split())
S=str(input())
Slist=list(S)
#偶数が”1”
hu=[]
ima=""
imal=0
for i in range(N):
    if i == 0:
        ima=Slist[0]
        imal=1
        if Slist[0] == "0":
            hu.append(0)
    else:
        if ima==Slist[i]:
            imal+=1
        else:
            hu.append(imal)
            ima=Slist[i]
            imal=1
hu.append(imal)
Ngu=len(hu)
MAX=0
for i in range(Ngu):
    I=i
    kari=0
    k=0
    for j in range(Ngu):
        J=I+j
        if J == Ngu:
            break    
        if J%2==0:
            kari+=hu[J]
        else:
            if k<K:
                kari+=hu[J]
                k+=1
            else:
                break
    MAX=max(MAX,kari)
print(MAX)

Submission status: Time Limit Exceeded

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

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    if s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        if s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))

Submission status: Time Limit Exceeded

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

max_ = 0
for i in range(n):
    count = 0
    cur_k = 0
    is_zero = False
    for c in s[i:]:
        if len(s[i:]) < max_:
            break
        if c == '1':
            count += 1
            is_zero = False
        else:
            if is_zero:
                count += 1
            elif cur_k < k:
                cur_k += 1
                count += 1
                is_zero = True
            else:
                break
    if count > max_:
        max_ = count
print(max_)

Submission status: Time Limit Exceeded

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

N, K = map(int, input().split())
S = input()
c0, c1 = [], []
if S[0] == '1':
    c0.append(0)
i = 0
while i < N:
    p = S[i]
    c = 1
    i += 1
    while i < N and S[i] == p:
        i += 1
        c += 1
    if p == '0':
        c0.append(c)
    else:
        c1.append(c)
if S[N-1] == '0':
    c1.append(0)
ans = sum(c0[0:K]) + sum(c1[0:K])
for i in range(1, len(c1) - K + 1):
    tmp = sum(c0[i:i + K]) + sum(c1[i-1:i + K])
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

start = s[0]
arr = []
pre = start
cnt = 0
for x in s:
    if x == pre:
        cnt+=1
        continue
    else:
        pre = x
        arr.append(cnt)
        cnt = 1

arr.append(cnt)

if len(arr) == 1:
    print(arr[0])
    exit()
m = 0
if start == "1":
    for i in range((len(arr)//2)-k+1):
        m = max(sum(arr[2*i:2*i+2*k+1]), m)

else:
    m = sum(arr[:2*k])
    for i in range(((len(arr)+1)//2)-k):
        m = max(sum(arr[2*i+1:2*i+2*k+2]), m)
    
print(m)

Submission status: Time Limit Exceeded

Solution code:

def kakaka():
    a = list(map(int, input().split()))
    b = map(int, input().split())
    c = int(input())

def start_process():
    return
def main():
    all_num, inst_num = map(int, input().split())
    data = list(input())

    # all_num, inst_num = 5, 1
    # data = list('00010')

    max_num = 0
    for i in range(all_num):
        now_kiritsu = 0
        flg = 0
        for j in range(i, all_num):
            if data[j] == '0':
                if flg == 0:
                    now_kiritsu += 1
                    flg = 1
                else:
                    pass
                if now_kiritsu > inst_num:
                    if max_num < j - i:
                        max_num = j - i
                        # print(j, i, max_num)
                    break
            else:
                flg = 0
        else:
            if max_num < j - i + 1:
                max_num = j - i + 1
                # print(j, i, max_num)

        # print(i, j, now_kiritsu)

    print(max_num)






if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if a < b:
        a, b = b, a
    ans = a
    a -= 1
    ans += max(a, b)
    print(ans)
    return

#B
def B():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    ans = 0
    for i in range(n):
        dp[i] = max(dp[i - 1], h[i])
        if dp[i - 1] <= h[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    s = S()
    ans = 0
    for num, i in enumerate(s):
        if num % 2:
            if i == "0":
                ans += 1
        else:
            if i == "1":
                ans += 1
    ansb = 0
    for num, i in enumerate(s):
        if not num % 2:
            if i == "0":
                ansb += 1
        else:
            if i == "1":
                ansb += 1
    print(min(ans, ansb))
    return

#D
def D():
    n, k = LI()
    s = S()
    ans = 0
    for i in range(n):
        bk = k
        l = i
        while l < n and (bk > 0 or s[l] == "1"):
            if s[l] == "0":
                for x in range(l+1, n):
                    if s[x] == "0":
                        continue
                    l = x
                    bk -= 1
                    if l == n - 1:
                        l = n
                    break
            l += 1
        ans = max(ans, l - i)
        if l == n:
            break
        #print(ans, l , i)
    print(ans)
            
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if a < b:
        a, b = b, a
    ans = a
    a -= 1
    ans += max(a, b)
    print(ans)
    return

#B
def B():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    ans = 0
    for i in range(n):
        dp[i] = max(dp[i - 1], h[i])
        if dp[i - 1] <= h[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    s = S()
    ans = 0
    for num, i in enumerate(s):
        if num % 2:
            if i == "0":
                ans += 1
        else:
            if i == "1":
                ans += 1
    ansb = 0
    for num, i in enumerate(s):
        if not num % 2:
            if i == "0":
                ansb += 1
        else:
            if i == "1":
                ansb += 1
    print(min(ans, ansb))
    return

#D
def D():
    n, k = LI()
    s = S()
    ans = 0
    for i in range(n):
        bk = k
        l = i
        while l < n and (bk > 0 or s[l] == "1"):
            if s[l] == "0":
                for x in range(l+1, n):
                    if s[x] == "0":
                        continue
                    l = x
                    bk -= 1
                    if l == n - 1:
                        l = n
                    break
            l += 1        
        ans = max(ans, l - i)
        #print(ans, l , i)
    print(ans)
            
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

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

t = []
cur = s[0]
cnt = 0
for ss in s:
    if cur == ss:
        cnt += 1
    else:
        sgn = 1 if cur == '1' else -1
        # 逆立ちでないなら-1
        t.append(cnt * sgn)

        cur = ss
        cnt = 1
sgn = 1 if cur == '1' else -1
# 逆立ちでないなら-1
t.append(cnt * sgn)

M = len(t)
ans = 0
for i in range(M):
    cnt = 0
    b = 0
    for j in range(i, M):
        if t[j] < 0:
            cnt += 1
            if cnt > K:
                break
            b += -t[j]
        else:
            b += t[j]
    ans = max(ans, b)
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import numpy as np 

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

li = []
right=0
left =0
cnta = 0
if s[right]=="0":
    cnta=1
while(right<len(s)-1):
    if s[right]=="1" and s[right+1]=="0":
        cnta += 1
    if cnta > K:
        li.append(s[left:right+1])
        while(left<len(s)-1):
            if s[left]=="0" and s[left+1]=="1":
                left+=1
                cnta-=1
                li.append(s[left:right+1])
                break
            left += 1
    right += 1
li.append(s[left:])
mx = 0
for i in li:
    mx = max(mx, len(i))
print(mx)

Submission status: Memory Limit Exceeded

Solution code:
import numpy as np 

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

li = []
right=0
left =0
cnta = 0
if s[right]=="0":
    cnta=1
while(right<len(s)-1):
    if s[right]=="1" and s[right+1]=="0":
        cnta += 1
    if cnta > K:
        li.append(s[left:right+1])
        while(left<len(s)-1):
            if s[left]=="0" and s[left+1]=="1":
                left+=1
                cnta-=1
                li.append(s[left:right+1])
                break
            left += 1
    right += 1
li.append(s[left:])
mx = max(
    map(
        lambda x:len(x),
        li
    )
)
print(mx)

Submission status: Accepted

Solution code:

from itertools import accumulate
def resolve():
    N, K = map(int, input().split())
    S = input()

    # even:1
    # odd:0
    # 1-0-1-0-1 の配列にする. 両端は1にする
    L = []
    pre = "1"
    cnt = 0
    for i in range(N):
        if pre == S[i]:
            cnt += 1
        else:
            L.append(cnt)
            cnt = 1
        pre = S[i]
    L.append(cnt)
    # 最後が0で終わっていたら、仮の1を付け足す。(値が0なので影響ない)
    if pre == "0":
        L.append(0)

    # 1-0-1-0-1の配列を作成し、K＝2だとする。
    # 0を2個含めた個数は, 1＝3、0＝2の長さが作成できる
    length = 2 * K + 1

    # 0をすべて変換できる
    if len(L) <= length:
        return print(N)

    # 1-0-1-0-1の配列なので間に0を含んだ数え上げ
    # なので偶数とびに1を起点に数え上げ
    # 累積
    acc = [0] + list(accumulate(L))
    ans = 0
    for i in range(0, len(L), 2):
        left = i
        right = min(i + length, len(L))
        tmp = acc[right] - acc[left]

        ans = max(ans, tmp)

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

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

    # even:1
    # odd:0
    # 1-0-1-0-1 の配列にする. 両端は1にする
    L = []
    pre = "1"
    cnt = 0
    for i in range(N):
        if pre == S[i]:
            cnt += 1
        else:
            L.append(cnt)
            cnt = 1
        pre = S[i]
    L.append(cnt)
    # 最後が0で終わっていたら、仮の1を付け足す。(値が0なので影響ない)
    if pre == "0":
        L.append(0)

    # 1-0-1-0-1の配列を作成し、K＝2だとする。
    # 0を2個含めた個数は, 1＝3、0＝2の長さが作成できる
    length = 2 * K + 1

    # 0をすべて変換できる
    if len(L) <= length:
        return print(N)

    # 1-0-1-0-1の配列なので間に0を含んだ数え上げ
    # なので偶数とびに1を起点に数え上げ
    left = 0
    right = 0
    tmp = 0
    # しゃくとり
    ans = 0
    for i in range(0, len(L), 2):
        nextL = i
        nextR = min(i + length, len(L))

        while nextL > left:
            tmp -= L[left]
            left += 1
        while nextR > right:
            tmp += L[right]
            right += 1

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

from itertools import accumulate


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

    # even:1
    # odd:0
    # 1-0-1-0-1 の配列にする. 両端は1にする
    L = []
    pre = "1"
    cnt = 0
    for i in range(N):
        if pre == S[i]:
            cnt += 1
        else:
            L.append(cnt)
            cnt = 1
        pre = S[i]
    L.append(cnt)
    # 最後が0で終わっていたら、仮の1を付け足す。(値が0なので影響ない)
    if pre == "0":
        L.append(0)

    # 1-0-1-0-1の配列を作成し、K＝2だとする。
    # 0を2個含めた個数は, 1＝3、0＝2の長さが作成できる
    length = 2 * K + 1

    # 0をすべて変換できる
    if len(L) <= length:
        return print(N)

    acc = [0] + list(accumulate(L))
    ans = 0
    # 1-0-1-0-1の配列なので間に0を含んだ数え上げ
    # なので偶数とびに1を起点に数え上げ 
    for i in range(0, len(L) - length + 1, 2):
        ans = max(ans, acc[i + length] - acc[i])

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

from itertools import accumulate


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

    # even:1
    # odd:0
    # 1-0-1-0-1 の配列にする. 両端は1にする
    L = []
    pre = "1"
    cnt = 0
    for i in range(N):
        if pre == S[i]:
            cnt += 1
        else:
            L.append(cnt)
            cnt = 1
        pre = S[i]
    L.append(cnt)
    # 最後が0で終わっていたら、仮の1を付け足す。(値が0なので影響ない)
    if pre == "0":
        L.append(0)

    # 1-0-1-0-1の配列を作成し、K＝2だとする。
    # 0を2個含めた個数は, 1＝3、0＝2の長さが作成できる
    length = 2 * K + 1

    # 0をすべて変換できる
    if len(L) <= length:
        return print(N)

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

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
l=list()
s = s.replace("10","1,0")
s = s.replace("01","0,1")

l = [len(i) for i in s.split(",")]
r = 0
ans = 0

if s[0] == "1":
    r = min(k, len(l) - 1)
else:
    r = min(k-1, len(l) - 1)

t = l[r]

for j in range(1, k+1):
    #print(r,j,t,l[r-j],l[r+j])
    if r-j >= 0:
        #print("r-j >= 0:")
        t += l[r-j]
    if r+j < len(l):
        #print("r+j < len(l):")
        t += l[r+j]
ans = t
for i in range(r+2, len(l) ,2):
    for j in range(1, 3):
        if i-j-k >= 0:
            #print("l[i-j-k]", i-j-k, l[i-j-k])
            t -= l[i-j-k]
        if i+j+k-2 < len(l):
            #print("l[i+k+j]", i+j+k-2, l[i+j+k-2])
            t += l[i+j+k-2]
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
flag=False
cnt=[]
l=0
r=0
cnt.append([0,0])
for i in range(N):
    if flag:
        if S[i]=='0':
            r=i
            cnt.append([l,r])
            flag=False
    else:
        if S[i]=='1':
            l=i
            flag=True
if flag:
    cnt.append([l,N])
cnt.append([N,N])
ans=0
n=len(cnt)
for i in range(n):
    j=min(n-1,i+K)
    ans=max(cnt[j][1]-cnt[i][0],ans)
print(ans)

Submission status: Accepted

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

i = 0
x = 0

cumulative = [0]

while i < n:
    i0 = i
    x = s[i]
    while i < n and x == s[i]:
        i += 1
    cumulative.append(cumulative[-1] + i - i0)


x = s[0] == '1'
ans = 0
m = len(cumulative)
for i in range(1, m):
    j = i + 2 * k if x else i + 2 * k - 1
    ans = max(ans, cumulative[min(j, m-1)] - cumulative[i-1])
    if m <= j:
        break
    x = not x
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,k=map(int,input().split())
s=input()
w=[]
f=s[0]
ans=chk=0
d=deque([])
for i in s:
    if i!=f:
        if f=='0': chk*=-1
        w.append(chk)
        f=i
        chk=1
    else:
        chk+=1
if f=='0': chk*=-1
w.append(chk)

chk=0
for i in w:
    if i>0 or k>0:
        if i<0: k-=1
        chk+=abs(i)
        d.append(i)

    elif k>0:
        chk+=abs(i)
        k-=1
        d.append(i)
    else:
        x=d.popleft()
        chk-=abs(x)
        if x>0:
            x=d.popleft()
            chk-=abs(x)
        chk+=abs(i)
        d.append(i)

    ans=max(ans,chk)

print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n,K = i_map()
    s = list(input())

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

    for i,k in itertools.groupby(s):
        l.append(len(list(k)))
    if s[-1] == "0":
        l.append(0)

    l = list(itertools.accumulate(l))

    ans = 0
    if len(l) < 2*K:
        ans = max(l)
        print(ans)
        exit()

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






if __name__=="__main__":
    main()