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:
def main():
    from itertools import groupby as gr
    n, k = map(int, input().split())
    s = input()
    p, q = [], []
    i = 0
    for f, g in gr(s):
        p.append(len(list(g)))
        if f == '0':
            q.append(i)
        i += 1

    if not q:
        print(n)
        exit()

    ans = 0
    for i in q:
        x, y = max(0, i - 1), min(n, i + 2 * k)
        ans = max(ans, sum(p[x:y]))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

s = '1' + s + '1'

cnt_1 = []
cnt_0 = []
stack_1 = 0
stack_0 = 0
for i in s:
    if i == '1':
        if stack_0 > 0:
            cnt_0.append(stack_0)
            stack_0 = 0
        stack_1 += 1
    else:
        if stack_1 > 0:
            cnt_1.append(stack_1)
            stack_1 = 0
        stack_0 += 1
if stack_1 > 0:
    cnt_1.append(stack_1)

if len(cnt_1) == 0 or len(cnt_0) == 0:
    print(n)
    exit()
cnt_1[0] -= 1
cnt_1[-1] -= 1
cum_1 = []
cum_0 = []
if k > len(cnt_0):
    k = len(cnt_0)
for i in range(len(cnt_1)-k):
    cum_1.append(sum(cnt_1[i:i+k+1]))
for i in range(len(cnt_0)-k+1):
    cum_0.append(sum(cnt_0[i:i+k]))

res = []
for v, w in zip(cum_1, cum_0):
    res.append(v+w)
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
s=input()
g=[]
l=0
for i in range(1,N):
    if s[i]!=s[i-1]:
        g.append(i-l)
        l=i
g.append(N-l)

M=len(g)
ans=0

if s[0]=="0":
    if K>M//2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>=N:
                break
            elif j==0:
                ans=max(ans,sum(g[0:2*K]))
            elif j%2==1:
                ans=max(ans,sum(g[j:j+2*K+1]))
        print(ans)
    
else:
    if K>=M//2+M%2:
        print(N)
    else:
        for j in range(M):
            if j+2*K+1>=N:
                break
            elif j%2==0:
                ans=max(ans,sum(g[j:j+2*K+1]))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans_c,ans_n = int(s[0]),1,[] , []
    for i in range(1,len(s)):
        if tmp == int(s[i]):
            count += 1
        else:
            ans_c.append(tmp)
            ans_n.append(count)
            tmp = int(s[i])
            count = 1
    ans_c.append(tmp)
    ans_n.append(count)
    return ans_c,ans_n

   # AAABBCCCCA ⇒ A3B2C4A1

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a_c,a_n =rle(S)
a_len =len(a_c)
count =[0]*a_len
ans =0
if a_c[-1] ==1:
    f=1 
if a_c[-1] ==0:
    f=0 

if K >= (a_len +1)//2:
    ans =N
elif a_len==2:
    ans =N
elif a_len ==3 and a_c[0]==1:
    ans=N
