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: Wrong Answer

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

A = [0]
B = [0]
for s in S:
  if s == '1':
    A[-1] += 1
  elif A[-1] != 0:
    A.append(0)
  if s == '0':
    B[-1] += 1
  elif B[-1] != 0:
    B.append(0)

ans = 0

for i in range(min(len(A),len(B))):
  a = 0
  if S[0] == '1':
     a = sum(A[i:min(i + K + 1,len(A))]) + sum(B[i:min(i + K,len(B))])
  else:
     a = sum(A[i:min(i + K + 1,len(A))]) + sum(B[i:min(i + K,len(B))])
  ans = max(ans,a)
print(ans)

Submission status: Wrong Answer

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


def main():
    n,k = map(int,input().split())
    s = list(input())
    tank = []
    judge = True
    if s[0] == '0':
        judge = False
    cnt = 0
    for i in range(n):
        if judge:
            if s[i] == '0':
                tank.append(cnt)
                judge = False
                cnt = 0
            cnt += 1
        else:
            if s[i] == '1':
                tank.append(cnt)
                judge = True
                cnt = 0
            cnt += 1
        if i == n-1:
            tank.append(cnt)
    #print(tank)
    p = len(tank)
    ind = 0
    if s[0] == '0' and (p+1)//2 <= k:
        print(n)
        exit()
    if p//2 <= k and s[0] == '1':
        print(n)
        exit()
    ans = 0
    res = 0
    if s[0] == '0':
        for j in range(2*k):
            res += tank[j]
        ans = res
        for j in range(2*k,p):
            if j%2 == 0:
                res= res - tank[j-2*k] -tank[j-2*k+1]
            res += tank[j]
            ans = max(ans,res)

    else:
        for j in range(2*k+1):
            res += tank[j]
        ans = res
        for j in range(2*k+1,p):
            if j % 2 == 1:
                res = res- tank[j-2*k-1]-tank[j-2*k]
            res += tank[j]
            ans = max(ans,res)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
listS = list(input())
zeroCL=[]
index=0
flag=1
count=0
startI=0
while index < len(listS):
    if listS[index]=="0":
        if flag:
            flag=0
            count=1
            startI = index
        else:
            count+=1
    else:
        if flag:
            pass
        else:
            zeroCL.append([count, startI,index-1])
            flag=1
    index += 1
if flag == 0:
    zeroCL.append([count, startI, index-1])
zeroCL.sort()
zeroCL.reverse()
if len(zeroCL)==0:
    print(len(listS))
else:
    index2=0
    while index2 < min(k, len(zeroCL)):
        index3=zeroCL[index2][1]
        while index3 < zeroCL[index2][2]+1:
            listS[index3]="1"
            index3+=1
        index2+=1
    index4=0
    max=0
    counter=0
    flag=1
    while index4 < len(listS):
        if listS[index4]=="1":
            if flag:
                counter=1
                flag=0
            else:
                counter+=1
        else:
            if flag:
                pass
            else:
                if max < counter:
                    max=counter
                counter=0
                flag=1
        index4+=1
    if flag==0:
        if max < counter:
            max = counter
    print(max)

Submission status: Wrong Answer

Solution code:
import sys
import random
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n, k = map(int,input().split())
s = input().rstrip()
ans = []
if s[0] == "0":
    ans.append(0)
    mae = "0"
else:
    mae = "1"
b = 0
for i in range(n):
    if s[i] == mae:
        b += 1
    else:
        ans.append(b)
        if mae == "0":
            mae = "1"
        else:
            mae = "0"
        b = 1
else:
    if b:
        ans.append(b)
rui = [0]*(len(ans)+1)
for i in range(len(ans)):
    rui[i+1] = ans[i] + rui[i]
MAX = 0
if len(ans[1::2]) <= k:
    print(n)
    exit()
for i in range(len(ans)+1):
    try:
        if i %2 == 0:
            MAX = max(rui[i+2*k+1]-rui[i],MAX)
        else:
            pass
    except:
        pass
print(MAX)

Submission status: Wrong Answer

