Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

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

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

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

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

Sample Input 1

5 1
00010

Sample Output 1

4

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

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

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import re
import itertools

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

pattern = r"0+"
iterator = re.finditer(pattern ,S)
l = [match.span() for match in iterator]
count = len(l)

if count <= K:
    ans = N
else:
    ans = 0
    for k in range(K,-1,-1):
        for v in itertools.permutations(l, k):
            s = S
            for i in range(k):
                add = "1"*(v[i][1]-v[i][0])
                s = s[:v[i][0]] + add + s[v[i][1]:]
                splt = re.split(pattern, s)
                a = [len(splt[i]) for i in range(len(splt))]
                if max(a) >= ans:
                    ans = max(a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,K = (int(_) for _ in input().split())
    S = list(int(_) for _ in input())
    now = 1
    cnt = 0
    Nums = []
    ans = 0
    for i in range(N):
        if(S[i]==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
    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)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

ll = []
for i in range(len(s)):
    pre = "1"
    cnt0 = 0
    for j in range(i,len(s)):
        if s[j] != pre and s[j]=="0":
            cnt0 +=1
        pre = s[j]
        if cnt0 > K:
            break
        ll.append(j-i+1)
print(max(ll))

Submission status: Time Limit Exceeded

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

S = input()

C = []

one = True
c = 0
ans = 0
for s in S:
    if s=="0":
        if one:
            one = False
            C.append(c)
            c = 1
        else:
            c += 1
    else:
        if one:
            c += 1
        else:
            one = True
            C.append(c)
            c = 1
            
C.append(c)
CC = []
for i in range(0,max(min(N-K,len(C)),1))[::2]:
    CC.append(sum(C[i:i+(2*K)+1]))
    
print(max(CC))

Submission status: Time Limit Exceeded

Solution code:
def cul(lst, m):
    r = 0
    for i in lst:
        r  += i if i < m else m
    return r

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

a = 1
for i in range(1, len(s)):
    if s[i-1] == s[i]:
        a += 1
    else:
        val.append(a)
        a = 1
val.append(a)
ans = []
now = int(s[0])
for i in range(len(s)-k):
    ins = 0
    lst = val[i:i+k*2] if now == 0 else val[i:i+k*2+1]
    if len(lst) == 0: break
    ans.append(cul(lst, n))
    now = 1 if now == 0 else 0

print(max(ans) if not len(ans) == 0 else len(s))

Submission status: Time Limit Exceeded

Solution code:
def cul(lst, m):
    r = 0
    for i in lst:
        r  += i if i < m else m
    return r

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

a = 1
for i in range(1, len(s)):
    if s[i-1] == s[i]:
        a += 1
    else:
        val.append(a)
        a = 1
val.append(a)
ans = []
now = int(s[0])
for i in range(len(s)-k):
    ins = 0
    lst = val[i:i+k*2] if now == 0 else val[i:i+k*2+1]
    ans.append(cul(lst, n))
    now = 1 if now == 0 else 0

print(max(ans) if not len(ans) == 0 else len(s))

Submission status: Time Limit Exceeded

Solution code:
data = input().split()
N = int(data[0])
K = int(data[1])

TL = list(input())
TLLlist = []
now = TL[0]
nowlist = now
anslist = []

for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLLlist.append(len(nowlist))

hjm = 0
if TL[0] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    hjm = 1
elif TL[0] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    hjm = 2
for lop in range(hjm,len(TLLlist),2):
    if 2*K +  lop > len(TLLlist):
        break
    anslist.append( sum(TLLlist[lop:2*K + 1 + lop]) )


#print(TLlist)
#print(TLLlist)
#print(anslist)
print(max(anslist))

Submission status: Time Limit Exceeded

Solution code:
import re
import itertools
import copy

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

pattern = r'0+'

iterator = re.finditer(pattern ,S)
for match in iterator:
    where0.append(list(map(int, match.span())))

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

kouho = list(range(len(where0)))
conbination = list(itertools.combinations(kouho,K))

maxlength = 0
for conbi in conbination:
    temp = copy.copy(lstS)
    tempstr = ''
    for i in range(len(conbi)):
        for j in range(where0[conbi[i]][0], where0[conbi[i]][1]):
            temp[j] = '1'
    for x in temp:
        tempstr += x
    cnt = 0
    for i in range(len(tempstr)):
        if temp[i] == '1':
            cnt += 1
            if cnt > maxlength:
                maxlength = cnt
        else:
            cnt = 0

print(maxlength)

Submission status: Time Limit Exceeded

Solution code:
import copy

data = input().split()
N = int(data[0])
K = int(data[1])

TL = list(input())
TLlist = []
TLLlist = []
now = TL[0]
nowlist = now
anslist = []

for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)
TLLlist.append(len(nowlist))