else:
    if a_c[0] ==1:
        i=0
        while not(i +2*K +1 ==a_len+2 or i +2*K +1 ==a_len+3):
            count[i] =sum(a_n[i:i+2*K +1])
            i +=2
    else:
        count[0] =sum(a_n[:2*K])
        i=1
        while not(i +2*K +1 ==a_len +2 or i +2*K +1 == a_len +3):
            count[i] =sum(a_n[i:i+2*K+1])
            i +=2      

    ans =max(count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans = s[0], 1, []
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            ans.append((tmp,count))
            tmp = s[i]
            count = 1
    ans.append((tmp,count))
    return ans

   # AAABBCCCCA ⇒ A3B2C4A1

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a =rle(S)
a_len =len(a)
count =[0]*a_len
ans =0

if K >= (a_len +1)//2:
    ans =N
else:
    for i in range(a_len):
        j =0
        count_0 =0
        while count_0 <K and i+j <a_len: #and j <a_len:
            count[i] +=a[i+j][1]
            if a[i+j][0]=="0":
                count_0 +=1
                if count_0 ==K and i+j+1 <a_len :
                    count[i] +=a[i+j+1][1]
            j +=1
    ans =max(count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans = s[0], 1, []
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            ans.append((tmp,count))
            tmp = s[i]
            count = 1
    ans.append((tmp,count))
    return ans

   # AAABBCCCCA ⇒ A3B2C4A1

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a =rle(S)
a_len =len(a)
count =[0]*a_len
ans =0

if K >= (a_len +1)//2:
    ans =N
else:
    for i in range(a_len):
        j =0
        count_0 =0
        while count_0 <K and i+j <a_len and j <a_len:
            count[i] +=a[i+j][1]
            if a[i+j][0]=="0":
                count_0 +=1
                if count_0 ==K and i+j+1 <a_len :
                    count[i] +=a[i+j+1][1]
            j +=1
    ans =max(count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, S: str):
    d = []  # type: List[int]
    i = 0
    while True:
        r = 0
        while i < N and S[i] == "1":
            r += 1
            i += 1
        d.append(r)
        if i >= N:
            break
        s = 0
        while i < N and S[i] == "0":
            s += 1
            i += 1
        d.append(s)
    c = 2 * K + 1
    if c > len(d):
        print(sum(d))
        return
    print(max(sum(d[dl:dl + c]) for dl in range(0, len(d) - c + 1, 2)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

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

Submission status: Time Limit Exceeded

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

n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

A=deque(A)
if len(A)<=1:print(sum(A));exit()
ans=0
while len(A)>1:
    ans=max(ans,sum([A[i] for i in range(min(2*k+1,len(A)))]))
    A.popleft()
    A.popleft()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

A=deque(A)
if len(A)<=1:print(sum(A));exit()
ans=0
while len(A)>1:
    ans=max(ans,sum([A[i] for i in range(min(2*k+1,len(A)))]))
    A.popleft()
    A.popleft()
print(ans)

Submission status: Time Limit Exceeded

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

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

if len(count)==1:
  print(N)
  exit()

ans=0
for i in range(len(count)-1):
  if count[i][0]=="0":
    cnt=1
  else:
    cnt=0
  val=count[i][1]
  for j in range(i+1,len(count)):
    if count[j][0]=="0":
      val+=count[j][1]
      cnt+=1
      if cnt==K+1:
        val-=count[j][1]
        break
    else:
      val+=count[j][1]
  ans=max(ans,val)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
one = [i.count('1') for i in s.split('0') if i.count('1') > 0]
zero = [i.count('0') for i in s.split('1') if i.count('0') > 0]
if s[0] == '1':
    nums = sum([[i, j] for i, j in zip(one,zero)], [])
    if s[-1] == '1':
        nums.append(one[-1])
    a = sum(nums[:k*2+1])
    rslt = a
    for i in range(k*2+1,len(nums), 2):
        a += sum(nums[i:i+2])
        a -= sum(nums[i-2*k-1:i-2*k+1])        
        rslt = max(rslt, a)
else:
    nums = sum([[i, j] for i, j in zip(zero,one)], [])
    if s[-1] == '0':
        nums.append(zero[-1])
    a = sum(nums[:k*2])
    rslt = a
    for i in range(k*2, len(nums), 2):
        a += sum(nums[i:i+2])
        a -= sum(nums[max(0,i-2*k-1):i-2*k+1])
        rslt = max(rslt, a)
print(rslt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
s = input()
chk_0 = []
chk_1 = []
c0 = 0
c1 = 0
chk_0_append = chk_0.append
chk_1_append = chk_1.append
if s[0]=='0':
  c0 += 1
else:
  c1 += 1
  chk_0_append(0)

for i in range(n-1):
  if s[i]=='0' and s[i+1]=='0':
    c0 += 1
  if s[i]=='0' and s[i+1]=='1':
    chk_0_append(c0)
    c0 = 0
    c1 = 1
  if s[i]=='1' and s[i+1]=='0':
    chk_1_append(c1)
    c0 = 1
    c1 = 0
  if s[i]=='1' and s[i+1]=='1':
    c1 += 1

if c0 != 0:
  chk_0_append(c0)
  chk_1_append(0)
elif c1 != 0:
  chk_1_append(c1)
  chk_0_append(0)

if len(chk_0) <= k:
  print(n)
  exit()

chk_1 = tuple(chk_1)
chk_0 = tuple(chk_0)
ab = [x+y for x,y in zip(chk_0,chk_1)]
ab = tuple(ab)

ans = 0
for i in range(len(chk_0)-k+1):
  chk = sum(ab[i:i+k])
  if i >= 1:
    chk += chk_1[i-1]
  ans = max(ans,chk)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
s = input()
chk_0 = []
chk_1 = []
c0 = 0
c1 = 0
chk_0_append = chk_0.append
chk_1_append = chk_1.append
if s[0]=='0':
  c0 += 1
else:
  c1 += 1
  chk_0_append(0)

for i in range(n-1):
  if s[i]=='0' and s[i+1]=='0':
    c0 += 1
  if s[i]=='0' and s[i+1]=='1':
    chk_0_append(c0)
    c0 = 0
    c1 = 1
  if s[i]=='1' and s[i+1]=='0':
    chk_1_append(c1)
    c0 = 1
    c1 = 0
  if s[i]=='1' and s[i+1]=='1':
    c1 += 1

if c0 != 0:
  chk_0_append(c0)
  chk_1_append(0)
elif c1 != 0:
  chk_1_append(c1)
  chk_0_append(0)

if len(chk_0) <= k:
  print(n)
  exit()

ab = [x+y for x,y in zip(chk_0,chk_1)]
ab = tuple(ab)
chk_1 = tuple(chk_1)
#print(chk_0,chk_1,ab)
ans = 0
for i in range(len(chk_0)-k+1):
  chk = sum(ab[i:i+k])
  if i >= 1:
    chk += chk_1[i-1]
  ans = max(ans,chk)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n,k = map(int,input().split())
  s = input()
  chk_0 = []
  chk_1 = []
  c0 = 0
  c1 = 0
  chk_0_append = chk_0.append
  chk_1_append = chk_1.append
  if s[0]=='0':
    c0 += 1
  else:
    c1 += 1
    chk_0_append(0)

  for i in range(n-1):
    if s[i]=='0' and s[i+1]=='0':
      c0 += 1
    if s[i]=='0' and s[i+1]=='1':
      chk_0_append(c0)
      c0 = 0
      c1 = 1
    if s[i]=='1' and s[i+1]=='0':
      chk_1_append(c1)
      c0 = 1
      c1 = 0
    if s[i]=='1' and s[i+1]=='1':
      c1 += 1

  if c0 != 0:
    chk_0_append(c0)
    chk_1_append(0)
  elif c1 != 0:
    chk_1_append(c1)
    chk_0_append(0)

  if len(chk_0) <= k:
    print(n)
    exit()

  ab = [x+y for x,y in zip(chk_0,chk_1)]
  ab = tuple(ab)
  chk_1 = tuple(chk_1)
  #print(chk_0,chk_1,ab)
  ans = 0
  for i in range(len(chk_0)-k+1):
    chk = sum(ab[i:i+k])
    if i >= 1:
      chk += chk_1[i-1]
    ans = max(ans,chk)
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
s = input()
chk_0 = []
chk_1 = []
c0 = 0
c1 = 0
if s[0]=='0':
  c0 += 1
else:
  c1 += 1
  chk_0.append(0)
  
for i in range(n-1):
  if s[i]=='0' and s[i+1]=='0':
    c0 += 1
  if s[i]=='0' and s[i+1]=='1':
    chk_0.append(c0)
    c0 = 0
    c1 = 1
  if s[i]=='1' and s[i+1]=='0':
    chk_1.append(c1)
    c0 = 1
    c1 = 0
  if s[i]=='1' and s[i+1]=='1':
    c1 += 1
    
if c0 != 0:
  chk_0.append(c0)
  chk_1.append(0)
elif c1 != 0:
  chk_1.append(c1)
  chk_0.append(0)

if len(chk_0) <= k:
  print(n)
  exit()
  
ab = [x+y for x,y in zip(chk_0,chk_1)]
ab = tuple(ab)
chk_1 = tuple(chk_1)
#print(chk_0,chk_1,ab)
ans = 0
for i in range(len(chk_0)-k+1):
  chk = sum(ab[i:i+k])
  if i >= 1:
    chk += chk_1[i-1]
  ans = max(ans,chk)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def cont(s):
    ret = []
    if s[0] == '0':
        ret.append(0)
    tgt = s[0]
    i = 0
    count = 0
    while i < len(s):
        if s[i] == tgt:
            count += 1
        else:
            ret.append(count)
            count = 1
            if tgt == '0': tgt = '1'
            else: tgt = '0'
        if i == len(s)-1:
            ret.append(count)
        i += 1
    return ret        
cont_s = cont(s)
if len(cont_s) <= 2*k+1:
    print(sum(cont_s))
else:
    acum = [sum(cont_s[i:i+2*k+1]) for i in range(0, n+2*k+1, 2)]
    print(max(acum))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
cnt = 1
counts = []

if S[0]=='0':
  counts.append(0)
if N == 1:
  counts.append(1)
  
for i in range(1,N):
  if S[i-1]!=S[i]:
    counts.append(cnt)
    cnt = 1
  else:
    cnt += 1
  #print(i)
  if i == N-1:
    counts.append(cnt)

#print(counts)
m = 0
K = min(K,len(counts)//2)
for i in range(len(counts)//2-K+1):
  m = max(m,sum(counts[2*i:2*(i+K)+1]))
print(m)

Submission status: Time Limit Exceeded

Solution code:
import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    s = input()
    s_first = s[0]
    s_last = s[-1]

    s_groupby = itertools.groupby(s)
    len_group = []

    if s_first == "0":
        len_group.append(0)

    for key, group in s_groupby:
        list_group = list(group)
        len_group.append(len(list_group))

    if s_last == "0":
        len_group.append(0)

    range_num = 2*k + 1
    ans = 0

    if range_num >= len(len_group):
        ans = sum(len_group)
    else:
        begin = 0
        end = 0
        while end != len(len_group):
            end = begin + range_num
            ans = max(ans,sum(len_group[begin:end]))
            begin += 2

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left,bisect_right,insort
#input = sys.stdin.readline

def main():
    n,k=map(int,input().split())
    s=list(input())
    flg,cnt,chk='1',0,[0]    
    for i in range(n):
        if s[i]==flg:
            chk[cnt]+=1
        else:
            flg=str((int(flg)+1)%2)
            cnt+=1
            chk.append(1)
    lng=len(chk)
    if k*2>lng:
        print(n)
    else:
        i=1
        ans=0
        while i+2*(k-1)<=n-1:
            ans=max(ans,sum(chk[i-1:i+2*k]))
            i+=2
        print(ans)

if __name__ == '__main__':
    main()

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 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * K + 1
ans = 0
for i in range(0, len(nums), 2):
    tmp = 0

    left = i
    right = min(i + add, len(nums))
    for j in range(left, right):
        tmp += nums[j]
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n, k = map(int,input().split())
d = str(input())
tmp = list(d)
data = [int(s) for s in tmp]

cnt = 0
ans_cnt = 0
ans = 0

cnt_0 = []
cnt_1 = []

cnt0 = 0
cnt1 = 0

cnt_1.append(0)
for i in range(n):
    if i == 0:
        tmp = 0
    elif data[i-1] == 1 and data[i] == 0:
        cnt_1.append(cnt1)
        cnt1 = 0
    elif data[i - 1] == 0 and data[i] == 1:
        cnt_0.append(cnt0)
        cnt0 = 0

    if data[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

    if i == n-1:
        if cnt0 != 0:
            cnt_0.append(cnt0)
        if cnt1 != 0:
            cnt_1.append(cnt1)
cnt_1.append(0)

change = min(k, len(cnt_0))
if data[0] == 0:
    start_1 = 0
else:
    start_1 = 1

ans = 0
for i in range(len(cnt_0)):
    tmp_ans = 0
    for j in range(i, min(i+change, len(cnt_0)), 1):
       tmp_ans += cnt_0[j]+cnt_1[j+start_1]
    tmp_ans += cnt_1[j+start_1+1]
    ans = max(ans, tmp_ans)

if len(cnt_0) == 0:
    ans = max(ans, cnt_1[1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n, k = map(int,input().split())
d = str(input())
tmp = list(d)
data = [int(s) for s in tmp]

cnt = 0
ans_cnt = 0
ans = 0

cnt_0 = []
cnt_1 = []

cnt0 = 0
cnt1 = 0

cnt_1.append(0)
for i in range(n):
    if i == 0:
        tmp = 0
    elif data[i-1] == 1 and data[i] == 0:
        cnt_1.append(cnt1)
        cnt1 = 0
    elif data[i - 1] == 0 and data[i] == 1:
        cnt_0.append(cnt0)
        cnt0 = 0

    if data[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

    if i == n-1:
        if cnt0 != 0:
            cnt_0.append(cnt0)
        if cnt1 != 0:
            cnt_1.append(cnt1)
cnt_1.append(0)

change = min(k, len(cnt_0))
if data[0] == 0:
    start_1 = 0
else:
    start_1 = 1

ans = 0
for i in range(len(cnt_0)):
    tmp_ans = 0
    for j in range(i, min(i+change, len(cnt_0)), 1):
       tmp_ans += cnt_0[j]+cnt_1[j+start_1]
    tmp_ans += cnt_1[j+start_1+1]
    ans = max(ans, tmp_ans)

if len(cnt_0) == 0:
    ans = max(ans, cnt_1[1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#124_D
N,K=map(int,input().split())
S=input()
cnt=[]
if S[0]=='0':
    cnt.append(0)
res=1
for i in range(1,N):
    if S[i-1]==S[i]:
        res+=1
    else:
        cnt.append(res)
        res=1
cnt.append(res)
if S[-1]=='0':
    cnt.append(0)

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

Submission status: Time Limit Exceeded

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

s=input()
s = list(s)
if s[0] == '0':
    count0 = 1
else:
    count0 = 0

memo = []
ans = 0
a = ''
for i in range(len(s)):
    #print(i)
    memo.append(s[i])
    ans = max(ans, len(memo))
    if i<n-1:
        if s[i] == '1' and s[i+1] == '0':
            count0 += 1
            if count0 == k+1:
                while True:
                    a = memo.pop(0)
                    if a == '0' and memo[0] == '1':
                        count0 = k
                        break
print(ans)

Submission status: Time Limit Exceeded

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

ZERO, ONE = [], []
now = "1"
count = 0
for c in s:
    if c == now:
        count += 1
    else:
        if now == "0":
            ZERO.append(count)
        else:
            ONE.append(count)
        now = c
        count = 1
ONE.append(count)
ONE[0] -= 1; ONE[-1] -= 1

m = len(ZERO)
if k >= m:
    print(n)
    exit()

answer = 0
for i in range(m - k + 1):
    temporary = sum(ZERO[i:i + k]) + sum(ONE[i:i + k + 1])
    answer = max(answer, temporary)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    for i in range(0,N-num+1):
        test=[]
        count=0
        for j in range(i,i+num):
            test.append(int(S[j]))
        test=groupby(test)
        for key,group in test:
            if key==0:
                count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
s = list(input())
max_ans = 0
for i in range(n):
    now = i
    if max_ans > n - now:
        break
    ans = 0
    rest = k
    if s[now] == "1":
        q = 0
    else:
        q = 1
        rest -= 1
    while rest >= 0:
        ans += 1
        if now == n-1:
            break
        if s[now + 1] == "1":
            if q:
                q = 0
            else:
                pass
        else:
            if q:
                pass
            else:
                rest -= 1
                q = 1

        now += 1

    max_ans = max(max_ans, ans)
print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = list(input())
max_ans = 0
for i in range(n):
    now = i
    ans = 0
    rest = k
    if s[now] == "1":
        q = 0
    else:
        q = 1
        rest -= 1
    while rest >= 0:
        ans += 1
        if now == n-1:
            break
        if s[now + 1] == "1":
            if q:
                q = 0
            else:
                pass
        else:
            if q:
                pass
            else:
                rest -= 1
                q = 1

        now += 1

    max_ans = max(max_ans, ans)
print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from itertools import groupby
def input(): return sys.stdin.readline().rstrip()

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

    ans = 0
    l = 0
    que = deque()
    que_sum = 0
    for k, v in groupby(S):
        if k == '0':
            l0 = len(tuple(v))
            que.append(l + l0)
            if len(que) > K:
                que.popleft()
            que_sum = sum(que)
        else:
            l = len(tuple(v))
            que_sum += l
        if que_sum > ans:
            ans = que_sum
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
s=input()
if '0' not in s:
    print(len(s))
else:
    s2 = []
    count = 1
    for i in range(1,len(s)):
        if s[i-1] == s[i]:
            count += 1
        if s[i-1] != s[i]:
            s2.append(count)
            count = 1
    s2.append(count)
    if s[0] != '1':
        s2.insert(0,0)
    if s[-1] != '1':
        s2.append(0)
    ans2 = 0
    K2 = 2*K+1
    for i in range(0,max(1,(len(s2) - K2)//2 +2)):
        ans2 = max(ans2,sum(s2[2*i:2*i+K2]))
    print(ans2)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
s=input()
if '0' not in s:
    print(len(s))
else:
    s2 = []
    count = 1
    for i in range(1,len(s)):
        if s[i-1] == s[i]:
            count += 1
        if s[i-1] != s[i]:
            s2.append(count)
            count = 1
    s2.append(count)
    if s[0] != '1':
        s2.insert(0,0)
    if s[-1] != '1':
        s2.append(0)
    ans2 = 0
    K2 = 2*K+1
    for i in range(0,max(1,len(s2) - K2 +1),2):
        ans2 = max(ans2,sum(s2[i:i+K2]))
    print(ans2)

Submission status: Time Limit Exceeded

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

cnt = 0

if s[0] == '0': ss.append(0)
i = 0
while i < n:
    j = i
    while j < n and s[i] == s[j]: j += 1
    ss.append(j-i)
    i = j
if s[-1] == '0': ss.append(0)

#print(ss)
ans = []
i = 0
while i < n:
    #print(ans, i, sum(ss[i:i+2*k+1]))
    #if i+2*k+1 > n:
    #    break
    ans.append(sum(ss[i:i+2*k+1]))
    i += 2

print(max(ans))

Submission status: Time Limit Exceeded

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

cnt = 0

if s[0] == '0': ss.append(0)
i = 0
while i < n:
    j = i
    while j < n and s[i] == s[j]: j += 1
    ss.append(j-i)
    i = j
if s[-1] == '0': ss.append(0)

#print(ss)
ans = 0
i = 0
while i < n:
    #print(ans, i, sum(ss[i:i+2*k+1]))
    #if i+2*k+1 > n:
    #    break
    ans = max(ans, sum(ss[i:i+2*k+1]))

    i += 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
s = input()
lista = []
if s[0] == '0':
    lista.append(0)
now = s[0]
count = 0
for i in s:
    if now == i:
        count += 1
    else:
        lista.append(count)
        count = 1
        now = i
lista.append(count)
ans = 0
for i in range(0,len(lista),2):
    ans= max(ans,sum(lista[i:i+2*K+1]))
for i in range(1,len(lista),2):
    ans= max(ans,sum(lista[i:i+2*K]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
l = [0] * (k * 2 + 1)
c = '1'
p = 0
ret = 0
for i in range(len(s)):
    if s[i] != c:
        ret = max(ret, i - l[p])
        l.append(i)
        if c == '1':
            l = l[2:]
        c = s[i]
ret = max(ret, n - l[p])
print(ret)