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:
n, k = list(map(int, input().split(' ')))
s = input()
ll = []
prev = ''
temp = 0
for c in s:
  t = int(c)
  if t != prev:
    prev = t
    if temp:
      ll.append(temp)
    temp = 0
  temp += 1 if t else -1
if temp:
  ll.append(temp)
# print(ll)
ans = 0
for i in range(len(ll)):
  temp = 0
  if i == 0 and ll[i] < 0:
    for j in range(min(2*k, len(ll))):
      temp += abs(ll[j])
  elif ll[i] > 0:
    for j in range(i, min(i + 2*k + 1, len(ll))):
      temp += abs(ll[j])
  ans = max(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10001)

n, k = list(map(int, input().split(' ')))
s = input()
ll = []
prev = ''
temp = 0
for c in s:
  t = int(c)
  if t != prev:
    prev = t
    if temp:
      ll.append(temp)
    temp = 0
  temp += 1 if t else -1
if temp:
  ll.append(temp)
#print(ll)
memo = {}
def f(index, l, k):
  key = str(index) + str(l) + str(k)
  if key in memo:
    return memo[key]
  if k == 0 or index >= len(l):
    maxl = max(l)
    return max(maxl, -maxl)
  if l[index] > 0:
    return f(index+1, l, k)
  mmm = -l[index] + (l[index-1] if index >= 1 else 0) + (l[index+1] if index+1 < len(l) else 0)
  if len(l) == 1:
    new_l = None
  elif index == 0:
    new_l = [mmm] + l[2:]
  elif index == 1:
    new_l = [mmm] + l[3:]
  elif index == len(l)-1:
    new_l = l[:-2] + [mmm]
  elif index == len(l)-2:
    new_l = l[:-3] + [mmm]
  else:
    new_l = l[:index-2] + [mmm] + l[index+2:]
  t1 = f(index + 1, l[:], k)
  t2 = f(index - 1, new_l, k-1) if new_l else 0
  memo[key] = max(t1, t2)  
  return memo[key]

print(f(0, ll, k))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10001)

n, k = list(map(int, input().split(' ')))
s = input()
ll = []
prev = ''
temp = 0
for c in s:
  t = int(c)
  if t != prev:
    prev = t
    if temp:
      ll.append(temp)
    temp = 0
  temp += 1 if t else -1
if temp:
  ll.append(temp)
#print(ll)

def f(index, l, k):
  if k == 0 or index >= len(l):
    maxl = max(l)
    return max(maxl, -maxl)
  if l[index] > 0:
    return f(index+1, l, k)
  mmm = -l[index] + (l[index-1] if index >= 1 else 0) + (l[index+1] if index+1 < len(l) else 0)
  if len(l) == 1:
    new_l = None
  elif index == 0:
    new_l = [mmm] + l[2:]
  elif index == 1:
    new_l = [mmm] + l[3:]
  elif index == len(l)-1:
    new_l = l[:-2] + [mmm]
  elif index == len(l)-2:
    new_l = l[:-3] + [mmm]
  else:
    new_l = l[:index-2] + [mmm] + l[index+2:]
  t1 = f(index + 1, l[:], k)
  t2 = f(index - 1, new_l, k-1) if new_l else 0
  return max(t1, t2)  

print(f(0, ll, k))

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
s = input() + 'E'
top = int(s[0])
now = s[0]
idx = 0
ranges = []
for i, v in enumerate(s):
	if now != v:
		ranges.append(i - idx)
		idx = i
		now = v
zero = (k * 2) * [0]
ranges = zero + ranges + zero
targetIdx = 1 if top % 2 == 0 else 0 
ret = 0
for i, v in enumerate(ranges):
	if i % 2 == targetIdx:
		ret = max(sum(ranges[i:i+(k*2)+1]), ret)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        subs = s
        continue
    subs += s
ss.append(subs)
ssc = [len(s) for s in ss]
#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = sum(ssc[l:r])
    max_c = max(max_c, c)

print(max_c)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        subs = s
        continue
    subs += s
ss.append(subs)
#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = sum([len(s) for s in ss[l:r]])
    max_c = max(max_c, c)