Solution code:
from itertools import chain
N, K = map(int, input().split())
S = input()
LS = []
pre = S[0]
ctr = 0
for s in chain(S, '2'):
    if s == pre:
        ctr += 1
    else:
        LS.append(ctr)
        ctr = 1
        pre = s
if S[0] == '0':
    LS = [0] + LS
ans = 0
sumi = 0
for i in range(len(LS)):
    if i <= 2*K:
        sumi += LS[i]
    else:
        sumi += LS[i] - LS[i-2*K-1]
    if not i % 2:
        ans = max(ans, sumi)
print(ans)

Submission status: Wrong Answer

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

a = [0]
i = 0
p = "1"
for t in s:
  if t == p:
    a[i] += 1
  else:
    p = t
    i += 1
    a += [1]
# print(a)

if len(a) <= 2*k+1:
  print(n)
  quit()

x = sum(a[:2*k+1])
m = x 
for i in range(2*k+1,len(a)):
  # print(i)
  x = x + a[i] - a[i-(2*k+1)]
  m = max(m,x)
print(m)

Submission status: Wrong Answer

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if a == b:
        print(2*a)
    else:
        print(2*max(a,b)-1)
    return

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

#C
def C():
    s = S()
    ans = 0
    n = len(s)
    t = ["1" if i%2 else "0" for i in range(n)]
    for i in range(n):
        if t[i] != s[i]:
            ans += 1
    ans2 = 0
    t = ["0" if i%2 else "1" for i in range(n)]
    for i in range(n):
        if t[i] != s[i]:
            ans2 += 1
    print(min(ans,ans2))
    return

#D
def D():
    n,k = LI()
    s = S()
    f = [0 for i in range(n)]
    c = s[0]
    su = 1
    for i in range(1,n):
        if s[i] != c:
            if c == "0":
                f[i] = 1
            c = s[i]
            su = 1
        else:
            su += 1
    if c == "0":
        f[n-1] = 1
    for i in range(n-1):
        f[i+1] += f[i]
    ans = 0
    for l in range(n):
        r = bisect.bisect_right(f,k)
        ans = max(ans, r-l)
    print(ans)
    return

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

Submission status: Wrong Answer

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

beg=[0]
end=[]

for i in range(N):
	if len(beg) != len(end):
		if S[i] == "0":
			end.append(i-1)
	else:
		if S[i] == "1":
			beg.append(i)

if len(beg) != len(end):
	end.append(N-1)

ans=[1 + end[i+K] - beg[i] for i in range(len(beg)-K)]
print(max(ans) if len(ans) > 0 else N)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
S = list(map(int,list(str(input()))))
ss = []

cnt = 0
flag1 = (S[0] == 1)
if S[0] == 0:
    ss.append(0)

for s in S:
    if flag1 and s == 0:
        ss.append(cnt)
        cnt = 1
        flag1 = False
    elif not flag1 and s==1:
        ss.append(cnt)
        cnt = 1
        flag1 = True
    else:
        cnt += 1

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

l = 0
r = 2*K
tmp = sum(ss[l:r+1])
ans = tmp
while True:
    l += 2
    r += 2
    if r >= len(ss):
        break
    tmp -= ss[l-2] + ss[l-1]
    tmp += ss[r-1] + ss[r]
    ans = max(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, S):
    s1 = list(map(lambda x: len(x), filter(lambda x: x != '', S.split('0'))))
    s0 = list(map(lambda x: len(x), filter(lambda x: x != '', S.split('1'))))
    # error_print(s1)
    # error_print(s0)
    ans = 0
    l1 = sum(s1[:K+1])
    l0 = sum(s0[:K])
    k = 0
    l1o = 1 if S[0] == '1' else 0
    l0o = 1 if S[0] == '0' else 0
    while True:
        ans = max(ans, l1 + l0)
        if k+K+l1o < len(s1) and k+K+l0o < len(s0):
            l1 -= s1[k]
            l1 += s1[k+K+l1o]
            l0 -= s0[k]
            l0 += s0[k+K+l0o]
        else:
            break
        k += 1

    return ans


