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:
import re

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

def popcnt(n):
  return bin(n).count("1")

cands = []
for xor in range(2 ** len(S)):
  if len(re.split('1+', bin(xor))) != 2:
    continue
  cands.append(xor)

for _ in range(K):
  best_score = max([len(v) for v in re.findall(r'1+', S)])
  best_xor = 0
  for xor in cands:
    res = bin(intS ^ xor)
    matchs = re.findall(r'1+', res)      
    if matchs:
      score = max([len(v) for v in matchs])
    else:
      score = 0
    
    if score > best_score:
      best_score = score
      best_xor = xor
      # print(xor, bin(xor), res, bin(res), _popcnt)
        
  intS = intS ^ best_xor
    
print(max([len(v) for v in re.findall(r'1+', bin(intS))]))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = [int(i) for i in list(input())]
start = 0
m = 0
for i in range(N):
  t = 0
  c = 0
  k = K
  for s in S[i:]:
    if k == 0 and s == 0:
      break
    c+=1
    if(s == 0 and t == 0):
      t = 1
    elif(s == 1 and t == 1):
      k -= 1
      t = 0
  if(m < c):
    m = c
  if(i+m >= N):
    break
print(m)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from itertools import groupby

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

  num = []
  cot = []
  for k, n in groupby(S):
    num.append(k)
    cot.append(len(list(n)))

  if num[0] == "1":
    x = K*2+1
  else:
    x = K*2

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

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

runlength_one = []
runlength_zero = []
counter = 0
prev = '1'
for s in S:
    if s == prev:
        counter += 1
    else:
        if s == '1':
            runlength_zero.append(counter)
        else:
            runlength_one.append(counter)
        counter = 1
        prev = s
if S[-1] == '1':
    runlength_one.append(counter)
else:
    runlength_zero.append(counter)


max = 0
for i in range(len(runlength_one) - K + 1):
    length = sum(runlength_one[i:i+K+1]) + sum(runlength_zero[i:i+K])
    max = length if max < length else max

if max == 0:
    max = sum(runlength_one) + sum(runlength_zero)

print(str(max))

Submission status: Time Limit Exceeded

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

    chunks = []
    prev = S[0]
    count = 0
    for s in S[1:]:
        count += 1
        if prev != s:
            chunks.append(count)
            #if prev == '0':
            #    chunks.append(-1 * count)
            #else:
            #    chunks.append(count)
            count = 0
        prev = s

    chunks.append(count + 1)
    #if prev == '0':
    #    chunks.append(-1 * (count + 1))
    #else:
    #    chunks.append(count + 1)

    if S[0] == '0':
        chunks.insert(0, 0)
    if S[-1] == '0':
        chunks.append(0)
    #if chunks[0] < 0:
    #    chunks.insert(0, 0)
    #if chunks[-1] < 0:
    #    chunks.append(0)

    #print(chunks)

    cands = []
    cand = chunks[0:(2 * K + 1)]
    #print(cand)
    cands.append(sum(cand))

    i = 0
    first = True
    for c in chunks:
    #for i in range(2 * K + 1, len(chunks), 2):
        if i < (2 * K + 1):
            i += 1
            continue
        #print(i)
        if first:
            cand.append(c)
            first = False
            continue
        cand.append(c)
        first = True
        #cand.append(chunks[i])
        #cand.append(chunks[i + 1])
        cand = cand[2:]
        #print(cand)
        cands.append(sum(cand))
        i += 1

    #print(cands)
    print(max(cands))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

N, K = map(int, input().split())
S = sys.stdin.readline()
S = S[:-1]
check = S[0]
if check == '0':
    Slist = [0]
else:
    Slist = []
count = 1
num = len(S)-1
for i in range(num):
    if S[i+1] == check:
        count += 1
    else:
        Slist.append(count)
        check = S[i+1]
        count = 1
Slist.append(count)

if S[-1] == '0':
    Slist.append(0)

a = int((len(Slist)-2*K+1)/2)
if K >= int((len(Slist)-1)/2):
    print(sum(Slist))
