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 sub():
    N, K = [int(e) for e in input().split(" ")]
    ss = [int(e) for e in input()]
    if len(set(ss)) == 1:
        print(len(ss))
        return

    dd = [ss[i+1] - ss[i] for i in range(N-1)]
    memIdx = 0
    buf = []
    memNbOne = 0
    memChange = None
    for i, d in enumerate(dd):
        if d > 0:
            e = [(memIdx, i+1), 0]
            buf.append(e)
            memIdx = i+1
            memChange = d
        elif d < 0:
            e = [(memIdx, i+1), 1]
            buf.append(e)
            memIdx = i+1
            memChange = d
    if memChange > 0:
        e = [(memIdx, N), 1]
        buf.append(e)
    else:
        e = [(memIdx, N), 0]
        buf.append(e)
    # print(buf)
    maxScore = 0
    for i in range(len(buf)):
        score = 0
        count = 0
        lastNext = None
        for j in range(i, len(buf)):
            lastNext = j + 1
            b, flag = buf[j]
            score = score + b[1]-b[0]
            if flag == 0:
                count = count + 1
            if count >= K:
                break
        if i-1 >= 0:
            b, flag = buf[i-1]
            if flag == 1:
                score = score + b[1] - b[0]
        if lastNext is not None:
            if lastNext < len(buf):
                b, flag = buf[lastNext]
                if flag == 1:
                    score = score + b[1] - b[0]

        if score > maxScore:
            maxScore = score
        # print(i, score)
    print(maxScore)
sub()

Submission status: Time Limit Exceeded

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

a = []
x = 0 #1の個数
y = 0 #0の個数
for i in range(n):
  if s[i] == 1:
    x += 1
  else:
    y += 1
  if x > 0 and y > 0:
    if s[i] == 0:
      a.append(x)
      x = 0
    else:
      a.append(-y)
      y = 0
if x > y:
  a.append(x)
else:
  a.append(-y)

m = len(a)
ans = 0
for i in range(m):
  x = 0
  flag = 0
  for j in range(m - i):
    if flag < k:
      if a[i+j] > 0:
        x += a[i+j]
      else:
        x += -a[i+j]
        flag += 1
    if flag == k and a[i+j] >0:
      x += a[i+j]
      flag += 1
  if ans < x:
    ans = x
print(ans)

Submission status: Time Limit Exceeded

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

a = []
x = 0 #1の個数
y = 0 #0の個数
for i in range(n):
  if s[i] == 1:
    x += 1
  else:
    y += 1
  if x > 0 and y > 0:
    if s[i] == 0:
      a.append(x)
      x = 0
    else:
      a.append(-y)
      y = 0
if x > y:
  a.append(x)
else:
  a.append(-y)

m = len(a)
ans = [] #2k+1個の和
for i in range(m):
  x = 0
  flag = 0
  for j in range(m - i):
    if flag < k:
      if a[i+j] > 0:
        x += a[i+j]
      else:
        x += -a[i+j]
        flag += 1
    if flag == k and a[i+j] >0:
      x += a[i+j]
      flag += 1
  ans.append(x)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = [int(i) for i in input().split()]
    s = [int(i) for i in list(input())]
    table = []
    now = 1
    cnt = 0
    for i in range(n):
        if s[i] == now:
            cnt += 1
        else:
            table.append(cnt)
            cnt = 1
            now ^= 1 # 0　と 1 の切り替え
    if cnt != 0:
        table.append(cnt)
    if len(table)%2 == 0:
        # 奇数で終わらせれば、1 で終わったことになる
        table.append(0)
    ans = 0
    l, r = 0, min(len(table)-1, 2*k)
    while r < len(table):
        ans = max(ans, sum(table[l:r+1]))
        l += 2
        r += 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K = map(int,input().split())
S = input()
i=0
while i<N and S[i] =='0':
  i += 1
left_0 = i
if i==N:
  print(N)
  sys.exit()
i=0
while S[N-1-i]=='0':
  i += 1
right_0 = i

H = [0,left_0]
count =1
for i in range(N-left_0-right_0):
  if i==N-left_0-right_0-1:
    H.append(count)
  elif S[i+left_0] == S[i+left_0+1]:
    count += 1
  else:
    H.append(count)
    count =1