def main():
    # N = read_int()
    N, K = read_int_n()
    S = read_str()
    rS = ''.join(['0' if c == '1' else '1' for c in S])
    print(max(slv(N, K, S), slv(N, K-1, rS)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
S = list(map(int,list(str(input()))))
ss = []

cnt = 0
flag1 = (S[0] == 1)
if S[0] == 0:
    ss.append(0)

for s in S:
    if flag1 and s == 0:
        ss.append(cnt)
        cnt = 1
        flag1 = False
    elif not flag1 and s==1:
        ss.append(cnt)
        cnt = 1
        flag1 = True
    else:
        cnt += 1

ss.append(cnt)

l = 0
r = 2*K
tmp = sum(ss[l:r+1])
ans = tmp
while True:
    l += 2
    r += 2
    if r >= len(ss):
        break
    tmp -= ss[l-2] + ss[l-1]
    tmp += ss[r-1] + ss[r]
    ans = max(ans,tmp)

print(ans)

Submission status: Wrong Answer

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

turn = []
start = 0
end = 0
flag = False
while start < N and end < N:
    if flag:
        if S[end] == "0":
            end += 1
        else:
            turn.append((end - start, start))
            start = end
            flag = False
    else:
        if S[start] == "0":
            end = start + 1
            flag = True
        else: start += 1
if flag:turn.append((end - start, start))
turn.sort(reverse = True)
if len(turn) > K:
    for i in range(K):
        num, start = turn[i]
        S[start:start+num] = ["1"] * num
else:
    for num, start in turn: S[start:start+num] = ["1"] * num

length = [0] * N
if S[0] == "1": length[0] = 1
for i in range(1, N):
    if S[i] == "1":length[i] = length[i-1] + 1
print(max(length))

Submission status: Time Limit Exceeded

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

if N == 1:
  if S == '1':
    print(1)
  elif K > 0:
    print(1)
  else:
    print(0)
  exit()

cnt = 1
l = []
for i in range(N-1):
  if S[i] == S[i+1]:
    cnt += 1
  else:
    l.append(cnt)
    cnt = 1
if cnt > 1:
  l.append(cnt)

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

Submission status: Time Limit Exceeded

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

s = s[0] + s + str((int(s[-1])+1)%2)
a = []
l = 1
for i in range(1, n+2):
    if s[i] == s[i-1]:
        continue
    a.append(i-l)
    l = i
m = int(s[0])
ans = 0
for i in range(len(a)):
    ans = max(ans, sum(a[i:i+2*k+(m+i)%2]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#--初期の並びを圧縮表示,逆立ち、正立を目印--#
import sys,math,collections,itertools
input = sys.stdin.readline

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

stand = []
s_or_r = []

s_bf = '.'
cnt = 0
for i in range(N):
    if s_bf != S[i] and i != 0:
        stand.append(cnt)
        s_or_r.append(s_bf)
        cnt = 1
        s_bf=S[i]
    else:
        cnt += 1
        s_bf =S[i]
stand.append(cnt)
s_or_r.append(s_bf)


#--正立kまで許容して足す。maxが答え
if s_or_r.count('0')<=K:
    print(len(S))
    exit()

ans = 0
for start in range(len(stand)):
    rev = 0
    tmp = 0
    i=0
    flag = 0
    while rev+(s_or_r[start+i] == '0')<=K:
        tmp += stand[start+i]
        if s_or_r[start+i] == '0':
            rev += 1
        if start + i == len(stand)-1:
            flag =1
            break
        i += 1
    ans = max(ans,tmp)
    if flag == 1:
        break
print(ans)

Submission status: Time Limit Exceeded

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

# 1の個数, 0の個数, 1の個数, ..., 1の個数
list10 = []
head = S[0]
cnt = 0

# 左端の1の数
if S[0] == "0":
    list10.append(0)

for i in range(N):
    if S[i] == head:
        cnt += 1
    else:
        list10.append(cnt)
        cnt = 1
        head = S[i]

    if i == N - 1:
        list10.append(cnt)

# 右端の1の数
if S[-1] == "0":
    list10.append(0)

# print(list10)

ans = 0
for j in range(0, len(list10), 2):
    h = j
    t = min(N - 1, j + 2 * K)
    # print(sum(list10[j:t + 1]), j)
    ans = max(ans, sum(list10[j:t + 1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
s = []
count = 0
last = 1
for i in input():
    if i=='1':
        if last==1:
            count+=1
        else:
            s.append(count)
            count=1
        last = 1
    else:
        if last==0:
            count+=1
        else:
            s.append(count)
            count=1
        last = 0
s.append(count)
if last=='0':
    s.append(0)

k = min(k,len(s)//2)
ans = 0
for j in range(len(s)//2-k+1):
    ans = max(ans,sum(s[j*2:(j+k)*2+1]))
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0
if S[0] == '0':
    s = [0] + s
if S[-1] == '0':
    s = s + [0]

if 2*K + 1 > len(s):
    print(sum(s))
    exit()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
s = input()
count = 0
flag = 1
que = deque([0]*(2*k+1))
ans = 0
for x in s:
    if x == '0':
        if flag == 1:
            que.append(count)
            que.popleft()
            ans = max(ans, sum(que)) 
            count = 0
        flag = 0
        count += 1
    else:
        if flag == 0:
            que.append(count)
            que.popleft()
            count = 0
        flag = 1
        count += 1

que.append(count)
que.popleft()
if s[-1] == '0':
    que.popleft()
ans = max(ans,sum(que))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
from math import ceil

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

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

res = 0
for i in range(0, len(block), 2):
    res = max(sum(block[i:i+2*k+1]), res)
    if i+2*k+1 > n:
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=input()
a=[]
b=s[0]
c=0
mc=0
for i in range(n):
  if s[i]==b:
    c+=1
  elif s[i]=="1":
    a.append(-1*c)
    c=1
    b="1"
    mc+=1
  else:
    a.append(c)
    c=1
    b="0"
if s[i]=="1":
  a.append(c)
else:
  a.append(-c)
  mc+=1

mc=min(k,mc)
st=0
smm=0


while st<len(a):
  mc2=mc
  sm=0
  i=0

  while mc2>=0 and st+i<len(a):
    if a[st+i]>0:
      sm+=a[st+i]
    else:
      if mc2>0:
        sm-=a[st+i]
        mc2-=1
      else:
        break
    i+=1
  if sm>smm:
    smm=sm
  st+=1

print(smm)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 0
cnt = 0
L = []
for i in range(N):
    if i == N-1:
        L.append(N-num)
    if i < num:
        continue
    s = S[i]
    if s == '0':
        cnt += 1
    for j in range(i,N):
        if S[j] != s:
            L.append(j-num)
            num = j
            break
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,K = I()
S = list(s())
num = 0
cnt = 0
L = []
for i in range(N):
    if i == N-1:
        L.append(N-num)
    if i < num:
        continue
    s = S[i]
    if s == '0':
        cnt += 1
    for j in range(i,N):
        if S[j] != s:
            L.append(j-num)
            num = j
            break
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

Submission status: Time Limit Exceeded

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = sum(on[i:i+k]) + sum(off[i:i+k+1])
    # print (sum(on[i:i+k]),sum(off[i:i+k+1]))
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      s = sum(on[i:i+k]) + sum(off[i:i+k])
      # print (sum(on[i:i+k]),sum(off[i:i+k]))
    else:
      s = sum(on[i:i+k]) + sum(off[i-1:i+k])
      # print (sum(on[i:i+k]),sum(off[i-1:i+k]))
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Time Limit Exceeded

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

N, K = MAP()
S = input()

flg = [S[0]] #各連続部分の数字
count = []   #連続部分の個数
cnt = 1
tmp = S[0]

for x in S[1:]:
	if x == tmp:
		cnt += 1
	else:
		tmp = x
		flg.append(tmp)
		count.append(cnt)
		cnt = 1
count.append(cnt)

ans = 0
for i in range(len(flg)):
	if flg[i] == "1":
		ans = max(ans, sum(count[i:i+2*K+1]))
	else:
		ans = max(ans, sum(count[i:i+2*K]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

def main():
	N, K = MAP()
	S = input()

	flg = [int(S[0])]
	count = []
	cnt = 1
	tmp = S[0]

	for x in S[1:]:
		if x == tmp:
			cnt += 1
		else:
			tmp = x
			flg.append(int(tmp))
			count.append(cnt)
			cnt = 1
	count.append(cnt)

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

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

def main():
	N, K = MAP()
	S = input()

	flg = [int(S[0])]
	count = []
	cnt = 1
	tmp = S[0]

	for x in S[1:]:
		if x == tmp:
			cnt += 1
		else:
			tmp = x
			flg.append(int(tmp))
			count.append(cnt)
			cnt = 1
	count.append(cnt)

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

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

def main():
	N, K = MAP()
	S = input()

	flg = [S[0]]
	count = []
	cnt = 1
	tmp = S[0]

	for x in S[1:]:
		if x == tmp:
			cnt += 1
		else:
			tmp = x
			flg.append(tmp)
			count.append(cnt)
			cnt = 1
	count.append(cnt)

	ans = 0
	for i in range(len(flg)):
		if flg[i] == "1":
			ans = max(ans, sum(count[i:i+2*K+1]))
		else:
			ans = max(ans, sum(count[i:i+2*K]))

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

N, K = MAP()
S = input()

flg = [S[0]]
count = []
cnt = 1
tmp = S[0]

for x in S[1:]:
	if x == tmp:
		cnt += 1
	else:
		tmp = x
		flg.append(tmp)
		count.append(cnt)
		cnt = 1
count.append(cnt)

ans = 0
for i in range(len(flg)):
	if flg[i] == "1":
		ans = max(ans, sum(count[i:i+2*K+1]))
	else:
		ans = max(ans, sum(count[i:i+2*K]))

print(ans)

Submission status: Time Limit Exceeded

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

nums = []
now = 1 # 今見ている値
cnt = 0 # 今見ている値の連続する個数
for i in range(n):
    if s[i] == str(now): # 今見ているもの同じ場合
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1
        cnt = 1
# if cnt != 0:
nums.append(cnt)
# print(nums) # 消し忘れ（でもTLEすることは分かった）
# 配列の大きさが奇数でないなら，0を追加
if len(nums) % 2 == 0:
    nums.append(0)

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

Submission status: Time Limit Exceeded

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

X=[]
x0=S[0]
if x0=="0":
    X.append(0)
cnt=1
for i in range(1,N):
    if x0==S[i]:
        cnt+=1
    else:
        X.append(cnt)
        cnt=1
        x0=S[i]
X.append(cnt)

L=len(X)
ans=0
idx=0
while idx<L:
    if idx+2*K>L:
        temp=sum(X[idx:])
    else:
        temp=sum(X[idx:idx+2*K+1])
    ans=max(ans,temp)
    idx+=2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = list(map(int, input().split()))
    S = list(input())
    T = []
    a, c = S[0], 0
    for s in S:
        if s == a:
            c += 1
        else:
            T.append([a, c])
            a = s
            c = 1
    T.append([a, c])
    ans = 0
    for i, t in enumerate(T):
        if t[0] == '0':
            r = i + 2 * k - 1
        else:
            r = i + 2 * k
        ans = max(ans, sum([a[1] for a in T[i:min(len(T) - 1, r) + 1]]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    #print(S[i])
    if f != S[i]:
        #a.append([l, i-1, int(f)])
        #a.append([i-l, int(f)])
        a.append(i-l)
        l = i
        f = S[i]
        
#print(a)

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

MAX = 0
for i in range(len(a)):
    if i % 2 == 0:
        #print(a[i:i+2*K+1])
        #print(sum(a[i:i+2*K+1]))
        MAX = max(MAX, sum(a[i:i+2*K+1]))
        if len(a) < i+1+2*K+1:
            break

print(MAX)

Submission status: Time Limit Exceeded

Solution code:

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

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    #print(S[i])
    if f != S[i]:
        #a.append([l, i-1, int(f)])
        #a.append([i-l, int(f)])
        a.append(i-l)
        l = i
        f = S[i]
        
#print(a)

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

MAX = 0
for i in range(len(a)):
    if i % 2 == 0:
        #print(a[i:i+2*K+1])
        #print(sum(a[i:i+2*K+1]))
        MAX = max(MAX, sum(a[i:i+2*K+1]))

print(MAX)