else:
    sumlist = [sum(Slist[2*i:2*K+1+2*i]) for i in range(a)]
    print(max(sumlist))

Submission status: Time Limit Exceeded

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

value = [0]*n
ans = [0]*n
k = 0
flag = True

for i in range(n):

    if i > 0 and s[i] != s[i-1]:
        k += 1

    if s[i] == '1' :
        value[k] += 1

    if s[i] == '0' :
        value[k] -= 1



j = 0
count = p + 1
while j != n:
    for i in range(j,n):
        
        if value[i] > 0:
            ans[j] += value[i]

        if value[i] < 0:
           
            if count == 1:
               
                count = p + 1
                j += 1
                break

            ans[j] += -value[i]
            count -= 1 
    else:
        j += 1

    
    



ans = sorted(ans,reverse = True)
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

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

num = []
cot = []
for k, n in groupby(S):
  num.append(k)
  cot.append(len(list(n)))

if num[0] == "1":
  x = K*2+1
else:
  x = K*2

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
c = []
import itertools
for _, g in itertools.groupby(s):
  c.append(len(list(g)))

c = c + [0]
ans = 1

if s[0] == "1":
  for i in range(0, len(c), 2):
    if i+2*k+1 > len(c):
      ans = max(ans, sum(c[i:]))
    else:
      ans = max(ans, sum(c[i:i+2*k+1]))