print(max_c)

Submission status: Time Limit Exceeded

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

ss = []
pre = S[0]
num = 0
if S[0]=='0':ss.append(0)
  
for i in range(1, N):
    if S[i]!=pre:
        ss.append(len(S[num:i]))
        num = i
        pre = S[i]
ss.append(len(S[num: N]))

ans = []

for i in range(0,len(ss), 2):
    ans.append(sum(ss[i:i+2*K+1]))
    if i+2*K+1> len(ss):break

print(max(ans))

Submission status: Time Limit Exceeded

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

ss = []
pre = S[0]
num = 0
if S[0]=='0':ss.append(0)
  
for i in range(1, N):
    if S[i]!=pre:
        ss.append(len(S[num:i]))
        num = i
        pre = S[i]
ss.append(len(S[num: N]))

ans = 0

for i in range(0,len(ss), 2):
    ans = max(ans, sum(ss[i:i+2*K+1]))
    if i+2*K+1> len(ss):break

print(ans)

Submission status: Time Limit Exceeded

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

s = []
pre = S[0]
num = 0
for i in range(1, N):
    if S[i]!=pre:
        s.append(S[num:i])
        num = i
        pre = S[i]
s.append(S[num: N])

ss = []   

cnt = 0
if s[0][0]=='0':ss.append(0)
for si in s:
    ss.append(len(si))
ans = 0

for i in range(0,len(ss), 2):
    ans = max(ans, sum(ss[i:i+2*K+1]))

print(ans)

Submission status: Time Limit Exceeded

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

#連続する0or1の数をリスト化
L=[]
c=1
for i in range(1,N):
    if S[i]==S[i-1]:
        c+=1
        continue
    if c>0:
        L.append(c)
    c=1
if c>0:
    L.append(c)

#1で始まる2K+1個の塊を連続させることができる
#最大値を求める
ans=0
start=0
if S[0]=='0':
    #0から始まっている場合はそこから2K個をつなげる
    ans=sum(L[0:2*K])
    start=1