if TLlist[0][:1] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    for lop in range(1,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( sum(TLLlist[lop:2*K + 1 + lop]) )
elif TLlist[0][:1] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    for lop in range(2,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( sum(TLLlist[lop:2*K + 1 + lop]) )


#print(TLlist)
#print(TLLlist)
#print(anslist)
print(max(anslist))

Submission status: Time Limit Exceeded

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

if(n != 1):
    sl = []
    c = 1
    if (s[0] == "1"):
        sl.append(0)
    for i in range(n):
        if (i != 0):
            if (s[i] == s[i-1]):
                c += 1
            else:
                sl.append(c)
                c = 1
    sl.append(c)
    cl = []
    c = 0
    for i in range(n):
        st = i-k
        ed = i + k+1
        if (st < 0):
            st = 0
        if (k % 2 == 1 and i % 2 == 0 or k % 2 == 0 and i % 2 == 1):  # kが奇数の時、0の箇所（すなわちiが偶数の箇所）を中心に反転
            if (c == 0):
                cl.append(sum(sl[st: ed]))
            else:
                t = cl[c - 1]
                t += sum(sl[ed - 3: ed-1])
                if (st > 0):
                    cst = st-2
                    if (cst < 0):
                        cst = 0
                    t -= sum(sl[cst: st])
                cl.append(t)
                c += 1

    print(max(cl))
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
a = []

n,k = map(int, input().split())
for x in range(k):
  a.append(0)
q = input()

p = 0
c = 0
mx = 0

for i in range(n-1):
  c = c+1  
  if q[i] == q[i+1]:
    lalala = 1

  elif (int(q[i]) == 1) & (int(q[i+1]) == 0) :
    
    for x in a:
      p = p + x
    if mx < p+c:
      mx = p+c
    p = 0
    
  elif (int(q[i]) == 0) & (int(q[i+1]) == 1):
    a.append(c)
    a.pop(0)
    c = 0
for x in a:
  p = p + x
if int(q[n-1]) == 1:
  if mx < p+c+1:
    mx = p+c+1
else:
  p=0
  a.pop(0)
  for x in a:
    p = p + x
  if mx < p+c+1:
    mx = p+c+1
  


print(mx)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = list(input())
S = [int(S[i]) for i in range(N)]

def return_ans(S_initial, S):
    ans = 0
    block_size_list = []
    tmp_block_size = 1
    for i in range(1, N):
        if S[i - 1] == S[i]:
            tmp_block_size += 1

        else:
            block_size_list.append(tmp_block_size)
            tmp_block_size = 1
        if i == N - 1:
            block_size_list.append(tmp_block_size)

    block_size_list.append(0)

    times = len(block_size_list) - K * 2

    block_size_list.append(0)
    if K * 2 >= len(block_size_list) - 1:
        ans = len(S)
    else:
        if S_initial == 0:
            ans = max([sum(block_size_list[i:i + K * 2 + i % 2]) for i in range(times)])

        else:
            ans = max([sum(block_size_list[i:i + K * 2 + (i + 1) % 2]) for i in range(times)])

    return ans

print(return_ans(S[0], S))

Submission status: Time Limit Exceeded

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

arr = [0 for _ in range(N)]
idx = 0
pre = '1'
if S[0] == '0':
    idx += 1
    arr[0] = 0
    pre = '0'

for i in range(N):
    if pre == S[i]:
        arr[idx] += 1
    else:
        idx += 1
        arr[idx] += 1
    pre = S[i]

max_lensum = 0
for i in range(0, idx+1, 2):
    #print("arr", arr)
    #print("arr", arr[i:min(i+2*K+1, idx+1)])
    lensum = sum(arr[i:min(i+2*K+1, idx+1)])
    if lensum > max_lensum:
        max_lensum = lensum
    if i+2*K+1 > idx: break
print(max_lensum)

Submission status: Time Limit Exceeded

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

ls_try = []

prev = '1'
for i, s in enumerate(S):
    if s == '0' and prev == '1':
        ls_try.append(i)
    prev = s

ans_try = []
ans = 0
temp = 0
for s in S:
    if s == '1':
        temp += 1
    else:
        ans = max(ans,temp)
        temp = 0
ans = max(ans,temp)
ans_try.append(ans)

for l_try in ls_try:
    S_copy = S[:]
    ct = 0
    prev = '1'
    for i in range(N - l_try):
        if S_copy[l_try + i] == '1' and prev == '0':
            ct += 1
        if ct >= K:
            break
        prev = S_copy[l_try + i]
        S_copy[l_try + i] = '1'
    ans = 0
    temp = 0
    for s in S_copy:
        if s == '1':
            temp += 1
        else:
            ans = max(ans,temp)
            temp = 0
    ans = max(ans,temp)
    ans_try.append(ans)
print(max(ans_try))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
n,k = map(int,input().split())

s = input()

now = s[0]
tmp = 0

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

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
    tmp+=1
h.append(tmp)

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

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

s = input()

now = s[0]
tmp = 0

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

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
    tmp+=1
h.append(tmp)

h = np.array(h)

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
N,K = (int(i) for i in input().split())
S = list(str(input()))
d = []
k = 1
for i in range(len(S)):
    if i == len(S)-1:
        d.append(k)
    elif S[i]==S[i+1]:
        k += 1
    else:
        d.append(k)
        k = 1
m = 0
if len(d) == 1:
    m = abs(d[0])
else:
    if S[0]=='1':
        for i in [2*n for n in range(len(d)//2)]:
            #print("d[i:i+2*K+1]={}".format(d[i:i+2*K+1]))
            m = max(m,sum(d[i:i+2*K+1]))
    else:
        m = sum(d[0:2*K])
        for i in [2*n+1 for n in range(len(d)//2)]:
            #print("d[i:i+2*K+1]={}".format(d[i:i+2*K+1]))
            m = max(m,sum(d[i:i+2*K+1]))
print(m)

Submission status: Time Limit Exceeded

Solution code:
a = []

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

for i in range(k):
  a.append(0)
q = input()


if int(q[0]) == 1:
  a.append(0)

c = 0
mx = 0

for i in range(n-1):
  c = c+1  
  if q[i] == q[i+1]:
    lalala = 1

  elif (int(q[i]) == 1) & (int(q[i+1]) == 0):
    for x in range(k+1):
      a[x] = a[x]+c
    c = 0
    if mx < a[0]:
      mx = a[0]
    a.pop(0)
    
  elif (int(q[i]) == 0) & (int(q[i+1]) == 1):
    for x in range(k):
      a[x] = a[x]+c
    c = 0
    a.append(0)

a[0] = a[0]+c+1
if mx < a[0]:
  mx = a[0]


print(mx)

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/abc124/tasks/abc124_d
#TLE

NK = [int(i) for i in input().split()]
Sarray = [int(x) for x in list(str(input()))]
N = NK[0]
K = NK[1]
'''
Sarray = list(S)

for i in range(len(Sarray)):
    Sarray[i] = int(Sarray[i])
    if Sarray[i] == 0:
        Sarray[i] = -1
'''

for i in range(len(Sarray)):
    Sarray[i] = Sarray[i] * 2 - 1


mode = Sarray[0]
a = [0]

for i in range(len(Sarray)):
    c = (len(a) - 1) % 2
    b = (-1)** c * mode
    if Sarray[i] != b:
        a.append(0)
    a[len(a) - 1] += 1

adjust = 0
if mode == 1:
    adjust = 1

tmp = 0
count = []

for l in range(adjust,len(a) + 1,2):
    u = l
    v = l + 2 * (K - 1)
    if l > 0:
        u = l - 1
    if l + 2 * K - 1 < len(a):
        v = l + 2 * K - 1

    for i in range(u, v + 1):
        if i < len(a):
            tmp += a[i]
        else:
            break

    count.append(tmp)
    tmp = 0

print(max(count))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=list(map(int,list(input())))
t=[1 if s[0]==1 else -1]
ans=0
for i in range(1,n):
    if s[i]==s[i-1]:
        t[-1]+=1 if s[i]==1 else -1
    else:
        t+=[1 if s[i]==1 else -1]
for i in range(len(t)):
    temp=0
    l=k*2+1 if t[i]>0 else k*2
    for j in range(l):
        if 0<=i+j<len(t):
            temp+=abs(t[i+j])
    ans=max(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

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

## 連続するものをlistとして保持する
import re

def nchars(s,n):
    reg = re.compile("(.)\\1{%d,}" % (n-1))
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s =s[m.end():]
        
candidates = list(nchars(S,1))
## いい具合にnumpyで操作
import numpy as np
count_0 = np.zeros((len(candidates)))
count_1 = np.zeros((len(candidates)))

for i,candidate in enumerate(candidates):
  if int(candidate[0]) == 0:
    count_0[i] += len(candidate)
  else:
    count_1[i] += len(candidate)
    
## 最小の試行回数
min_Try = len(np.where(count_0 != 0)[0])

change_ = np.where(count_0 != 0)[0]
## 最小の試行回数以下の時どうするかが厳しいな...
## 連続しないので、とりあえず大きい順に入れていけばオッケー
## 個数分だけ全部足して、indexで見たときに一番大きいやつが正解！！
if min_Try <= K :
  print(N)
else:
  count_ = count_0 + count_1
  del count_0,count_1
  #print(count_)
  change_list = []
  for k in range(min_Try-K+1):
    c__ = change_[k:k+K]
    s = max(0,c__[0]-1)
    e = min(len(candidates)-1,c__[-1]+1)
    #print(count_[s:e+1])
    change_list.append(np.sum(count_[s:e+1]))
  print(int(max(change_list)))

Submission status: Time Limit Exceeded

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

## 連続するものをlistとして保持する
import re

def nchars(s,n):
    reg = re.compile("(.)\\1{%d,}" % (n-1))
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s =s[m.end():]
        
candidates = list(nchars(S,1))
## いい具合にnumpyで操作
import numpy as np
count_0 = np.zeros((len(candidates)))
count_1 = np.zeros((len(candidates)))

for i,candidate in enumerate(candidates):
  if int(candidate[0]) == 0:
    count_0[i] += len(candidate)
  else:
    count_1[i] += len(candidate)
    
## 最小の試行回数
min_Try = len(np.where(count_0 != 0)[0])

change_ = np.where(count_0 != 0)[0]
## 最小の試行回数以下の時どうするかが厳しいな...
## 連続しないので、とりあえず大きい順に入れていけばオッケー
## 個数分だけ全部足して、indexで見たときに一番大きいやつが正解！！
if min_Try <= K :
  print(N)
else:
  count_ = count_0 + count_1
  #print(count_)
  change_list = []
  for k in range(min_Try-K+1):
    c__ = change_[k:k+K]
    s = max(0,c__[0]-1)
    e = min(len(candidates)-1,c__[-1]+1)
    #print(count_[s:e+1])
    change_list.append(np.sum(count_[s:e+1]))
  print(int(max(change_list)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc124_d

# input
n, k = [int(s) for s in input().split()]
S = input()
# get ans
node = [len(s) for s in S.split('0')]
node = [s for i, s in enumerate(node) if not (s==0 and i!=0 and i!=len(node)-1)]
arch = [len(s) for s in S.split('1')]
arch = list(filter(int, arch))
k = min(k, len(arch))
sls = [(i,i+k) for i in range(len(arch)-k+1)]
m = (sum(arch[i:j])+sum(node[i:j+1]) for i, j in sls)
ans = max(m)
# output
# print(node)
# print(arch)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

a = list(map(int, input().split()))
S = input()

first = int(S[0])
li = []
if(int(S[0]) == 0):
    li.append(0)

count = 0
for i in range(a[0]):
    if int(S[i]) == first:
        count += 1
        if i == a[0] - 1:
            li.append(count)
    else:
        li.append(count)
        count = 1
        first = (first + 1)% 2

if(int(S[-1]) == 0):
    li.append(0)

if(len(li) <= a[1]*2+1):
    print(a[0])
else:
    max = 0
    for i in range(int((len(li) - (a[1]*2+1)) / 2 + 1)):
        sum = 0
        for j in range(i*2, i*2 + a[1]*2+1):
            sum += li[j]
        if max < sum:
            max = sum

    print(max)

Submission status: Time Limit Exceeded

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


def main():
    n, k, s = load_input()

    starts = [0]
    ends = []
    for i in range(n):
        if 0 < i and s[i - 1] == '1' and s[i] == '0':
            ends.append(i)

        if 0 < i and s[i - 1] == '0' and s[i] == '1':
            starts.append(i)
    ends.append(n)

    ml = 0
    for start in starts:
        order = k
        if start == 0 and s[0] == '0':
            order -= 1
        for end in ends:
            if start < end:
                if order == 0:
                    if ml < end - start:
                        ml = end - start
                    break
                order -= 1
        if ml < end - start:
            ml = end - start
    print(ml)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
NK = [int(i) for i in input().split()]
S = str(input())

N = NK[0]
K = NK[1]
Sarray = list(S)

for i in range(len(Sarray)):
    Sarray[i] = int(Sarray[i])
    if Sarray[i] == 0:
        Sarray[i] = -1

mode = Sarray[0]
a = [0]

for i in range(len(Sarray)):
    c = (len(a) - 1) % 2
    b = (-1)** c * mode
    if Sarray[i] != b:
        a.append(0)
    a[len(a) - 1] += 1

#print(mode,a)

#aはmodeを先頭に同じのが何個続くか

adjust = 0
if mode == 1:
    adjust = 1

tmp = 0
count = []

for l in range(adjust,len(a) + 1,2):
    u = l
    v = l + 2 * K - 2
    if l > 0:
        u = l - 1
    if l + 2 * K - 1 < len(a):
        v = l + 2 * K - 1

    for i in range(u, v + 1):
        if i < len(a):
            tmp += a[i]
        else:
            break

    count.append(tmp)
    tmp = 0

print(max(count))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
S = [int(S[i:i+1]) for i in range(N)]
ns = []
c0 = 0
c1 = 0
s =  S[0]
for i in S:
    if i == 0:
        c0 += 1
        if c1 > 0:
            ns.append(c1)
            c1 = 0
    else:
        c1 += 1
        if c0 > 0:
            ns.append(c0)
            c0 = 0
if c0 > 0:
    ns.append(c0)
if c1 > 0:
    ns.append(c1)
msum = 0
ssum = 0
ofset = 0
if s == 0:
    while(2):
        if ofset == 0:
            for i in range(K * 2):
                ssum += ns[i]
                if i + 1 == len(ns):
                    print(ssum)
                    exit()
            ofset += 1
            msum  = ssum
            ssum = 0
        else:
            while(True):
                for i in range(K * 2 + 1):
                    ssum += ns[i + ofset]
                    if i + ofset + 1 == len(ns):
                        if msum < ssum:
                            msum = ssum
                        print(msum)
                        exit()
                if msum < ssum:
                    msum = ssum
                ssum = 0
                ofset += 2
else:
    while(True):
            for i in range(K * 2 + 1):
                ssum += ns[i + ofset]
                if i + ofset + 1 == len(ns):
                    if msum < ssum:
                        msum = ssum
                    print(msum)
                    exit()
            if msum < ssum:
                msum = ssum
            ssum = 0
            ofset += 2

Submission status: Time Limit Exceeded

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

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            line[ind] = counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        line[ind] = counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = counter0
        ind+=1
        
if ind%2 ==0:
        line[ind] = 0
        ind+=1
line = line[:ind]    
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    maxchain = 0
    for i in range(0,ind-(2*k+1)+1,2):
        chain = sum(line[i:i+2*k+1])
        if chain>maxchain:
            maxchain=chain
    print(maxchain)

Submission status: Time Limit Exceeded

Solution code:
import sys,re,copy
input = sys.stdin.readline

N,K=[int(x) for x in input().strip().split()]
S=input().strip()
Z=[len(x) for x in re.split(r'1+',S)]
O=[len(x) for x in re.split(r'0+',S)]

m=0
i=0
if S[0]=='1':
    Z.pop(0)
l1=len(O)
l0=len(Z)
while True:
    c=sum(O[i:i+K+1])+sum(Z[i:i+K])
    if c > m:
        m = c
    i+=1
    if i+K>l1 or i+K>l0:
        break

print(m)

Submission status: Time Limit Exceeded

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

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            line[ind] = counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        line[ind] = counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = counter0
        ind+=1
        
if ind%2 ==0:
        line[ind] = 0
        ind+=1
line = line[:ind]    
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    maxchain = 0
    for i in range(0,len(line)-(2*k+1)+1,2):
        chain = sum(line[i:i+2*k+1])
        if chain>maxchain:
            maxchain=chain
    print(maxchain)

Submission status: Time Limit Exceeded

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

import re

def nchars(s, n):
    """文字列 s に、同じ文字が n 個以上連続している部分文字列を見つける
    """
    assert n > 0
    reg = re.compile("(.)\\1{%d,}" % (n - 1))  # カンマを取ると n 個ちょうどになる
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s = s[m.end():]

s_list = list(nchars(S, 1))
s_list_num = [len(s) for s in s_list]

#print(s_list)
#print(s_list_num)

ans = 0
for i in range(len(s_list)):
    count = 0
    s_len = 0
    for j in range(i, len(s_list)):
        if s_list[j][0] == '0':
            count += 1
            if count > K:
                break
        s_len += s_list_num[j]
        
    ans = max(ans, s_len)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, copy
input = sys.stdin.readline

N, K = map(int, input().split())
S = list(input().replace('\n',''))
S = list(map(int, S))

max_ans = 0
cursol = 0
for i in range(N):
    cursol = i
    while cursol < N and S[cursol] == 1:
        cursol += 1
    for k in range(K):
        if cursol >= N:
            break
        l = cursol
        r = cursol
        while r < N and S[r] == 0:
            r += 1
        # print(i, k, l, r)
        cursol += (r - l)
        while cursol < N and S[cursol] == 1:
            cursol += 1
    ans = cursol - i
    max_ans = ans if ans > max_ans else max_ans

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
s = input()
 
l = []
count = 1
 
for i in range(len(s)):
  try:
    if s[i] == s[i+1]:
      count +=  1
    else:
      l.append(count)
      count = 1
  except:
    l.append(count)

if len(l) / 2 <= k:
  print(sum(l))
else:
  m = []
  if s[0] == '1':
    for i in range(len(l) // 2 - k + 1):
      st = max(0, i * 2)
      en = min(i * 2 + k * 2 + 1, len(l)) 
      m.append(sum(l[st:en]))
 
  else:
    for i in range((len(l) + 1) // 2 - k + 1):
      st = max(0, i * 2 - 1)
      en = min(i * 2 + k * 2, len(l)) 
      m.append(sum(l[st:en]))
 
  print(max(m))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
state_list = [int(_) for _ in input()]
state_num_list = []
 
counter = 1
prev_num = state_list[0]
# リストの改変
for n in range(1, N):
 
    if state_list[n] == prev_num:
        counter += 1
        continue
    else:
        state_num_list.append(counter)
        counter = 1
        prev_num = state_list[n]
state_num_list.append(counter)
 
max_sum = 0
# メイン
start_num = state_list[0]
for s in range(len(state_num_list)):
    count_num = 0
    if start_num == 0:
        count_num = K * 2
    else:
        count_num = K * 2 + 1
    
    check_sum = sum(state_num_list[s:s + count_num])
 
    max_sum = check_sum if max_sum < check_sum else max_sum
    start_num = 0 if start_num == 1 else 1
 
print(max_sum)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split()) 
t = list(str(input()))
t = [int(s) for s in t]
last = t[0]
temp_c = 0
s = []
con_c = 0
temp_con_c = 0
corrent_p = 0
for i in range(n):
    if last == t[i]:
        temp_c += 1
    else:
        last = t[i]
        s.append(temp_c)
        temp_c = 1
s.append(temp_c)
if t[0] == 0:
    start_n = 0
else:
    start_n = 1
l = len(s)
if k*2 <= l:
    if start_n == 0:
        for i in range(0,k*2):
            temp_con_c += s[i]
        con_c = temp_con_c
        temp_con_c = 0
        corrent_p = 1
    for i in range(corrent_p,l,2):
        for m in range(k*2+1):
            if i+m >= l:
                break
            temp_con_c += s[i+m]
        if temp_con_c > con_c:
            con_c = temp_con_c
        temp_con_c = 0
        
else:
    con_c = n
print(con_c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc124_d

# input
n, k = [int(s) for s in input().split()]
S = input()
# get ans
node = [len(s) for s in S.split('0')]
node = [s for i, s in enumerate(node) if not (s==0 and i!=0 and i!=len(node)-1)]
arch = [len(s) for s in S.split('1')]
arch = list(filter(int, arch))
def window(iterable, size):
    #TODO size = min(size, len(iterable))
    from itertools import tee
    iters = tee(iterable, size)
    for i in range(1, size):
        for each in iters[i:]:
            next(each, None)
    return zip(*iters)
k = min(k, len(arch))
sls = [(i,i+k) for i in range(len(arch)-k+1)]
m = (sum(arch[i:j]+node[i:j+1]) for i, j in sls)
ans = max(m)
# output
# print(node)
# print(arch)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
a = []
maxLen = 0
now = ''
for i in range(n):
    decriment = 0
    if now != s[i]:
        now = s[i]
        if now == '0':
            decriment = 1
        a.append([k, i, 0])
    for j in a:
        j[0] -= decriment
        if j[0] >= 0:
            j[2] += 1
for j in a:
    maxLen = max(maxLen, j[2])
print(maxLen)

Submission status: Time Limit Exceeded

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

S1 = []

tmp = 0
flag = False

if S[0]=="0":
    S1.append((0,0))

if S[-1]=="0":
    for i in range(N):
        if not flag:
            if S[i] =="1":
                flag = True
                tmp = i
            if i ==N-1:
                S1.append((i,i))
    
        if flag:
            if i==N-1:
                S1.append((tmp,i-1))
                S1.append((i,i))

            elif S[i]=="0":
                flag = False
                S1.append((tmp,i-1))



else:
    for i in range(N):
        if not flag:
            if S[i] =="1":
                flag = True
                tmp = i
            elif i ==N-1:
                S1.append((i,i))
    
        if flag:
            if S[i]=="0":
                flag = False
                S1.append((tmp,i-1))
            if i ==N-1:
                S1.append((tmp,N-1))

n = len(S1)

m = [0 for i in range(K+1)]

for k in range(K+1):
    M = 0
    i=0
    while i+k < n:
        M = max(M,S1[i+k][1]-S1[i][0]+1)
        i+=1
    m[k]=M
print(max(m))