else:
  c = [0] + c
  for i in range(0, len(c), 2):
    if i+2*k+1 > len(c):
      ans = max(ans, sum(c[i:]))
    else:
      ans = max(ans, sum(c[i:i+2*k+1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
L = []
rp = 1
for i in range(1,len(S)):
    if S[i-1] == S[i]:
        rp += 1
    else:
        L.append(rp)
        rp = 1
else:
    L.append(rp)
#print(L)
if S[0] == "1":
    if len(L)//2 <= K:
        print(N)
    else:
        M = [0] * len(L)
        for i in range(len(L)//2-K+1):
            now = sum(L[2*i:2*i+1+2*K])
            M[i] = now
        #    print(M)
        print(max(M))
else:
    if (len(L)+1)//2 < K:
        print(N)
    else:
        M = [0] * len(L)
        M[0] = sum(L[:2*K])
        for i in range(len(L)//2-K+1):
            now = sum(L[2*i+1:2*i+2+2*K])
            M[i+1] = now
        print(max(M))

Submission status: Time Limit Exceeded

Solution code:
# ハノイの塔的な感じで、変換して『連続する』1をいくつまで増やせるか。順番は可換。
# 組み合わせは NC2 * K 回ある。多そう。

N, K = (int(i) for i in input().split())
S = input() # strにしてある

# 1.連続する1の数を数える関数が必要
# 2.変換の機構が必要
# 3.総当りする？
# 0があるところだけに絞ってもいい


# 1.連続する1の数を数える関数
def count_1(string):
  length = len(string)
  num = 0
  num_max = 0
  for i in range(length):
    if string[i] == '1':
      num += 1
      num_max = max(num_max, num)
    else:
      num =0
  return num_max



# 2.変換の機構
def change(string, l, r):
  hoge = str()
  for i in range(l, r):
    hoge += str( abs( int(string[i])-1 ) )
  return string[:l] + hoge + string[r:]
  


# 3.総当りする？

num = count_1(S)
S_list = [S]
for k in range(K):
  for S_k in S_list:
    for i in range(N):
      for j in range(i,N):
        num = max(num, count_1(change(S_k, i, j)))
        S_list.append(change(S_k, i, j))



print(num)

Submission status: Time Limit Exceeded

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

if len(s) == 1:
    print(1)
else:
    # 最初に塊を把握
    chunk_len = []
    prev = s[0]
    cnt = 1
    max_score = 0
    for x in s[1:]:
        if x == prev:
            cnt += 1
        else:
            if prev == '0':
                prev = '1'
            else:
                prev = '0'
                max_score = max(max_score, cnt)
            chunk_len.append(cnt)
            cnt = 1
            
    chunk_len.append(cnt)
    n_chunk = len(chunk_len)

    if s[0] == '1':
        # 偶数番目を順番に入れ替えていく
        n_odd_chunk = int(n_chunk / 2)
        if n_odd_chunk - k <= 0:
            print(len(s))
        else:
            for i in range(n_odd_chunk - k + 1):
                score = sum(chunk_len[2*i:2*(i+k)+1])
                if max_score < score:
                    max_score = score
            
            print(max_score)
    else:
        # 奇数番目を順番に入れ替えていく
        n_odd_chunk = int((n_chunk+1) / 2)
        if n_odd_chunk - k <= 0:
            print(len(s))
        else:
            for i in range(n_odd_chunk - k + 1):
                if i == 0:
                    score = sum(chunk_len[:2*(i+k)])
                else:
                    score = sum(chunk_len[2*i-1:2*(i+k)])

                if max_score < score:
                    max_score = score
        
            print(max_score)

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 = [int(i) for i in input().split()]
S = list(map (int, list(input())))
start = S[0]
row = []
state = [0,start]
for i in S:
    if i == start:
        state[0] += 1
    else:
        row.append(state)
        start = i
        state = [1,i]
row.append(state)
ans = []
for i in range(max(len(row)-K*2+1,1)):
    if row[i][1] == 1:
        ans.append(sum([row[i][0] for i in range(i,min(K*2+i+1,len(row)))]))
    else:
        ans.append(sum([row[i][0] for i in range(i,min(K*2+i,len(row)))]))
print(max(ans))

Submission status: Time Limit Exceeded

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

S_a = []
preval = 0
counter = 1
for i,val in enumerate(S):
    if i == 0:
        preval = val
        continue
    if val == preval:
        counter += 1
    else:
        if preval == '0':
            S_a.append(-1 * counter)
        else:
            S_a.append(counter)
        preval = val
        counter = 1
if preval == '0':
    S_a.append(-1 * counter)
else:
    S_a.append(counter)

maxnum = 0
tmpmax = 0
tmp = 0
mp = K
for idx_o,val_o in enumerate(S_a):
    if val_o < 0 and idx_o != 0:
        continue
    for idx,val in enumerate(S_a):
        if idx < idx_o:
            continue
        if val >= 0:
            tmp += val
        else:
            if mp > 0:
                tmp += val * -1
                mp -= 1
            else:
                tmpmax = tmp
                if maxnum < tmpmax:
                    maxnum = tmpmax
                break
    else:
        tmpmax = tmp
        if maxnum < tmpmax:
            maxnum = tmpmax
    mp = K
    tmp = 0
    tmpmax = 0


print(maxnum)

Submission status: Time Limit Exceeded

Solution code:
import re

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

def popcnt(n):
  return bin(n).count("1")

cands = []
for xor in range(2 ** len(S)):
  if len(re.split('1+', bin(xor))) != 2:
    continue
  cands.append(xor)

for _ in range(K):
  best_score = max([len(v) for v in re.findall(r'1+', S)])
  best_xor = 0
  for xor in cands:
    res = bin(intS ^ xor)
    try:
      score = max([len(v) for v in re.findall(r'1+', res)])
    except:
      score = 0
    
    if score > best_score:
      best_score = score
      best_xor = xor
      # print(xor, bin(xor), res, bin(res), _popcnt)
        
  intS = intS ^ best_xor
    
print(max([len(v) for v in re.findall(r'1+', bin(intS))]))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

stand = []
reverse = []
state = None
count = 0
tmp = None
for i in S:
	if i == "0":
		state = "stand"
	else:
		state = "reverse"
	if tmp == "stand" and state == "reverse":
		stand.append(count)
		count = 1
	elif tmp == "reverse" and state == "stand":
		reverse.append(count)
		count = 1
	else: # 状態が前と同じ
		count += 1
	tmp = state
if state == "stand":
	stand.append(count)
else:
	reverse.append(count)

if "0" not in S:
	print(len(S))
else:
	if K >= len(stand): # 全員逆立ちにできる
		print(len(S))
	else:
		if len(stand) > len(reverse):
			reverse.append(0)
			reverse.insert(0, 0)
		if len(stand) == len(reverse) and S[0] == "0":
			reverse.insert(0, 0)
		if len(stand) == len(reverse) and S[0] == "1":
			reverse.append(0)
		# print(stand)
		# print(reverse)
		max_ = 0
		for i in range(max(1, 1+len(reverse)-(K+1))):
			# print(reverse[i:i+K+1],stand[i:i+K])
			tmp = sum(reverse[i:i+K+1]+stand[i:i+K])
			if tmp > max_:
				max_ = tmp
		print(max_)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder
"""
def encode(S):
    code=[]
    code.append([int(S[0]),1])
    for s in S[1:]:
        if int(s)==code[-1][0]:
            code[-1][1]+=1
        else:
            code.append([int(s),1])
    return code

def main():
    N, K=list(map(int,input().split()))
    S=list(map(str,input().split()))[0]

    E=encode(S)
    
    L=[]
    krange=range(K)
    if E[0][0]==0:
        L.append(0)
    for s in E:
        if s[0]==1:
            L.append(s[1])
            for p in krange:
                if 2+p>len(L):
                    break
                L[-2-p]+=s[1]
        else:
            for p in krange:
                if 1+p>len(L):
                    continue
                L[-1-p]+=s[1]

    print(max(L))
            

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

zero_lens = []
one_lens = []
flag_zero_before = 'None'
zeros = 0
ones = 0

for i in range(n):
    if s[i] == '0':
        if flag_zero_before == False:
            one_lens.append(ones)
            ones = 0
        zeros += 1
        flag_zero_before = True
    if s[i] == '1':
        if flag_zero_before and zeros != 0:
            zero_lens.append(zeros)
            zeros = 0
        ones += 1
        flag_zero_before = False

if s[-1] == '0':
    zero_lens.append(zeros)
if s[-1] == '1':
    one_lens.append(ones)

k = min(k, len(zero_lens))

counters = []
if s[0] == '1':
    for i in range(len(zero_lens) - k + 1):
        if i + k == len(one_lens):
            counter = sum(zero_lens[i: i+k]) + sum(one_lens[i: i+k])
        else:
            counter = sum(zero_lens[i: i+k]) + sum(one_lens[i: i+k+1])
        counters.append(counter)
elif s[0] == '0':
    for i in range(len(zero_lens) - k + 1):
        if i == 0:
            counter = sum(zero_lens[i: i+k]) + sum(one_lens[i: i+k])
        elif i + k > len(one_lens):
            counter = sum(zero_lens[i: i+k]) + sum(one_lens[i-1: i+k-1])
        else:
            counter = sum(zero_lens[i: i+k]) + sum(one_lens[i-1: i+k])
        counters.append(counter)

print(max(counters))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

S_ren = []
ren = 0
for s in S:
    if s == '0':
        if ren > 0:
            S_ren.append(ren)
            ren = -1
        else:
            ren += -1
    else:
        if ren < 0:
            S_ren.append(ren)
            ren = 1
        else:
            ren += 1
S_ren.append(ren)

if S_ren[-1] < 0:
    S_ren.append(0)

if S_ren[0] < 0:
    S_ren = S_ren[::-1] 
    S_ren.append(0)
    
S_ren = [abs(sren) for sren in S_ren]

ans = 0
if K*2 > len(S_ren):
    K = len(S_ren)//2
for i in range(((len(S_ren)+1)//2)-K):
    a = sum(S_ren[i*2:(i+K)*2+1])
    if a > ans:
        ans = a

print(ans)

Submission status: Time Limit Exceeded

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

clusters=[]
prev=-1
for s in S:
    if prev!=s:
        if prev!=-1:
            clusters.append((prev, seq))
        seq=0
    prev=s
    seq+=1
clusters.append((prev,seq))
clusters=[(1,0)] + clusters + [(1,0)]

ncls_0=0
for c in clusters:
    if c[0]==0:
        ncls_0 +=1

if ncls_0-K+1<=0:
    print(N)
    exit()

longest=0
for bgn_flip in range(ncls_0-K+1):
    clusters_copy=[]
    icls_0=-1
    ic_seq=[]
    for ic,c in enumerate(clusters):
        if c[0]==0:
            icls_0+=1
            if icls_0>=bgn_flip and icls_0 < bgn_flip+K:
                ic_seq.append(ic)

    seq=0
    for ic in range(ic_seq[0]-1,ic_seq[-1]+2):
        seq+=clusters[ic][1]
    if seq>longest:
        longest=seq

print(longest)

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 = 0 
  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 = max(m, 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 = max(m, sum(l[st:en]))

  print(m)

Submission status: Time Limit Exceeded

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

S_a = []
preval = 0
counter = 1
for i,val in enumerate(S):
    if i == 0:
        preval = val
        continue
    if val == preval:
        counter += 1
    else:
        if preval == '0':
            S_a.append(-1 * counter)
        else:
            S_a.append(counter)
        preval = val
        counter = 1
if preval == '0':
    S_a.append(-1 * counter)
else:
    S_a.append(counter)

maxnum = 0
tmpmax = 0
tmp = 0
mp = K
for idx_o,val_o in enumerate(S_a):
    for idx,val in enumerate(S_a):
        if idx < idx_o:
            continue
        if val >= 0:
            tmp += val
        else:
            if mp > 0:
                tmp += val * -1
                mp -= 1
            else:
                tmpmax = tmp
                if maxnum < tmpmax:
                    maxnum = tmpmax
                break
    else:
        tmpmax = tmp
        if maxnum < tmpmax:
            maxnum = tmpmax
    mp = K
    tmp = 0
    tmpmax = 0


print(maxnum)

Submission status: Time Limit Exceeded

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

# 奇数番目は1のカタマリの人数　偶数番目は0のカタマリの人数 両端は必ず1のカタマリの人数
now_state, now_count = '1', 0
L = []
Ladd = L.append
for i in range(len(S)):
  if S[i] == now_state:
    now_count += 1
  else:
    Ladd(now_count)
    # reset
    now_count = 1
    now_state = '1' if now_state == '0' else '0'
Ladd(now_count)
if now_state == '0':
  Ladd(0)

j = min(int((len(L)-1)/2), K) # 0のカタマリをひっくり返せるだけひっくり返す
print(max([sum(L[i:i+j*2+1]) for i in range(len(L)-j*2) if i%2==0]))

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().split()]
#import time
#t1= time.time()
S = input()
a= S[0]
b = S[0]
table = [0 for i in range(N+1)]
c = 0
l = 0
#t2 =time.time()
for s in S:
    if s == b:
        c += 1
        continue

    table[l]=c
    c = 1
    l+=1
    if b == '1':
        b = '0'
    else:
        b='1'
#t3 = time.time()
table[l]=c
table = table[0:l+1]
if a =='0':
    N = 2*K+1
    ans = sum(table[0:2*K])
    for i in range(1,len(table),2):
        ans = max(ans,sum(table[i:i+N]))

else:
    ans =0
    N = 2*K +1
    for i in range(0,len(table),2):
        ans = max(ans,sum(table[i:i+N]))
#print(table)
print(ans)

#print(t3-t2)
#print(t2-t1)

Submission status: Time Limit Exceeded

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

runlength_one = []
runlength_zero = []
counter = 0
prev = '1'
for s in S:
    if s == prev:
        counter += 1
    else:
        if s == '1':
            runlength_zero.append(counter)
        else:
            runlength_one.append(counter)
        counter = 1
        prev = s
if S[-1] == '1':
    runlength_one.append(counter)
else:
    runlength_zero.append(counter)


max = 0
for i in range(len(runlength_one)):
    length = sum(runlength_one[i:i+K+1]) + sum(runlength_zero[i:i+K])
    max = length if max < length else max

if max == 0:
    max = sum(runlength_one) + sum(runlength_zero)

print(str(max))

Submission status: Time Limit Exceeded

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

z_l = []
ans = []
total = 0
count = 0
if int(S[0])==0:
    flag = True
    st =0
else:
    flag = False
    st =1
ct = 0
for i in S:
    t = int(i)
    if t==0:
        if flag:
            pass
        else:
            flag=True
            z_l.append(ct)
            ct=0
        count+=1
    else:
        if flag:
            flag=False
            z_l.append(count)
            count=0
        ct+=1
if count==0:
    z_l.append(ct)
else:
    z_l.append(count)
leng=len(z_l)
for i in range(leng):
    if i+2*K>leng:
        tmp = sum(z_l[i:])
    else:
        if st==0:
            if i%2==0:
                tmp = sum(z_l[i:i+2*K])
            else:
                tmp = sum(z_l[i:i+2*K+1])
        else:
            if i%2==0:
                tmp = sum(z_l[i:i+2*K+1])
            else:
                tmp = sum(z_l[i:i+2*K])
    ans.append(tmp)
total = max(ans)

print(total)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
L = []
rp = 1
for i in range(1,len(S)):
    if S[i-1] == S[i]:
        rp += 1
    else:
        L.append(rp)
        rp = 1
else:
    L.append(rp)
#print(L)
if S[0] == "1":
    if len(L)//2 <= K:
        print(N)
    else:
        M = 0
        for i in range(len(L)//2-K+1):
            now = sum(L[2*i:2*i+1+2*K])
            M = max(M,now)
        #    print(M)
        print(M)
else:
    if (len(L)+1)//2 < K:
        print(N)
    else:
        M = sum(L[:2*K])
        for i in range(len(L)//2-K+1):
            now = sum(L[2*i+1:2*i+2+2*K])
            M = max(M,now)
        print(M)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().split()]
#import time
#t1= time.time()
S = input()
a= S[0]
b = S[0]
table = [0 for i in range(N+1)]
c = 0
l = 0
#t2 =time.time()
for s in S:
    if s == b:
        c += 1
        continue
    else:
        table[l]=c
        c = 1
        l+=1
        if b == '1':
            b = '0'
        else:
            b='1'
#t3 = time.time()
table[l]=c
table = table[0:l+1]
if a =='0':
    N = 2*K+1
    ans = sum(table[0:2*K])
    for i in range(1,len(table),2):
        ans = max(ans,sum(table[i:i+N]))

else:
    ans =0
    N = 2*K +1
    for i in range(0,len(table),2):
        ans = max(ans,sum(table[i:i+N]))
#print(table)
print(ans)

#print(t3-t2)
#print(t2-t1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder
"""
def encode(S):
    code=[]
    code.append([int(S[0]),1])
    for s in S[1:]:
        if int(s)==code[-1][0]:
            code[-1][1]+=1
        else:
            code.append([int(s),1])
    return code

def main():
    N, K=list(map(int,input().split()))
    S=list(map(str,input().split()))[0]

    E=encode(S)

    L=[]
    if E[0][0]==0:
        L.append(0)
    for s in E:
        if s[0]==1:
            L.append(s[1])
            for p in range(K):
                if 2+p>len(L):
                    break
                L[-2-p]+=s[1]
        else:
            for p in range(K):
                if 1+p>len(L):
                    continue
                L[-1-p]+=s[1]

    print(max(L))
            

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Z = [j for j, s in enumerate(S) if (j > 0 and s == 0 and S[j] != S[j-1]) or (j == 0 and s == 0)] + [N]
Y = [j for j, s in enumerate(S) if (j > 0 and s == 1 and S[j] != S[j-1]) or (j == 0 and s == 1)] + [N]
result = 0
if len(Z) <= K:
    print(N)
else:
    for i in range(len(Z)-K):
        if i == 0:
            result = Z[i+K]
        else:
            result = max(result, Z[i+K] - max([y for y in Y if y <= Z[i]]))
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

arr0 = np.array(list(map(len, s.split('1'))))
arr0 = arr0[arr0!=0]

arr1 = np.array(list(map(len, s.split('0'))))
arr1 = arr1[arr1!=0]


ans = 0

if s[0] == '0':
    for i in range(len(arr0)):
        
        if i == 0:
            length = arr0[i:i+k].sum() + arr1[i:i+k].sum()
        else:
            length = arr0[i:i+k].sum() + arr1[i-1:i+k].sum()
        ans = max(ans, length)
        
else:        
    for i in range(len(arr0)):
        length = arr0[i:i+k].sum() + arr1[i:i+k+1].sum()
        ans = max(ans, length)
        

if len(s) == s.count('1'):
    print(len(s))
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    n, k = map(int, input().split())
    s = input()
    m = count(s)
    sl = [s]
    if jimei(s):
        print(n)
        sys.exit()
    for i in range(k):
        nl = []
        for a in sl:
            for l in range(n):
                for r in range(l+1, n):
                    t = invert(a, l, r)
                    if jimei(t) and i < k -1:
                        print(n)
                        sys.exit()
                    if count(t) == n:
                        print(n)
                        sys.exit()
                    c = count(t)
                    m = m if m > c else c
                    nl.append(t)
        sl = list(set(nl))
    print(m)

def count(s):
    return len(sorted(s.split('0'))[-1])

def invert(s, l, r):
    return s[:l] + ''.join([str(abs(p-1)) for p in map(int, list(s[l:r]))]) + s[r:]

def jimei(s):
    if s.count('0') == len(s) or s.count('1') == len(s):
        return True
    a = s.split('10')
    if len(a) > 2:
        return False
    elif len(a) == 2:
        b = a[1].split('01')
        if len(b) != 2:
            return False
        return a[0].count('1') == len(a[0]) and b[0].count('0') == len(b[0]) and b[1].count('1') == len(b[1])
    return False

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
S = input()
consecutive = 0
alternately = []
if S[0] == "0":
    first_num = "0"
else:
    first_num = "1"

current_num = first_num

for i in S:
    if i == current_num:
        consecutive += 1
    else:
        alternately.append(consecutive)
        consecutive = 1
        current_num = i
else:
    alternately.append(consecutive)

if len(alternately) % 2 == 0:
    num_of_zero = len(alternately) // 2
else:
    if first_num == "0":
        num_of_zero = len(alternately) // 2 + 1
    else:
        num_of_zero = len(alternately) // 2

res = 0
max_res = 0

if K >= num_of_zero:
    ans = sum(alternately)
else:
    if first_num == "0":
        for i in range(num_of_zero - K + 1):
            for k in range(2*K + 1):
                if 0 <= i*2 - 1 + k <= len(alternately) - 1:
                    res += alternately[i*2 - 1 +k]
            if res > max_res:
                max_res = res
            res = 0
        ans = max_res
    else:
        for i in range(num_of_zero - K + 1):
            for k in range(2*K + 1):
                if 0 <= i*2 + k <= len(alternately) - 1:
                    res += alternately[i*2 + k]
            if res > max_res:
                max_res = res
            res = 0
        ans = max_res

print(ans)

Submission status: Time Limit Exceeded

Solution code:
line = raw_input()
N, K = list(map(int, line.split(' ')))

line = raw_input()
chunks = []
flag = line[0] == '1'
zerocnt = 0
onecnt = 0
for i, val in enumerate(line):
    if flag:
        if val == '0':
            chunks.append((zerocnt, onecnt))
            onecnt = 0
            zerocnt = 0
            flag = False
    else:
        if val == '1':
            flag = True
    if val == '0':
        zerocnt += 1
    else:
        onecnt += 1
   
chunks.append((zerocnt, onecnt))

prev = (0,0)
results = []
for i, chunk in enumerate(chunks):
    result = prev[1] 
    for j in range(K):
        if i + j > len(chunks) - 1:
            break
        curr = chunks[i + j]
        result += curr[0] + curr[1]
    results.append(result)
    prev = chunk

print max(results)
# if chunks[0] > 0:
#     chunks = [0] + chunks
# if chunks[len(chunks)-1] < 0:
#     chunks = chunks + [0]

# prevVal = 0
# values = []
# for i in range(len(chunks) / 2):
#     values.append(-chunks[i * 2] + chunks[i * 2 + 1])