for i in range(start,len(L),2):
    ans=max(ans,sum(L[i:i+2*K+1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    n,k = inpm()
    s = list(input())
    cnt = []
    be = ''
    c = 0
    for i in range(n):
        if i == 0:
            be = s[i]
            c = 1                        
        elif s[i] != be:
            if be == '0':
                cnt.append((c,0))
            else:
                cnt.append((c,1))
            be = s[i]
            c = 1
        else:
            c += 1
    cnt.append((c,int(be)))
    ans = []
    length = len(cnt)
    if length//2 + (1-cnt[0][1]) <= k:
        print(n)
        return
    for i in range(length):
        s = 0
        for j in range(min(2*k+cnt[i][1], length-i)):
            s += cnt[i+j][0]
        ans.append(s)
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N,K=map(int,input().split())
S=input()

#N=14
#K=2
#S="11101010110011"

LIST=[[[0] for j in range (2)]for i in range(N)]

t=S[0]
c=0
k=0
for i in range(N):
    if(t!=S[i]):
        LIST[k][0]=c
        LIST[k][1]=t
        t=S[i]
        k+=1
        c=0
    c+=1

LIST[k][0]=c
LIST[k][1]=t
LIST=LIST[0:k+1]
MAX=0

def calc(i,s,K,f):
    global MAX
    MAX=max(MAX,s)
    if(i==len(LIST)):
        return

    if(LIST[i][1]=="1"):
        s+=LIST[i][0]
        MAX=max(MAX,s)
        i+=1
        if(i==len(LIST)):
            return
    if(K==0):
        return
    if(K>=1):
        calc(i+1,s+LIST[i][0],K-1,1)
    if(f==0):
        calc(i+1,0,K,0)

calc(0,0,K,0)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N,K=map(int,input().split())
S=input()

#N=14
#K=2
#S="11101010110011"

LIST=[[[0] for j in range (2)]for i in range(N)]

t=S[0]
c=0
k=0
for i in range(N):
    if(t!=S[i]):
        LIST[k][0]=c
        LIST[k][1]=t
        t=S[i]
        k+=1
        c=0
    c+=1

LIST[k][0]=c
LIST[k][1]=t
LIST=LIST[0:k+1]
MAX=0

def calc(i,s,K):
    global MAX
    MAX=max(MAX,s)
    if(i==len(LIST)):
        return

    if(LIST[i][1]=="1"):
        s+=LIST[i][0]
        MAX=max(MAX,s)
        i+=1
        if(i==len(LIST)):
            return
    
    if(K>=1):
        calc(i+1,s+LIST[i][0],K-1)
    calc(i+1,0,K)

calc(0,0,K)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
n,K = map(int, input().split(' '))
s = input()
ls0 = [0]
ls1 = [0]
if s[0] == "0":
    ls1[0] = -1
for i in range(n):
    if s[i] == "0":
        ls0[-1] += 1
        if ls1[-1] != 0:
            ls1.append(0)
    if s[i] == "1":
        ls1[-1] += 1
        if ls0[-1] != 0:
            ls0.append(0)
if s[0] == "0":
    ls1[0] = 0
if ls0[-1] == 0:
    del ls0[-1]
ansmax = 0
if K>=len(ls0):
    ansmax = len(s)
else:
    for i in range(len(ls0)-K+1):
        ansmax = max(ansmax, sum(ls0[i:i+K])+sum(ls1[i:i+K+1]))
print(ansmax)

Submission status: Time Limit Exceeded

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

memo = []

for i, s in enumerate(S):
    if i == 0:
        now = s
        cnt = 1
        continue

    if s == now:
        cnt += 1
    else:
        if now == "0":
            memo.append(-cnt)
        else:
            memo.append(cnt)
        now = s
        cnt = 1
else:
    if now == "0":
        memo.append(-cnt)
    else:
        memo.append(cnt)

if memo[0] < 0:
    memo = [0] + memo
if memo[-1] < 0:
    memo += [0]

stand = memo[0::2]
handstand = memo[1::2]

if len(handstand) <= k:
    ans = sum(stand) - sum(handstand)
else:
    ans = 0
    for i in range(len(handstand)-k+1):
        tmp = sum(stand[i: i + k + 1]) - sum(handstand[i: i + k])
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 1
before_s = S[0]
for s in S[1:]:
    count += 1
    if before_s != s:
        S_list.append(count-1)
        count = 1
    before_s = s

if S[-2] == "0":
    S_list.append(0)

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        ans = max(ans, sum(S_list[left:right+1]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 0
for idx, s in enumerate(S[:-1]):
    count += 1
    if s != S[idx+1]:
        S_list.append(count)
        count = 0

if S[-2] == "0":
    S_list.append(0)

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        ans = max(ans, sum(S_list[left:right+1]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split( ))
s = input()
c0 = 0
c1 = 0
l0 = []
 
l1 = []
if s[0]=="0":
    l1 = [0]
for i in range(n):
    if s[i]=="0":
        c0+=1
        if c1!=0:
            l1.append(c1)
            c1 = 0
    else:
        c1+=1
        if c0!=0:
            l0.append(c0)
            c0 = 0
if c0:
    l0.append(c0)
if c1:
    l1.append(c1)
 
l1.append(0)

ans = 0
if k >= len(l0):
    print(n)
else:
    nl1 = len(l1)
    for i in range(nl1-k):
        ans = max(ans,(sum(l0[i:i+k])+sum(l1[i:i+k+1])))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = list(input())
 
l0 = []
l1 = []
pred = s[0]
if s[0] == "0":
    l0.append(1)
    l1.append(0)
else:
    l1.append(1)
 
for i in range(1,n):
    if pred == s[i]:
        if s[i] == "0":
            l0[-1] += 1
        else:
            l1[-1] += 1
    else:
        if s[i] == "0":
            l0.append(1)
        else:
            l1.append(1)
    pred = s[i]
if s[-1] == "0":    
    l1.append(0)

ans = 0
if k >= len(l0):
    print(n)
else:
    nl1 = len(l1)
    for i in range(nl1-k):
        ans = max(ans,(sum(l0[i:i+k])+sum(l1[i:i+k+1])))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int,input().split())
s = list(input())
 
l0 = []
l1 = []
pred = s[0]
if s[0] == "0":
    l0.append(1)
    l1.append(0)
else:
    l1.append(1)
 
for i in range(1,n):
    if pred == s[i]:
        if s[i] == "0":
            l0[-1] += 1
        else:
            l1[-1] += 1
    else:
        if s[i] == "0":
            l0.append(1)
        else:
            l1.append(1)
    pred = s[i]
if s[-1] == "0":    
    l1.append(0)

ans = 0
if k >= len(l0):
    print(n)
else:
    nl1 = len(l1)
    for i in range(nl1-k):
        ans = max(ans,(sum(l0[i:i+k])+sum(l1[i:i+k+1])))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []
ans = 0

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

# kが十分大きいなら
if len(c) <= 2*k+1:
    print(sum(c))
    sys.exit()
# TLEしたから尺取りにしたい
for i in range(0, len(c)-2*k, 2):
    ans = max(ans, sum(c[i:i+2*k+1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []
ans = 0

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

# kが十分大きいなら
if len(c) <= 2*k+1:
    print(sum(c))
    sys.exit()

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

print(ans)

Submission status: Time Limit Exceeded

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

#for i in range(n):
l = 0
while True:
    if l == n - 2:
        break
    m = l
    r = l + 1
    cnt = 0

    if s[l] == '0':
        cnt += 1

    while True:
        #print(l, r)
        if r > n - 1:
            break

        if s[r] == '0':
            if s[r-1] == '1':
                cnt += 1
                if cnt > k:
                    break
        else:
            if s[r-1] == '0' and cnt == 1:
                m = r
        r += 1
    ans = max(ans, r - l)
    #print('[C] ans:', ans)
    l = m


print(ans)

'''
5 1
00010

14 2
11101010110011
'''

Submission status: Time Limit Exceeded

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

for i in range(n):
    l = i
    r = l + 1
    cnt = 0
    #print(l, r)
    if s[l] == '0':
        cnt += 1

    while True:
        #print(l, r)
        if r > n - 1:
            break
        # if r == n - 1:
        #     if s[r] == '1':
        #         ans = max(ans, r - l + 1)
        #         print('[A] ans:', ans)
        #     break

        if s[r] == '0':
            if s[r-1] == '1':
                cnt += 1
                if cnt > k:
                    # ans = max(ans, r - l + 1)
                    #ans = max(ans, r - l)
                    #print('[B] ans:', ans)
                    break
        # else:
        #     if s[r-1] == '0':
        #         if cnt == k:
        #             ans = max(ans, r - l + 1)
        #             print('ans:', ans)
        #             break
        r += 1
    ans = max(ans, r - l)
    #print('[C] ans:', ans)

print(ans)

'''
5 1
00010

14 2
11101010110011
'''

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
N, K = map(int, input().split())
S = groupby(list(input()))
state = []
number = []
for i, j in S:
    state.append(i)
    number.append(len(list(j)))

answer = 0

if len(state) == 1:
    print(number[0])
    exit()

if state[0] == '0':
    answer = sum(number[0:2 * K])

start = state.index('1')
for i in range(start, len(number), 2):
    answer = max(answer, sum(number[i:2 * K + i + 1]))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k = map(int,input().split())
input = sys.stdin.readline
list1 = list(input())
list2 = []
count = 1
for i in range(1,n):
	if list1[i] != list1[i-1]:
		list2.append(count)
		count = 0
	count += 1
list2.append(count) #最後の処理
length = 0
list3 = []
#以下のループはn=1のときのみうまく動作しないので、例外処理
if n ==1:
	print(1)
	exit()

if list1[0] == "0": #長さはk*2
	length1 = k*2 #初期値
	length2 = k*2 + 1
	for i in range(len(list2)):
		if length != length1:
			length = length1
		else:
			length = length2
		if i+length >= n:
			break
		list3.append(sum(list2[i:i+length]))

else: #長さはk*2+1
	length1 = k*2 +1 #初期値
	length2 = k*2
	for i in range(len(list2)):
		if length != length1:
			length = length1
		else:
			length = length2
		if i+length >= n:
			break
		list3.append(sum(list2[i:i+length]))
if len(list3) == 0:
	print(n)
	exit()
print(max(list3))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = list(input()) + ['2']

blocks = []
cur = 1
seq = 0
for s in S:
    if int(s) == cur:
        seq += 1
    else:
        blocks.append(seq)
        cur = 1 - cur
        seq = 1
answer = 0
for i in range(0, len(blocks), 2):
    answer = max(answer, sum(blocks[i:i+2*K+1]))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=list(input())
a=[]
f=1
s.append(2)
for i in range(n):
    if s[i]==s[i+1]:
        f+=1
    else:
        a.append(f)
        f=1
g=len(a)
if s[0]=='1':
    ans=0
    for i in range(g):
        if 2*i<g:
            ans=max(ans,sum(a[2*i:2*i+2*k+1]))
        else:
            break
    print(ans)
else:
    ans=sum(a[0:2*k])
    for i in range(g):
        if 2*i+1<g:
            ans=max(ans,sum(a[2*i+1:2*i+2*k+2]))
        else:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
S = input()
lst = []
if (S[0] == '0'): lst.append(0)
cnt = 1
for i in range(N-1):
    if (S[i] == S[i+1]):
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1 
lst.append(cnt)
if (S[-1] == '0'): lst.append(0)
tmp = []
ans = 0 if (len(lst) != 1) else lst[0] 
for i in range(0, len(lst)-1, 2):
    s = sum(lst[i:(i+1+2*K)])
    if (ans < s):
        ans = s
print(ans)

Submission status: Time Limit Exceeded

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

L = S.replace('01', '0,1')
L = L.replace('10', '1,0')
L = L.split(',')
L = [len(l) for l in L]

if S[0] == '0':
    L = [0] + L

R = [sum(L[2*i:2*(i+K)+1]) for i in range(max(1, len(L) // 2 + 1 - K))]

print(max(R))

Submission status: Time Limit Exceeded

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

L = []
t = S[0]
l = 1

for s in S[1:]:
    if t == s:
        l += 1
    else:
        L.append(l)
        t = s
        l = 1

L.append(l)

if S[0] == '0':
    L = [0] + L

R = []
for i in range(max(1, len(L) // 2 + 1 - K)):
    R.append(sum(L[2*i:2*(i+K)+1]))

print(max(R))

Submission status: Time Limit Exceeded

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

L = S.replace('01', '0,1')
L = L.replace('10', '1,0')
L = L.split(',')
L = [len(l) for l in L]

if S[0] == '0':
    L = [0] + L

R = []
for i in range(max(1, len(L) // 2 + 1 - K)):
    R.append(sum(L[2*i:2*(i+K)+1]))

print(max(R))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = list(map(int,input()))
num = 1
T = []
T_append = T.append
if S[0] == 0:
    T.append(0)
tmp = S[0]
for i,s in enumerate(S):
    if i == 0:
        continue
    if tmp != s:
        T_append(num)
        num = 0
    tmp = s
    if i == N-1:
        T_append(num+1)
        continue
    num += 1
if S[N-1] == 0:
    T.append(0)
#index 0,2,4...に1の連続数、1,3,5...に0の連続数
if K >= len(T)//2:
    print(N)
else:
    ans = 0
    for i in range(len(T)//2 -K+1):
        ans = max(ans,sum(T[2*i:2*i+2*K+1]))
    print(ans)

Submission status: Time Limit Exceeded

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

#index 0,2,4...に1の連続数、1,3,5...に0の連続数
if K >= len(T)//2:
    print(N)
else:
    ans = 0
    for i in range(len(T)//2 -K+1):
        ans = max(ans,sum(T[2*i:2*i+2*K+1]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = list(map(int,input()))
s_list = list()
num = s[0]
temp_streak = 0
temp_max = 0
[s_list.append(0) for i in range(1+s[0])]

for i in s:
    if i == num:
        temp_streak += 1
    else:
        s_list.append(temp_streak)
        temp_streak = 1
        num = i
s_list.append(temp_streak)
[s_list.append(0) for i in range(1+s[-1])]
# odd = len(s_list)%2
num_i = len(s_list) // 2 
#print(s_list)

for i in range(max(num_i+1-k,1)):
    temp_max = max(temp_max,sum(s_list[i*2:i*2+k*2+1]))
print(temp_max)




#print(s_list)

Submission status: Time Limit Exceeded

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

if S.count('1') == N or S.count('0') == N:
  print(N)
  exit()

S += '2'
s = S[0]
L0 = []
if s == '0':
  L1 = [0]
else:
  L1 = []
c = 1
for i in range(1,N+1):
  if S[i] != s:
    if s == '0':
      L0.append(c)
    else:
      L1.append(c)
    s = S[i]
    c = 1
  else:
    c += 1
L1 += [0]
#print(L0)
#print(L1)

if len(L0) <= K:
  print(N)
  exit()

ans = 0
for i in range(len(L0)-K+1):
    ans = max(ans,sum(L0[i:i+K])+sum(L1[i:i+K+1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f_d():
    n, k = map(int, input().split())
    *s, = map(int, list(input()))
    l, t, c = [], 1, 0
    for i in range(n):
        if s[i]==t:
            c += 1
        else:
            l.append(c)
            c, t = 1, t^1
    if c!=0:
        l.append(c)
    if len(l)%2==0:
        l.append(0)

    r, a = 2*k+1, 0
    for i in range(0, len(l), 2):
        a = max(a, sum(l[i:min(i+r, len(l))]))
    print(a)

if __name__ == "__main__":
    f_d()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split(' '))
S = input()
S2=[]
key=S[0]
tmpcnt=1
if key=='0':
    S2.append(0)
for i in range(1,len(S)):
    if key!=S[i]:
        if key == '0':
            S2.append(-1*tmpcnt)
        else:
            S2.append(tmpcnt)
        key=S[i]
        tmpcnt=1
    else:
        tmpcnt+=1
if key == '0':
    S2.append(-1*tmpcnt)
    S2.append(0)
    S2.append(0)
else:
    S2.append(tmpcnt)
    S2.append(0)
    S2.append(0)
#print(S2)
max=0
for i in range(0,len(S2),2):
    tmp=S2[i]
    maxj=len(S2)-1
    for j in range(1,K*2+1):
        tmp+=abs(S2[min(i+j,maxj)])
        #print(S2[i],S2[min(i+j,maxj)])
    if tmp >= max:
        max=tmp
    #print(tmp)
print(max)

Submission status: Time Limit Exceeded

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

s.append(9)
ran = []
a = 0
i = 1
#ランレングス圧縮
while i < len(s):
    if s[a] == s[i]:
        i +=1
    else:
        ran.append(i-a)
        a = i
        i += 1
ran.append(0)
ran.append(0)
ran.append(0)
b = s[0]
result = []
i = 0
counter = 0
if len(ran)-3 <= k*2:
    print(n)
else:
    while i+2*k <= len(ran)-3:
        if s[counter] == 1:
            result.append(sum(ran[i:2*k+i+1]))
        else:
            result.append(sum(ran[i:2*k+i]))
        counter += ran[i]
        i += 1
    print(max(result))

Submission status: Time Limit Exceeded

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

a = []
j = 0
temp = 1
prev = s[0]
for i in s[1:]:
    if i == prev:
        prev = i
        temp += 1
    else:
        a.append(temp)
        prev = i        
        temp = 1
a.append(temp)

b = []
if s[0] == "1":
    b.append(sum(a[:2*k+1]))
    for i in range(len(a) - 2*k + 1):
        if i % 2 == 0:
            try:
                b.append(sum(a[i:i+(2*k) + 1]))
            except:
                continue
    print(max(b))

else:
    t = a[1:]
    b.append(sum(t[:2*k+1]))
    for i in range(len(t) - 2*k + 1):
        if i % 2 == 0:
            try:
                b.append(sum(t[i:i+(2*k) + 1]))
            except:
                continue
    b.append(sum(a[:2*k]))
    print(max(b))

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
print(max(sum(a[i:i+k+1]+b[i:i+k])for i in range(l+1-k)))

Submission status: Time Limit Exceeded

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

l = []
now = 1 # 今見ている数(1から見る配列を作りたいので1で初期化)
cnt = 0

# lには(1の個数),(0の個数),(1の個数),(0の個数),...(1の個数)という感じのリストを入れたい(両端が0から始まるとしても1が0こあるとしてカウントしたい)
for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now # 0と1を切り替える(now ^= 1でも良い)
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: # (1の個数),(0の個数),(1の個数),(0の個数),...(0の個数)となってしまっていたら最後に0を入れておく
    l.append(0)
# print(l)

ans = 0
width = 2 * K + 1

for i in range(0, len(l), 2):
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): # leftからright-1まで
        tmp += l[j]
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
As = []
Cs = []
count = 0
now = S[0]

for i in range(N):
    if now == S[i]:
        count += 1
    else:
        As.append(now)
        Cs.append(count)
        now = S[i]
        count = 1
As.append(now)
Cs.append(count)
ans = 0
for i in range(len(As)):
    if As[i] == "1":
        k = 2*K if (len(As) - i) // 2 - K >= 0 else len(As) - i
        if ans < sum(Cs[i:i+k+1]):
            ans = sum(Cs[i:i+k+1])
    else:
        k = 2*K if (len(As) - i) // 2 - K >= 0 else len(As) - i
        if ans < sum(Cs[i:i+k]):
            ans = sum(Cs[i:i+k])
print(ans)

Submission status: Time Limit Exceeded

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

streaks = []
c = s[0]
i = 1
count = 1
while True:
    if i == n:
        streaks.append(count)
        count = 1
        break
    if s[i] == c:
        i += 1
        count += 1
    else:
        c = s[i]
        i += 1
        streaks.append(count)
        count = 1

start = s[0]
res = []
for i in range(len(streaks)):
    x = 0
    stop = min(len(streaks), i + 2 * k + start)
    for j in range(i, stop):
        x += streaks[j]
    res.append(x)
    start = 1 - start
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

sys.setrecursionlimit(len(s) + 100)


def count_streak(s, i, c):
    count = 0
    for j in range(i, len(s)):
        if s[j] == c:
            count += 1
        else:
            break
    return count


def dfs(s, i, k, count):
    if i == len(s):
        return count
    elif s[i] == 1:
        c = count_streak(s, i, 1)
        count += c
        return dfs(s, i + c, k, count)
    else:
        if k > 0:
            c = count_streak(s, i, 0)
            count += c
            return dfs(s, i + c, k - 1, count)
        else:
            return count


nums = []
for i in range(n):
    if i > 0 and s[i - 1] == 1:
        continue
    count = 0
    nums.append(dfs(s, i, k, count))
print(max(nums))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

sys.setrecursionlimit(len(s) + 100)


def count_zero(s, i):
    count = 0
    for j in range(i, len(s)):
        if s[j] == 0:
            count += 1
        else:
            break
    return count


def dfs(s, i, k, count):
    if i == len(s):
        return count
    elif s[i] == 1:
        count += 1
        return dfs(s, i + 1, k, count)
    else:
        if k > 0:
            c = count_zero(s, i)
            count += c
            return dfs(s, i + c, k - 1, count)
        else:
            return count


nums = []
for i in range(n):
    count = 0
    nums.append(dfs(s, i, k, count))
print(max(nums))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = input()
tmp = s[0]
cnt = 1
ans = 0
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)

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

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
s = list(map(int, list(input())))
pres = []
i = 0
while i < n:
    ka = 0
    while s[i] == s[i+ka]:
        ka += 1
        if ka+i >= n:
            break
    pres.append([s[i],ka])
    i += ka
ia = 0
result = []
while ia < len(pres):
    h = 0
    if pres[ia][0] == 0:
        if ia + 2*k <= len(pres):
            for p in range(2*k):
                h += pres[p+ia][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[p+ia][1]
            result.append(h)
            break
    else:
        if ia + 2*k+1 <= len(pres):
            for p in range(2*k+1):
                h += pres[ia+p][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[ia+p][1]
            result.append(h)
            break
    ia += 1
print(max(result))