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:
n, k = list(map(int, input().split(' ')))
s = list(map(int, list(input())))
pres = []
i = 0
while i < n:
    ka = 0
    while s[i] == s[i+ka]:
        ka += 1
        if ka+i >= n:
            break
    pres.append([s[i],ka])
    i += ka
ia = 0
result = []
while ia < len(pres):
    h = 0
    if pres[ia][0] == 0:
        if ia + 2*k <= len(pres):
            for p in range(2*k):
                h += pres[p+ia][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[p+ia][1]
            result.append(h)
    else:
        if ia + 2*k+1 <= len(pres):
            for p in range(2*k+1):
                h += pres[ia+p][1]
            result.append(h)
        else:
            for p in range(len(pres)-ia):
                h += pres[ia+p][1]
            result.append(h)
    ia += 1
print(max(result))

Submission status: Time Limit Exceeded

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値

L=1
L2=0
for i in range(n):
    count=0
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L2=j
                v+=1
                
            
        if count==k+1:
            ans=max(ans,j-L)
            #次はL2から始める
            L=L2
            break
            
        if s[j]=='E':
            ans=max(ans,j-L)
            print(ans)
            exit()

Submission status: Time Limit Exceeded

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

L=1
L2=0
for i in range(n):
    count=0
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L2=j
                v+=1
                continue
                
            
        if count==k+1:
            ans=max(ans,j-L)
            L=L2
            break
            
        if s[j]=='E':
            ans=max(ans,j-L)
            print(ans)
            exit()

Submission status: Time Limit Exceeded

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

L=1
L2=0
for i in range(n):
    count=0
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L2=j
                v+=1
                
            
        if count==k+1:
            ans=max(ans,j-L)
            L=L2
            break
            
        if s[j]=='E':
            ans=max(ans,j-L)
            print(ans)
            exit()

Submission status: Time Limit Exceeded

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

L=1
L2=0
for i in range(n):
    count=0
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L2=j
                v+=1
                
            
        if count==k+1:
            
            if i==0:
                ans=j-1
                break
                
            else:
                ans=max(ans,j-L)
                L=L2
                break
            
        if s[j]=='E':
            ans=max(ans,j-L)
            print(ans)
            exit()

Submission status: Time Limit Exceeded

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

L=[1]

for i in range(n):
    count=0
    v=0
    for j in range(L[i],n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L.append(j)
                v+=1
                
            
        if count==k+1:
            
            if i==0:
                ans=j-1
                break
                
            else:
                ans=max(ans,j-L[i])
                break
            
        if s[j]=='E':
            ans=max(ans,j-L[i])
            print(ans)
            exit()

Submission status: Time Limit Exceeded

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

sp = "1"
count = 0
cu = []
cd = []
for i in range(n):
    if sp == s[i]:
        count += 1
    else:
        if sp == "1":
            cu.append(count)
        else:
            cd.append(count)
        count = 1
    sp = s[i]
if sp == "1":
    cu.append(count)
else:
    cd.append(count)
ans = 0
for i in range(len(cd)):
    sn = 0
    ld = i
    rd = min(i + k - 1, len(cd)-1)
    sn += sum(cd[ld:rd+1])
    lu = i
    ru = min(rd+1,len(cu)-1)
    sn += sum(cu[lu:ru+1])
    ans = max(ans,sn)
if len(cd)==0:
    ans = n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
_, k = map(int, input().split())
S = input()
T = []
while S:
    if S[0] == "0":
        T += [re.match("0+", S).group()]
        S = S.lstrip("0")
    else:
        T += [re.match("1+", S).group()]
        S = S.lstrip("1")
T = [""]*("0" in T[0])+T+[""]*("0" in T[-1])
*L, = map(len, T)
A = [sum(L[:2*k+1])]
for i in range(len(T)-2*k-1):
    A += A[-1]-L[i]+L[i+2*k+1],
print(max(A[::2]))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
S = input().replace("01", "0 1").replace("10", "1 0").split()
S = [""]*("0" in S[0])+S
*L, = map(len, S)
print(max([sum(L[i:i+2*k+1]) for i in range(0, len(L), 2)]))

Submission status: Time Limit Exceeded

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

if s[0] == '1':
    length_01 = []
else:
    length_01 = [0]

a = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        a += 1
    else:
        length_01.append(a)
        a = 1

length_01.append(a)
if s[n-1] == '0':
    length_01.append(0)

num_0 = int((len(length_01)+1)/2)
if num_0 - 1 >= k:
    answer = 0
    for i in range(num_0):
        if answer < sum(length_01[2*i:2*(i+k)+1]):
            answer = sum(length_01[2*i:2*(i+k)+1])
else:
    answer = len(s)

print(answer)

Submission status: Time Limit Exceeded

Solution code:

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

#N = 10 ** 5
#K = 3
#S = "01" * ((10 ** 5) // 2 )

lis = []

nowchar = -1
num = 0

for i in range(N):

        if nowchar == S[i]:

            num += 1

        elif nowchar != -1:

            lis.append([nowchar,num])

            nowchar = S[i]
            num = 1

        else:

            nowchar = S[i]
            num = 1

lis.append([nowchar,num])


nlis = []
zeronum = 0
summ = 0
ans = 0


while True:

    if zeronum <= K:

        ans = max(ans,summ)

        if len(lis) == 0:
            break

        new = lis.pop(0)
        nlis.append(new)

        if new[0] == "0":
            zeronum += 1

        summ += new[1]

    else:

        old = nlis.pop(0)

        if old[0] == "0":
            zeronum -= 1

        summ -= old[1]

print (ans)

Submission status: Time Limit Exceeded

Solution code:

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

lis = []

nowchar = -1
num = 0

for i in range(N):

        if nowchar == S[i]:

            num += 1

        elif nowchar != -1:

            lis.append([nowchar,num])

            nowchar = S[i]
            num = 1

        else:

            nowchar = S[i]
            num = 1

lis.append([nowchar,num])


nlis = []
zeronum = 0
summ = 0
ans = 0


while True:

    if zeronum <= K:

        ans = max(ans,summ)

        if len(lis) == 0:
            break

        new = lis.pop(0)
        nlis.append(new)

        if new[0] == "0":
            zeronum += 1

        summ += new[1]

    else:

        old = nlis.pop(0)

        if old[0] == "0":
            zeronum -= 1

        summ -= old[1]

print (ans)

Submission status: Time Limit Exceeded

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


def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())

n, k = get_numbers()
s = [int(c) for c in input()]

rle = list()
target = 1
cnt = 0
for i in range(n):
    if s[i] == target:
        cnt += 1
    else:
        target = 1 - target
        rle.append(cnt)
        cnt = 1
rle.append(cnt)
if target == 0:
    rle.append(0)

length = len(rle)
ans = 0
for l in range(0, length, 2):
    r = min(l + 2 * k + 1, length)
    ans = max(sum(rle[l:r]), ans)

print(ans)

Submission status: Time Limit Exceeded

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

# Sに登場する文字1, 0を左から順にまとめる
array = []
count = 1
for i in range(N+1):
    if i == 0:
        continue
    if i == N:
        # 終了処理
        array.append([S[i-1], count])
        count = 1
        continue
    if S[i-1] == S[i]:
        # カウンターを回す
        count += 1
        continue
    if not S[i-1] == S[i]:
        # ブロック作成
        array.append([S[i-1], count])
        count = 1

maxhito = 0
hito = 0
maxcount = 0

for l in range(len(array)):
    if array[l][0] == 0:
        maxcount += 1

K = min(K, maxcount)

if array[0][0] == 0:
    start = 0
else:
    start = 1

for i in range(start, len(array) - K + 1, 2):
    if i == 0:
        hito = 0
    else:
        hito = array[i-1][1]

    for j in range(i, min(len(array), i+2*K), 1):
        hito += array[j][1]

    if hito > maxhito:
        maxhito = hito

print(maxhito)

Submission status: Time Limit Exceeded

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

Cs = []
c = 1
if N == 1:
    Cs.append(1)
else:
    for i in range(1, N):
        if Ss[i] == Ss[i - 1]:
            c += 1
        else:
            Cs.append(c)
            c = 1
        if i == N - 1:
            Cs.append(c)
            break

m = 0
for i in range(len(Cs)):
    s = 0
    C = 1 if (Ss[0] == '0' and i % 2 == 1) or (Ss[0] == '1' and i % 2 == 0) else 0
    for j in range(i, min([len(Cs), i + K * 2 + C])):
        s += Cs[j]
    if s > m:
        m = s
print(m)

Submission status: Time Limit Exceeded

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

blk_list = []
for i in range(len(s)):
  if i==0:
    blk = {'n':0, 's':s[i]}
  if i > 1 and s[i-1]!=s[i]:
    blk_list.append(blk)
    blk = {'n':0, 's':s[i]}

  blk['n'] += 1
blk_list.append(blk)

# iblkの始点を1が連続する箇所の始点とするときの数を見る

mx = 0
for i, blk in enumerate(blk_list):
  if blk['s'] == '0':
    if i == 0:
      endi = i + 2*k - 1
    else:
      continue
  if blk['s'] == '1':
    endi = i + 2*k
    
  sm = blk['n']
  for j in range(i+1, min(len(blk_list), endi+1)):
    sm += blk_list[j]['n']
      
  if sm > mx:
    mx = sm
print(mx)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
S = [int(x) for x in input()]
a=[]
tmp = 0
if S[0]==1:
    a.append(0)
for i in range(N-1):
    tmp = tmp+1
    if S[i]!=S[i+1]:
        a.append(tmp)
        tmp=0
a.append(tmp+1)
if S[N-1] == 0:
    a.append(0)
if len(a)<=K*2:
    print(sum(a))
else:
    max_l = sum(a[:2*K])
    for i in range(K,int(len(a)/2)):
        tmp = sum(a[2*(i-K+1):(i+1)*2]) + a[2*(i-K+1)-1]
        max_l = tmp if tmp>max_l else max_l
    print(max_l)

Submission status: Time Limit Exceeded

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

now = s[0]
num = 0
for c in s:
  num += 1
  if now != c:
    block.append((now,num-1))
    num = 1
    now = c
block.append((now,num))

cand = []
for i,(c,num) in enumerate(block):
  if c == '0':
    cand.append( sum([x[1] for x in block[i:i+2*k]]) )
  else:
    cand.append(sum([x[1] for x in block[i:i+2*k+1]]))

print(max(cand))

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()
S = s()

nums = []

num = 1
prev = S[0]
first_zero = prev == '0'
for i in range(1, N):
    if prev != S[i]:
        nums.append(num)
        num = 1
        prev = S[i]
    else:
        num += 1
nums.append(num)

first = 0
if first_zero:
   first = -1

res = 0
for i in range(first, len(nums), 2):
    total = sum(nums[max(i, 0):min(i+2*K+1, len(nums))])
    if total > res:
        res = total

print(res)

Submission status: Time Limit Exceeded

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

_, k = map(int, input().split())
s = list(map(int, list(input())))
# print(s)
is_count_zero = True
s0 = [0]
s1 = []
s0_ptr = 0
s1_ptr = -1
for c in s:
    if is_count_zero and c == 0:
        s0[s0_ptr] += 1
    elif not is_count_zero and c == 0:
        s0.append(1)
        s0_ptr += 1
        is_count_zero = True
    elif is_count_zero and c == 1:
        s1.append(1)
        s1_ptr += 1
        is_count_zero = False
    else: # not is_count_zero and c == 1
        s1[s1_ptr] += 1

# print(s0,s1)
# is_end_one = True if len(s0) == len(s1) else False

if k >= len(s0):
    print(sum(s0)+sum(s1))
elif k == 0:
    if s1 == []:
        print(0)
    else:
        print(max(s1))
else:
    ans = 0
    n = len(s0)-k+1
    for i in range(n):
        if i == 0 and s0[0] > 0:
            ans = sum(s0[:k]) + sum(s1[:k])
        elif i == n-1:
            ans = max(ans, sum(s0[i:]) + sum(s1[i-1:]))
        elif i != 0:
            ans = max(ans, sum(s0[i:i+k]) + sum(s1[i-1:i+k]) )
        # print(ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
cnt = 1
run = []
for i in range(1, len(S)):
    if S[i - 1] == S[i]:
        cnt += 1
    else:
        run.append(cnt)
        cnt = 1
    if i == len(S) - 1:
        run.append(cnt)
if S[0] == '0':
    run = [0] + run
if S[N - 1] == '0':
    run = run + [0]
X = [sum(run[j: j + 2 * K + 1]) for j in range(len(run) - 2 * K) if j % 2 == 0]
ans = sum(run[0: 2 * K + 1])
for j in range(2, len(run) - 2 * K):
    if j % 2 == 1:
        continue
    else:
        ans = max(ans, ans - run[j - 1] - run[j - 2] + run[j + 2 * K] + run[j + 2 * K - 1])
if len(X) == 0:
    print(N)
else:
    print(max(X))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
cnt = 1
run = []
for i in range(1, len(S)):
    if S[i - 1] == S[i]:
        cnt += 1
    else:
        run.append(cnt)
        cnt = 1
    if i == len(S) - 1:
        run.append(cnt)
if S[0] == '0':
    run = [0] + run
if S[N - 1] == '0':
    run = run + [0]
X = [sum(run[j: j + 2 * K + 1]) for j in range(len(run) - 2 * K) if j % 2 == 0]
if len(X) == 0:
    print(N)
else:
    print(max(X))

Submission status: Time Limit Exceeded

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

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



if S[0] == '1':
    width = K * 2 + 1
    flag = True
    index = 0
    ans = 0
    while flag:
        if index + width <= len(L):
            tmp = sum(L[index:index+width])
            ans = max(ans, tmp)
        else:
            tmp = sum(L[index:index+width])
            ans = max(ans, tmp)
            flag = False
        index += 2
    print(ans)

if S[0] == '0':
    width = K * 2 + 1
    flag = True
    index = 0
    ans = 0
    while flag:
        if index != 0:
            if index + width <= len(L):
                tmp = sum(L[index:index+width])
                ans = max(ans, tmp)
            else:
                tmp = sum(L[index:index+width])
                ans = max(ans, tmp)
                flag = False
            index += 2

        else:
            else_width = width - 1
            if index + width <= len(L):
                tmp = sum(L[index:index+else_width])
                ans = max(ans, tmp)
            else:
                tmp = sum(L[index:index+width])
                ans = max(ans, tmp)
                flag = False
            index += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
Sinput=input()
S=[]
for i in range(len(Sinput)):
    S.append(int(Sinput[i]))
Smax=0
human=[]
counter=1
if S[0]==0:
    human.append(0)
for i in range(1,len(S)):
    if S[i-1]!=S[i]:
        human.append(counter)
        counter=1
    else:
        counter+=1
human.append(counter)
if len(human)%2==0:
    human.append(0)

#奇数番目が０の個数、偶数番目が１の個数
if K>=len(human)//2:
    ans=len(S)
else:
    for i in range(len(human)//2-K+1):
        if sum(human[i*2:(i+K)*2+1])>=Smax:
            Smax=sum(human[i*2:(i+K)*2+1])
    ans=Smax
print(ans)

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:
'''
Sを連続する値の数のリストに変換
(ただし、左右端は必ず1が0個以上存在するとする)
S='0111010011' -> A=[0,1,3,1,1,2,2]

K=1なら、
sum(A[0:3]), sum(A[2:5]), sum(A[4:7])のmaxが答え
'''

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

# Sを0,1の区切りで分解したときのそれぞれの長さ
A = []
cur = S[0]
c = 0
for s in S[1:] + '*':
    c += 1
    if cur != s:
        cur = s
        A.append(c)
        c = 0

# 先頭、末尾が"0"のときは0を追加
if S[0] == '0':
    A = [0] + A
if S[-1] == '0':
    A = A + [0]

# Aの偶数番号インデックス(0始まり)から計算される
# 2K+1個の連続する要素の和の最大値が求める値
if len(A) <= 2 * K + 1:
    print(sum(A))
else:
    m = 0
    i = 0
    while i + 2*K+1 <= len(A):
        m = max(m, sum(A[i: i+2*K+1]))
        i += 2
    print(m)

Submission status: Time Limit Exceeded

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

ans = 1
#左端の文字を全探索
for i in range(0, N):
    #count = 切り替わりを潰しても良い回数
    if S[i] == '0':
        count = 2 * K -1
    else:
        count = 2 * K
#切り替わりを探す
    for j in range(i+1, N):
        if S[j] != S[j-1]: #1つ前と今の位置が違う時、変えて良い回数を1つ減らす
            count -= 1
        if count == 0: #これ以上変えることができない時
            ans = max(ans, j-i+1) #今までの答えとi番目からj番目までの個数=j-i+1の大きい方を答えに記録
            # print ('A', j)
        elif j == N -1 and count > 0: #最後まで探索したが、交換回数が余っている時
            ans = max(ans, j-i+1) #今までの答えとi番目からj番目までの個数=j-i+1の大きい方を答えに記録
            # print ('B')
        
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, sys.stdin.readline().split())
s = [int(string) for string in input()]

tmp = []
flag = s[0]
cnt = 1

if s[0] == 0:
    tmp.append(0)
for i in range(1, n):
    if flag == s[i]:
        cnt += 1
    else:
        tmp.append(cnt)
        cnt = 1
        flag = 1 - flag
tmp.append(cnt)
if s[-1] == 0:
    tmp.append(0)

ans = 0
for i in range(0, n, 2):
    ans_tmp = 0
    for j in range(2*k+1):
        if len(tmp) <= i+j:
            break
        ans_tmp += tmp[i+j]
    ans = max(ans, ans_tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
S=input()+"2"
if S[0]=="1":
    _list=[]
else:
    _list=[0]
cnt=1
for i in range(N):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        _list.append(cnt)
        cnt=1
C=len(_list)
K=min(C,K)
print(max([sum(_list[2*i:2*i+2*K+1]) for i in range(C-K+1)]))

Submission status: Time Limit Exceeded

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

## make 'next_lst'
## S='1100010000' --> next_lst=[2,3,1,4,1]
next_lst = []
pre_state = S[0]
cnt = 1
for i in range(1,len(S)):
  if S[i] == pre_state:
    cnt += 1
  else:
    next_lst.append(cnt)
    pre_state = S[i]
    cnt = 1
else:
  next_lst.append(cnt)
if S[0] == '0':
  next_lst = [0] + next_lst
if S[-1] == '0':
  next_lst = next_lst + [0]
#print(next_lst)

ans = 0
if len(next_lst) <= 2*K+1:
  ans = sum(next_lst)
  print(ans)
  exit()
for i in range((len(next_lst)-2*K+1)//2):
  var = sum(next_lst[2*i:2*i+(2*K+1)])
  ans = max(ans, var)
  #print(i, var, next_lst[2*i:2*i+(2*K+1)])
  
print(ans)

Submission status: Time Limit Exceeded

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

streak = 1
arr = [[],[]]
for i in range(n):
    if i== n-1:
        arr[0].append(int(s[i]))
        arr[1].append(streak)
        break
    if s[i] != s[i+1]:
        arr[0].append(int(s[i]))
        arr[1].append(streak)
        streak = 0
    streak += 1
# print(arr)

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

Submission status: Time Limit Exceeded

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

a = [0] * (2*k)

count = 1

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

if s[-1] == 1:
    a.append(count)
else:
    a.append(-count)
for _ in range(2*k):
    a.append(0)

ans = 0

for i in range(len(a)):
    if a[i] >= 0:
        temp = 0
        for j in range(-(2*k), 1):
            temp += abs(a[i+j])
        ans = max(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
s = input()
x = [0]
for si in s:
    if si == '1':
        if x[-1] >= 0:
            x[-1] += 1
        else:
            x.append(1)
    else:
        if x[-1] <= 0:
            x[-1] -= 1
        else:
            x.append(-1)
y = []
for i in range(len(x)):
    yi = 0
    ki = 0
    for j in range(i, len(x)):
        if x[j] > 0:
            yi += x[j]
        else:
            if ki >= k:
                break
            yi += -x[j]
            ki += 1
    y.append(yi)
    if ki < k:
        break
print(max(y))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
s = input()
sList = [] #連続する1の数、0の数、1の数...と格納するリスト
switch = int(s[0])
num = 1
if int(s[0]) == 0:
  sList.append(0)
if n > 1:
  for i in range(1, n):
    if int(s[i]) == switch:
      num += 1
    else:
      sList.append(num)
      num = 1
      switch = int(s[i])
sList.append(num)
if len(sList) // 2 < k: #全部ひっくり返せる
  print(n)
  sys.exit()
elif len(sList) % 2 == 0: #最後が0の数で終わっている場合、1の数で終わらせる
  sList.append(0)
  
sMax = 0
for i in range(0, (len(sList)-2*k) // 2 + 1): #リストの2k+1個の部分和のうち、最大のものが答え
  s = sum(sList[2*i:2*i+2*k+1])
  if sMax < s:
    sMax = s
    
print(sMax)

Submission status: Time Limit Exceeded

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

q = []
tmp = 0

if len(s) == 1:
    if k >= 1 or s[0] == '1':
        print(1)
    else:
        print(0)
else:
    if s[0] == '0':
        q.append(0)
    for i in range(len(s)):
        if i == 0:
            tmp += 1
        elif i != len(s)-1:
            if s[i] == s[i-1]:
                tmp += 1
            else:
                q.append(tmp)
                tmp = 1
        else:
            if s[i] == s[i-1]:
                tmp += 1
                q.append(tmp)
            else:
                q.append(tmp)
                q.append(1)
    if s[len(s)-1] == '0':
        q.append(0)

    tmp = 0
    max_k = min(math.ceil(len(q)/2), k)
    ans = []
    if max_k == math.ceil(len(q)/2):
        max_k -= 1
    for i in range(0, len(q) - 2 * max_k, 2):
        ans.append(sum(q[i:i+2*max_k+1]))

    print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N,K =map(int,input().split())
S =input()
lis = [[],[]]
if S[0]=="0":
    lis[1].append(0)
st = []
j = S[0]
su = 0
for i in S:
    if i ==j:
        su += 1
    else:
        lis[int(j)].append(su)
        st.append(j)
        j = i
        su = 1
lis[int(j)].append(su)
st.append(j)
if j=="0":
    lis[1].append(0)
if len(lis[0])<=K:
    print(N)
else:
    ans = 0
    for i in range(len(lis[0])+1-K):    
        foo = sum(lis[0][i:i+K]) + sum(lis[1][i:i+K+1])
        if ans < foo:
            ans = foo
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
S = list(input())
cnt = 1
k = {}
if S[0] == "0":
    k[cnt] = [0]
    cnt += 1


flg = False
for i in range(N):
    if S[i] == '1':
        if cnt not in k.keys() :
            k[cnt] = []
        k[cnt].append(i)
        flg = True
    else:
        if flg == True:
            flg = False
            cnt += 1

if S[-1] == '0':
    k[cnt] = [N-1]


if '0' not in S:
    print(len(S))
    exit()
if N == 1:
    print(1)
    exit()

if cnt - K + 1 < 0:
    print(len(S))
    exit()

ans = 0
for i in range(1,cnt - K+1):
    ans = max(ans , k[i+K][-1]-k[i][0] + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, K = LI()
S = SI().strip()

searching = 1
count = [0]
head = 0
for i in range(N):
    if int(S[i]) == searching:
        count[head] += 1
    else:
        searching = (searching+1)%2
        head += 1
        count.append(1)
if len(count)//2 <= K:
    print(N)
    sys.exit()

count.append(0)

max_length = 0
for k in range(N):
    if 2*k+2*K+1 > N: break
    max_length = max(sum(count[2*k:2*k+2*K+1]), max_length)
print(max_length)

Submission status: Time Limit Exceeded

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

arr.append(c)
if b!='1':
  arr.append(0)

a = arr[0] if len(arr)==1 else max(sum(arr[2*i:2*i+2*k+1]) for i in range(len(arr)//2))
print(a)

Submission status: Time Limit Exceeded

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

# print(n, k, s)

prevcCt = 0 # 前に連続逆立ちの数
nextCnt = 0 # 後ろに連続逆立ちの数

# "00010" ⇒ [-3, 1, -1]のような配列に変換

val = 0
vals = []
for i in range(len(s)):
	if s[i] == "0":
		val -= 1
	else:
		val += 1

	#print(i, val, s[i], s[i+1])
	# print(i,len(s))
	if i == len(s) - 1 or s[i] != s[i+1]:
		vals.append(val)
		val = 0

#print(vals)

#操作しやすいようにマイナス要素が偶数になるように先頭に0を追加
if vals[0] < 0:
	vals.insert(0,0)

vals.append(0)
vals.append(0)

#print(vals)

vals = list(map(abs, vals))
#print(vals)


# K回操作できるということは連続した2k+1個の要素の最大値を求めればよい
max = 0

loopCnt = len(vals) - k
if  loopCnt < 1:
	loopCnt = 1

for i in range(loopCnt):
	#print(i, len(vals), k)
	# 偶数の時だけ判定
	if i%2 == 0:
		# print(vals[i:i + 2*k + 1])

		sumVal = sum(vals[i:i + 2*k + 1])
		# for e in vals[i:i + 2*k + 1]:
		# 	sumVal += abs(e)
		if sumVal > max:
			max = sumVal

print(max)