H.append(right_0)
H.append(0)
new_k = 2*K+1
ans=0
LL = (len(H)-new_k)//2
if LL>=0:
  for i in range(LL+1):
    ans = max(ans,sum(H[(i*2):(new_k+i*2)]))
else:
  ans = N
print(ans)

Submission status: Time Limit Exceeded

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

i=0
while i<N and S[i] =='0':
  i += 1
left_0 = i
i=0
while i<N and S[N-1-i]=='0':
  i += 1
right_0 = i

H = []
H.append(0)
H.append(left_0)
count =1
for i in range(N-left_0-right_0):
  if i==N-left_0-right_0-1:
    H.append(count)
  elif S[i+left_0] == S[i+left_0+1]:
    count += 1
  else:
    H.append(count)
    count =1
H.append(right_0)
H.append(0)
new_k = 2*K+1
ans=0
LL = len(H)-new_k
if LL>=0:
  for i in range(LL//2+1):
    ans = max(ans,sum(H[(i*2):(new_k+i*2)]))
else:
  ans = N
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = list(input())
A = [1]
for i in range(len(S)-1):
    if S[i] == S[i+1]:
        A[-1] += 1
    else:
        A.append(1)
J = len(A)
if S == ['0']:
    print(1)
elif (S[0] == '1') & (S[-1] == '1'):
    ANSL = []
    if J <= 2*K+1:
        print(sum(A))
    else:
        for i in range((J+1)//2-K):
            ANS = 0
            for j in range(2*K+1):
                ANS += A[2*i+j]
            ANSL.append(ANS)
        print(max(ANSL))
elif (S[0] == '0') & (S[-1] == '0'):
    if J <= 2*K-1:
        print(sum(A))
    else:
        ANSL = []
        ANSM = 0
        for i in range(2*K):
            ANSM += A[i]
        ANSN = 0
        for i in range(J-2*K,J):
            ANSN += A[i]
        for i in range((J-1)//2-K):
            B = A[2*i+1:2*i+2+2*K]
            ANSL.append(sum(B))
        ANSL.append(ANSM)
        ANSL.append(ANSN)
        print(max(ANSL))
elif (S[0] == '0') & (S[-1] == '1'):
    if J <= 2*K:
        print(sum(A))
    else:
        ANSL = []
        ANSM = 0
        for i in range(2*K):
            ANSM += A[i]
        for i in range(J//2-K):
            B = A[2*i+1:2*i+2*K+2]
            ANSL.append(sum(B))
        ANSL.append(ANSM)
        print(max(ANSL))
else:
    A.reverse()
    if J <= 2*K-1:
        print(sum(A))
    else:
        ANSL = []
        ANSM = 0
        for i in range(2*K):
            ANSM += A[i]
        for i in range(J//2-K):
            B = A[2*i-1:2*i+2*K]
            ANSL.append(sum(B))
        ANSL.append(ANSM)
        print(max(ANSL))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
S = input()
L = []
t = 1
for k in range(1,N):
    if S[k-1] == S[k]:
        t += 1
    else:
        L.append(t)
        t = 1
L.append(t)
l = len(L)
if S[0] == "0":
    ans = sum(L[:2*K])
    for k in range(l-2*K+1):
        if k%2 == 1:
            ans = max(ans,sum(L[k:k+2*K+1]))
else:
    ans = sum(L[:2*K+1])
    for k in range(l-2*K+1):
        if k%2 == 0:
            ans = max(ans,sum(L[k:k+2*K+1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = input()
length = 0
test_length = 0
test_count = 0

# 指示の回数分下記処理を繰り返す。
for y in range(K):
    # 文字列の長さ分繰り返す。
    for i in range(len(S)):
        #もし調べる文字列の始まりが0だった場合は、00011 となる最大の長さを格納する。
        if int(S[i]) == 0:
            test_count = 0
            test_length = 0
            # test_count が2になるまで続ける。
            while test_count != 2:
                for z in range(i , len(S)):
                    if z == len(S) - 1 :
                        pass
                    else:
                        if int(S[z]) == int(S[z + 1]):
                            test_length += 1
                        else:
                            test_count += 1
                            test_length += 1
            length = test_length        

        elif int(S[i]) == 1:
            test_count = 0
            test_length = 0
            # test_count が3になるまで続ける。
            while test_count != 3:
                for z in range(i , len(S)):
                    print("test_count:",  test_count)
                    if z == len(S) - 1 :
                        pass
                    else:
                        print("score",int(S[z]) , int(S[z + 1]))
                        if int(S[z]) == int(S[z + 1]):
                            test_length += 1
                        else:
                            test_count += 1
                            test_length += 1
            length = test_length        

print(length)

Submission status: Time Limit Exceeded

Solution code:
import re


n, k = map(int, input().split())
s = input()
s_re = re.split(r'(0+)', s)
srl = len(s_re)
m = [0] * srl
if srl // 2 <= k:
    ans = [n]
else:
    for i, w in enumerate(s_re):
        m[i] = len(w)
    ans = [1]
    for i in range(0, srl, 2):
        ie = i + k * 2 + 1
        if ie <= srl:
            ans += [sum(m[i:ie])]
        else:
            break
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
'''input
5 1
00010
'''


N, K=map(int,input().split())
Sstr=input()
# print(Sstr)
S=[]

for i in range(N):
	S.append(int(Sstr[i]))

# print(S)
# flip=0
# for i in range(N-1):
# 	flip+=abs(S[i+1]-S[i])
# print(flip)


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

handstand = []
hs = 0

for j in range(n):
  flag = False
  remain_order = k # j=7
  for i in range(j,n):
    if s[i] == '1' or flag == True:
      hs += 1
      if s[i] == '1': flag = False
      if i == n-1:
          handstand.append(hs)
          hs = 0
          break
    else:
      if remain_order > 0:
        hs += 1
        remain_order -= 1
        flag = True
        if i == n-1:
          handstand.append(hs)
          break
      else:
        handstand.append(hs)
        hs = 0
        break

print(max(handstand))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Handstand
https://atcoder.jp/contests/abc124/tasks/abc124_d
WA
"""
import sys


from itertools import groupby
from collections import deque

def solve(N, K, S):
    seq = [[k, len(list(g))]  for k, g in groupby(S)]
    if len(seq) <= 2*K:
        return len(S)
    if seq[0][0] == '0':
        seq = [['1', 0]] + seq
    if len(seq) % 2 == 0:
        seq.append(['1', 0])

    seq = deque(seq)
    rem = deque()
    ans = 0
    for i in range(2*K+1):
        _, v = seq.popleft()
        ans += v
        rem.append(v)

    max_ans = ans
    while seq:
        try:
            ans -= rem.popleft()
            _, v = seq.popleft()
            ans += v
            ans -= rem.popleft()
            _, v = seq.popleft()
            ans += v
            max_ans = max(max_ans, ans)
        except:
            max_ans = max(max_ans, ans)
    return max_ans


def main(args):
    N, K = map(int, input().split())
    S = input()
    ans = solve(N, K, S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

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

for i in range(1, n):
    if s[i-1] != s[i]:
        l.append(c)
        c = 1
    else: 
        c +=1
l.append(c)

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

ll = len(l)
pl = 2 * k + 1

if ll <= pl:
    t = 0
    for i in range(ll):
        t += l[i]
    print(t)
else:
    m = 0
    for i in range(0, ll-pl+1, 2):
        t = 0
        for j in range(pl):
            t += l[i+j]
        m = t if (t > m) else m 
    print(m)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, K = [int(_) for _ in raw_input().split()]
    S = raw_input()
    elms = [S[0]]
    cnts = []
    cnt = 1
    for i in range(1,N):
        if S[i] == elms[-1]:
            cnt += 1
        else:
            cnts.append(cnt)
            elms.append(S[i])
            cnt = 1
    cnts.append(cnt)
    num_elm = len(elms)
    max_cont1 = 0
    for i in range(num_elm):
        if elms[i] == '1':
            tmp = sum(cnts[i:(i+2*K+1)])
            max_cont1 = max(max_cont1, tmp)
        elif i == 0:
            tmp = sum(cnts[i:(i+2*K)])
            max_cont1 = max(max_cont1, tmp)
    print str(max_cont1)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
lis = [0]*(len(li)+1)
for i in range(len(li)):
  lis[i+1]=lis[i]+li[i]
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  ds = sum( li[i*2:i*2+2*K+1] )
  a = min(i*2,len(li))
  b = min(i*2+2*K+1,len(li))

  ds2 = lis[b]-lis[a]
  s = max(s,ds)
print (s)

Submission status: Time Limit Exceeded

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

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  ds = sum( li[i*2:i*2+2*K+1] )
  s = max(s,ds)
print (s)

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[51]:

import sys
#input = sys.stdin.readline
N, K = map(int, input().split())
S = input()


# In[59]:

tmp = S[0]
f = S[0]
c_list = [0]*N
counter = 1
nb = 0
for i in range(1, N):
    #counter += 1
    #print(S[i], i)
    if S[i] != tmp:
        c_list[nb] = counter
        nb += 1
        counter = 0
        tmp = S[i]
    counter += 1
    if i == N-1:
        c_list[nb] = counter
    #print(S[i], i,counter, c_list)

#print(c_list)
pl = [0]*N
if len(c_list) <= K*2:
    #print("a")
    print(N)
else:
    #print("b")
    if f == "0":
        #print("c")
        for i in range(-1, len(c_list)-K*2, 2):
            #print(i, i+K*2+1)
            j = 0 if i < 0 else i
            pl[i] = sum(c_list[j:i+K*2+1])
    else:
        #print("d")
        for i in range(0, len(c_list)-K*2, 2):
            #print(i, i+K*2+1)
            j = i
            pl[i] = sum(c_list[j:i+K*2+1])
    #print(pl)
    print(max(pl))


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s = list(map(int, input()))

# Run Length Encoding
rle = list()
target = 1
count = 0
for i in range(n):
    if s[i] == target:
        count += 1
    else:
        target = 1 - target
        rle.append(count)
        count = 1
rle.append(count)
if target == 0:
    rle.append(0)

offset = 2 * k + 1
res = 0

# two pointers
for i in range(0, len(rle), 2):
    left = i
    right = min(i + offset, len(rle))
    cand = 0
    for j in range(left, right):
        cand += rle[j]
    res = max(res, cand)

print(res)

Submission status: Time Limit Exceeded

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

A = [-1]
B = []

if n == 1:
    l_max = 1
else:
    for i in range(0, n - 1):
        if S[i] == "0" and S[i + 1] == "1":
            A.append(i)
            A.sort()
        if S[i] == "1" and S[i + 1] == "0":
            B.append(i)
            B.sort()
    B.append(n - 1)
    if len(A) == 1 or len(B) == 1:
        l_max = n
    else:
        l_max = 0
        if S[0] == "0" and S[n - 1] == "0":
            m = len(A) - 1
            if k >= m + 2:
                k = m + 1
            for i in range(0, m - k + 2):
                l = B[k + i - 1] - A[i]
                if l > l_max:
                    l_max = l
        elif S[0] == "1" and S[n - 1] == "1":
            m = len(A) - 1
            if k >= m + 1:
                k = m
            for i in range(0, m - k + 1):
                l = B[k + i] - A[i]
                if l > l_max:
                    l_max = l
        elif S[0] == "0" and S[n - 1] == "1":
            m = len(A) - 1
            if k >= m + 1:
                k = m
            for i in range(0, m - k + 1):
                l = B[k + i - 1] - A[i]
                if l > l_max:
                    l_max = l
        elif S[0] == "1" and S[n - 1] == "0":
            m = len(A)
            if k >= m + 1:
                k = m
            for i in range(0, m - k + 1):
                l = B[k + i] - A[i]
                if l > l_max:
                    l_max = l

print(l_max)

Submission status: Time Limit Exceeded

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(lambda x:int(x), sys.stdin.readline().split())
    S = list(map(lambda x: int(x), list(sys.stdin.readline().rstrip())))
    start, end = 0, 0
    bStart, bEnd = 0, 0
    while True:
        # S[start:end]にある孤立した0がK個以下か
        sub = S[start:end]
        # print(S, start, end)
        # 11001101
        # print(start, end)
        z = 0
        prev = 1
        for i in range(len(sub)):
            if prev == 1 and sub[i] == 0:
                z += 1
            prev = sub[i]
        # print(z)
        # exit()
        # 全員を起立させられるので，広げる
        if z <= K:
            if bEnd - bStart < end - start:
                bStart, bEnd = start, end
                # print(S, start, end)
            
            end += 1
            if end == len(S) + 1:
                break
        # 反転しても逆立ちが残るので，狭める
        else:
            start += 1
    S[bStart:bEnd] = [1 for _ in range(bStart, bEnd)]

    o, maxO = 0, 0
    prev = 1
    for s in S:
        # print(prev, s)
        if prev == 1 and s == 0:
            if o > maxO:
                maxO = o
            o = 0
        elif s == 1:
            o += 1
        prev = s
    else:
        if o > maxO:
            maxO = o

    print(maxO)

Submission status: Time Limit Exceeded

Solution code:
import sys

if __name__ == '__main__':
    N, K = map(lambda x:int(x), sys.stdin.readline().split())
    S = list(map(lambda x: int(x), list(sys.stdin.readline().rstrip())))
    # print(S)
    start, end = 0, 0
    bStart, bEnd = 0, 0
    # print(S)
    while True:
            # S[start:end]にある孤立した0がK個以下か
        sub = S[start:end]
        # print(S, start, end)
        # 11001101
        # print(start, end)
        z = 0
        prev = 1
        for i in range(len(sub)):
            if prev == 1 and sub[i] == 0:
                z += 1
            prev = sub[i]
        # print(z)
        # exit()
        # 全員を起立させられるので，広げる
        if z <= K:
            if bEnd - bStart < end - start:
                bStart, bEnd = start, end
                # print(S, start, end)
            
            end += 1
            if end == len(S) + 1:
                break
        # 反転しても逆立ちが残るので，狭める
        else:
            start += 1
    # print(S)
    S[bStart:bEnd] = [1 for _ in range(bStart, bEnd)]
    # print(S, bStart, bEnd)

    o, maxO = 0, 0
    prev = 1
    for s in S:
        # print(prev, s)
        if prev == 0 and s == 1:
            o = 1
        elif prev == 1 and s == 0:
            if o > maxO:
                maxO = o
        elif prev == 1 and s == 1:
            o += 1
        prev = s
    else:
        if o > maxO:
            maxO = o

    print(maxO)

Submission status: Time Limit Exceeded

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

a = []
cnt = 0
for i in range(n-1):
    cnt += 1
    if s[i] != s[i+1]:
        a.append(cnt)
        cnt = 0 # reset
a.append(cnt+1)
# print(a) # 連続する0,1の数の配列を作った
### 前処理 両端が1の数を表す数列を作ることが出来た
if s[0] == "0": # 左端
    a.insert(0, 0)
if s[-1] == "0": # 右端
    a.append(0)
# print(a)
# print((len(a)-2*k+1)//2)
if (len(a)-2*k+1)/2 < 1:
    k = int((len(a)-1)/2)
# print(k)
ans = 0
for i in range((len(a)-2*k+1)//2):
    # b = 0
    b = sum(a[2*i:2*i+2*k+1])
    #for j in range(2*k+1):
    #    b += a[2*i+j]
    # print(i, b)
    ans = max(ans, b) # 最大値を更新していく
print(ans)

Submission status: Time Limit Exceeded

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

a = []
cnt = 0
for i in range(n-1):
    cnt += 1
    if s[i] != s[i+1]:
        a.append(cnt)
        cnt = 0 # reset
a.append(cnt+1)
# print(a) # 連続する0,1の数の配列を作った
### 前処理 両端が1の数を表す数列を作ることが出来た
if s[0] == "0": # 左端
    a.insert(0, 0)
if s[-1] == "0": # 右端
    a.append(0)
# print(a)
# print((len(a)-2*k+1)//2)
if (len(a)-2*k+1)/2 < 1:
    k = int((len(a)-1)/2)
# print(k)
ans = 0
for i in range((len(a)-2*k+1)//2):
    # b = 0
    b = sum(a[2*i:2*i+2*k+1])
    #for j in range(2*k+1):
    #    b += a[2*i+j]
    # print(i, b)
    ans = max(ans, b) # 最大値を更新していく
print(ans)

Submission status: Time Limit Exceeded

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

a = []
cnt = 0
for i in range(n-1):
    cnt += 1
    if s[i] != s[i+1]:
        a.append(cnt)
        cnt = 0 # reset
a.append(cnt+1)
# print(a) # 連続する0,1の数の配列を作った
### 前処理 両端が1の数を表す数列を作ることが出来た
if s[0] == "0": # 左端
    a.insert(0, 0)
if s[-1] == "0": # 右端
    a.append(0)
# print(a)
# print((len(a)-2*k+1)//2)
if (len(a)-2*k+1)/2 < 1:
    k = int((len(a)-1)/2)
# print(k)
ans = 0
for i in range((len(a)-2*k+1)//2):
    b = 0
    for j in range(2*k+1):
        b += a[2*i+j]
    # print(i, b)
    ans = max(ans, b) # 最大値を更新していく
print(ans)

Submission status: Time Limit Exceeded

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


s_len = len(S)
maxvalue = 0
mode = 0

check_i = [0] + [i+1 for i in range(s_len-1) if S[i] != S[i+1]]

for i in check_i:
    count = 0
    life = K
    for s in S[i:s_len]:
        if mode == 0 and s == '0':
            if life <= 0: break
            life -= 1
            mode = 1
        elif mode == 1 and s == '1':
            mode = 0
        count += 1
    if maxvalue < count:
        maxvalue = count
print(maxvalue)

Submission status: Time Limit Exceeded

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

maxvalue = 0
mode = 0
for i in range(len(S)):
    count = 0
    life = K
    for s in S[i:len(S)]:
        if mode == 0 and s == '0':
            if life <= 0: break
            life -= 1
            mode = 1
        elif mode == 1 and s == '1':
            mode = 0
        count += 1
    if maxvalue < count:
        maxvalue = count
print(maxvalue)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int, input().split())

# print(N, K)
S = input()
index_array = np.array([])
now_letter = "1"
letter_count = 0
for s in S:
    if s != now_letter:
        index_array = np.append(index_array, letter_count)
        now_letter = s
        letter_count = 1
    else:
        letter_count += 1
else:
    index_array = np.append(index_array, letter_count)
    if now_letter == "0":
        index_array = np.append(index_array, 0)
# print(index_array)
ans = 0

array_len = len(index_array)
if (K * 2 + 1) >= array_len:
    print(N)
    exit()
candidate = (array_len + 1) // 2 - K
for i in range(candidate):
    # print(index_array[i * 2:(i + K) * 2 + 1])
    ans = max(np.sum(index_array[i * 2:(i + K) * 2 + 1]), ans)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate as acc

N,K=map(int,input().split())
S=input()
First=S[0]
Last=S[N-1]
Now=First
cnt=0
Cont=[]
for s in S:    
    if Now=='1' and s=='0':
        Cont+=[cnt]
        cnt=0
        Now='0'
    elif Now=='0' and s=='1':
        Cont+=[cnt]
        cnt=0
        Now='1'
    cnt+=1
Cont+=[cnt]

lenC=len(Cont)
if First=="0":
    A1=[0]+[list(acc(Cont))[i] for i in range(lenC) if i%2==1]
    A0=[0]+[list(acc(Cont))[i] for i in range(lenC) if i%2==0]
else:
    A1=[list(acc(Cont))[i] for i in range(lenC) if i%2==0]
    A0=[0]+[list(acc(Cont))[i] for i in range(lenC) if i%2==1]

if Last=="0":
    A1+=[N]

if First=="0":
    if K<len(A1):
        print(max([A1[i+K]-A0[i] for i in range(len(A1)-K)]))
    else:
        print(A1[len(A1)-1])
else:
    if K<len(A1):
        print(max([A1[i+K]-A0[i] for i in range(len(A1)-K)]))
    else:
        print(A1[len(A1)-1])

Submission status: Time Limit Exceeded

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

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(len(S)):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == len(S)-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)

lk = int((len(D)-1)/2)
if K > lk:
    K = lk
ans = 0
for i in range(int((len(D)-2*K-1)/2)+1):
    j = 2*i
    k = 2*K + 2*i + 1
    sumd = sum(D[j:k])
    if sumd > ans:
        ans = sumd

print(ans)

Submission status: Time Limit Exceeded

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

D = []
count = 0
mode = 1
if S[0] == "0":
    D.append(0)
    mode = 0

for i in range(len(S)):
    if int(S[i]) == mode:
        count += 1
    else:
        D.append(count)
        count = 1
        mode = 1 - mode
    if i == len(S)-1:
        D.append(count)

if S[-1] == "0":
    D.append(0)
    mode = 0

if K > int((len(D)-1)/2):
    K = int((len(D)-1)/2)
ans = 0
for i in range(int((len(D)-2*K-1)/2)+1):
    j = 2*i
    k = 2*K + 2*i + 1
    if sum(D[j:k]) > ans:
        ans = sum(D[j:k])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N = [int(x) for x in stdin.readline().rstrip().split()]
S = [int(x) for x in list(stdin.readline().rstrip())]

one = []

c = 0

if S[0] != 1:
    one.append(0)

for i in range(N[0]):
    if i != 0:
        if S[i] != S[i-1]:
            one.append(c)
            c = 0
    c += 1
    if i + 1 == N[0]:
        one.append(c)

if S[-1] != 1:
    one.append(0)

ans = []

for k in range(max(len(one) // 2 + len(one) % 2 - N[1], 1)):
    ans.append(sum(one[2 * k:(2 * k) + (2 * N[1]) + 1]))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N = [int(x) for x in stdin.readline().rstrip().split()]
S = [int(x) for x in list(stdin.readline().rstrip())]

one = []

c = 0

if S[0] != 1:
    one.append(0)

for i in range(N[0]):
    if i != 0:
        if S[i] != S[i-1]:
            one.append(c)
            c = 0
    c += 1
    if i + 1 == N[0]:
        one.append(c)

if S[-1] != 1:
    one.append(0)

ans = []

for k in range(len(one) // 2 + len(one) % 2):
    ans.append(sum(one[2 * k:(2 * k) + (2 * N[1]) + 1]))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N = [int(x) for x in stdin.readline().rstrip().split()]
S = [int(x) for x in list(stdin.readline().rstrip())]

one = []
zero = []

c = 0

if S[0] != 1:
    one.append(0)

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

if S[-1] != 1:
    one.append(0)

ans = []

p = 0

for k in range(len(one) // 2 + len(one) % 2):
    ans.append(sum(one[2 * k:(2 * k) + (2 * N[1]) + 1]))

print(max(ans))

Submission status: Time Limit Exceeded

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

# solve

##. number of consecutive 0 groups and 1 groups
##. ex:
##.  s = '11101010110011'
##.       0: 0, 0, 0, 00
##.       1: 111, 1, 1, 11, 11
##.  zeros = [1, 1, 1, 2]
##.  ones = [3, 1, 1, 2, 2]
##.   (always count the edges of s as 1)
zeros = []
ones = []
_c = '1'
count = 0
for c in s:
	if _c == c:
		count += 1
	else:
		if _c == '0':
			zeros.append(count)
		else:
			ones.append(count)
		_c = c
		count = 1

if c == '0':
	zeros.append(count)
	ones.append(0)
else:
	ones.append(count)

if len(zeros) <= k:
	## flip all 0's
	ans = len(s)
else:
  ## flip k consecutive zero groups
  ans = 0
  i = 0
  while i + k <= len(zeros):
	  _ans = sum(zeros[i:i+k]) + sum(ones[i:i+k+1])
	  ans = max(ans, _ans)
	  i += 1

print(ans)

Submission status: Time Limit Exceeded

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

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[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=tmp+nums[j]
        
    ans=max(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

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

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

for i in s:
    if i == '0':
        if cnt_1 != 0:
            l.append(cnt_1)
            one.append((cnt_1))
            cnt_1 = 0
        cnt_0 += 1
    if i =='1':
        if cnt_0 != 0:
            l.append(cnt_0)
            cnt_0 = 0
        cnt_1 += 1

if cnt_1 != 0:
    l.append(cnt_1)
    one.append(cnt_1)
if cnt_0 != 0:
    l.append(cnt_0)
    l.append(0)

#print(one)
#print(l)


ans = 0

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

"""
if len(one) == 0:
    print(sum(l))

elif len(one) == 1:
    for i in range(len(l)):
        if ans < sum(l[i:i+2]):
            ans = sum(l[i:i+2])

if len(one) >= 2:
    for i in range(len(l)):
        if ans < sum(l[i:(k*2+1)+1]):
            ans = sum(l[i:(k*2+1)+1])
"""

print(ans)

Submission status: Time Limit Exceeded

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

lenzero=0
lenone=0
lenList=[]
for n in range(N):
    if S[n]=='0':
        if lenone>0:
            lenList.append(lenone)
        lenzero=lenzero+1
        lenone=0
    else:
        if lenzero>0:
            lenList.append(lenzero)
        lenone=lenone+1
        lenzero=0
lenList.append(max(lenzero,lenone))
if S[0] == '0':
    lenList=[0]+lenList

NL=len(lenList)

maxlist=[]
for  ns in range(0, NL, 2):
    rightedge=min(NL,ns+K*2)
    maxlist.append(sum(s for i,s in enumerate(lenList) if (i>=ns) & (i<=rightedge)))

print(max(maxlist))