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: Wrong Answer

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

now = 1
cnt = 0
li = []

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        li.append(cnt)
        now = 1 - now
        cnt = 1

if len(li)%2 == 0:
    li.append(cnt)

    

left = 0
right = 2*k + 1
length = sum(li[left:right])
ans = length

for i in range(2, len(li), 2):
    
    length -= sum(li[left:left+2])
    
    left = i
    right = i + 2*k + 1
    
    length += sum(li[right-2:right])

    ans = max(ans, length)
            
print(ans)

Submission status: Wrong Answer

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


#n, k = 5, 3
#s = "00010"

m = 0
cur_s = cur_e = 0

while True:
  print((cur_s, cur_e, k))
  while cur_e < n and s[cur_e] == '1':
    cur_e+=1
  
  if k <= 0 or cur_e >= n:
    wm = cur_e - cur_s
    if wm > m:
      m = wm
      
    if cur_e >= n:
      break
 
    while cur_s < n and s[cur_s] == '1':
      cur_s+=1
    while cur_s < n and s[cur_s] == '0':
      cur_s+=1
    k+=1

  if k > 0:
    while cur_e < n and s[cur_e] == '0':
      cur_e+=1
    k-=1
    
print(m)

Submission status: Wrong Answer

Solution code:
import copy

def main():
  a, reverse_cnt = map(int, input().split(" "))
  h_list = input()
  h_list_henkei = []
  first_time_state = int(h_list[0])
  tmpstate = first_time_state
  tmpcnt = 0
  for h in h_list:
    if int(h) == tmpstate:
      tmpcnt = tmpcnt + 1
    else:
      h_list_henkei.append(tmpcnt)
      tmpstate = int(h)
      tmpcnt = 1
  h_list_henkei.append(tmpcnt)
  del h_list
  max_sum_length_first_is_one = 1 + reverse_cnt * 2
  tmp_cnt = 0
  tmp_list = h_list_henkei[0:max_sum_length_first_is_one]
  tmp_list.reverse()
  max_cnt = 0
  if first_time_state == 0:
    max_cnt = sum(tmp_list[1:max_sum_length_first_is_one])
  else:
    max_cnt = sum(tmp_list)
  for i in range(max_sum_length_first_is_one,len(h_list_henkei)):
    tmp_list.pop()
    tmp_list.insert(0,h_list_henkei[i])
    if (i - first_time_state + 1) % 2 == 0:
      if max_cnt < sum(tmp_list):
        max_cnt = sum(tmp_list)
  print (max_cnt)  

main()

Submission status: Wrong Answer

Solution code:
N, k = map(int, input().split())
S = input()
ans = []
state = S[0]
for i in range(1, len(S)):
  if S[i] != state:
    ans.append(i)
    state = S[i]
ans.append(len(S))

if 2*k-1 < len(ans):
  if S[0] == '0':
    temp = ans[2*k-1]   
    for i in range(1, len(ans)-2*k-1):
      if i%2 == '0':
        dif = ans[i+2*k] - ans[i]
      else:
        dif = ans[i+2*k+1] - ans[i]
      if dif > temp:
        temp = dif
  else:
    temp = ans[2*k]
    for i in range(1, len(ans)-2*k-1):
      if i%2 == '1':
        dif = ans[i+2*k] - ans[i]
      else:
        dif = ans[i+2*k+1] - ans[i]
      if dif > temp:
        temp = dif
else:
  temp = ans[0]
print(temp)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
S = input()
lstS = list(S)
block = [0]

cnt = 1
for i in range(len(S)):
    if S[i:i+1] == S[i+1:i+2]:
        cnt += 1
    else:
        block.append(cnt)
        cnt = 1
block.append(0)

acc = [0, 0]
for i in range(1, len(block)):
    wa = acc[-1]+block[i]
    acc.append(wa)

if S[0] == '0':
    start = 0
else:
    start = 1
end = len(acc) - (2*K+1)

max = 0
for i in range(start, end, 2):
    if max < acc[i+(2*K+1)] - acc[i]:
        max = acc[i+(2*K+1)] - acc[i]

if len(S) == 1:
    if K == 0 and S =='0':
        max = 0
    else:
        max = 1

print(max)

Submission status: Wrong Answer

Solution code:
N, k = map(int, input().split())
S = input()
ans = []
state = S[0]
for i in range(1, len(S)):
  if S[i] != state:
    ans.append(i)
    state = S[i]
ans.append(len(S))

if 2*k-1 < len(ans):
  if S[0] == '0':
    temp = ans[2*k]   
    for i in range(1, len(ans)-2*k-1):
      if i%2 == '0':
        dif = ans[i+2*k] - ans[i]
      else:
        dif = ans[i+2*k+1] - ans[i]
      if dif > temp:
        temp = dif
  else:
    temp = ans[2*k+1]
    for i in range(1, len(ans)-2*k-1):
      if i%2 == '1':
        dif = ans[i+2*k] - ans[i]
      else:
        dif = ans[i+2*k+1] - ans[i]
      if dif > temp:
        temp = dif
else:
  temp = ans[0]
print(temp)

Submission status: Wrong Answer

Solution code:
import sys

N, K = [int(x) for x in input().split()] # N:Sの長さ K:操作を行える回数の最大値
S = [int(x) for x in list(input())] # S:0と1から成る列
index = [0] # index:Sにおいて0と1が切り替わる部分の添字を集めたリスト
length = [0] # length:1が連続して並んでいる長さの最大値の候補を集めたリスト
zeros = 0 # zeros:Sにおいて0が連続して並んでいる箇所がいくつあるか

for i in range(0, len(S) - 1): # indexの要素を取得
    if S[i] != S[i + 1]: # 0と1の変わり目を探索
        index.append(i + 1) 

if S[0] == 0: # Sが0から始まる場合
    
    for i in range(len(index)): # zerosの値を取得
        if len(index) % 2 == 0: # indexの長さが偶数である場合
            zeros = int(len(index) / 2)
        else: # indexの長さが奇数である場合
            zeros = int((len(index) + 1) / 2) 
            
    for i in range(len(index)): # max(length)の初期値を取得
        if S[len(S) - 1] == 0: # Sが0で終わっている場合
            if i % 2 == 1:
                length.append(index[i + 1] - index[i])
        else: # Sが1で終わっている場合
            if (i % 2 ==1 and (i + 1) < len(index)):
                length.append(index[i + 1] - index[i])
            elif (i % 2 ==1 and (i + 1) == len(index)): # 最後の1の連続を処理
                length.append((len(S) - 1) - index[i] + 1)

    for i in range(len(index)): # Sのindex[i]番目を左端としたときの1の連続回数の最大値をそれぞれ求める
        if K >= zeros: # Kがzeros以上なら0の連続を全て1に置き換えて終了
            print(len(S))
            sys.exit()
        
        elif i + (2 * K) <= (len(index) - 1): # 添字が飛び出ないように注意（飛び出るようなやつはそもそも最大値の候補にならない）
            if i % 2 == 0: # 左端が0の場合
                if (i + (2 * K) - 1) < len(index) - 1:
                    length.append(index[(i + (2 * K) - 1) + 1] - index[i])
                elif (i + (2 * K) - 1) == len(index) - 1:
                    length.append((len(S) - 1) - index[i] + 1)
            else: # 左端が1の場合
                if i + (2 * K) < (len(index) - 1):
                    length.append(index[i + (2 * K) + 1] - index[i])
                elif i + (2 * K) == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)
                
    print(max(length))
    sys.exit()

else: # Sが1から始まる場合
    
    for i in range(len(index)): # zerosの値を取得
        if len(index) % 2 == 0: # indexの長さが偶数である場合
            zeros = int(len(index) / 2)
        else: # indexの長さが奇数である場合
            zeros = int((len(index) - 1) / 2) 
            
    for i in range(len(index)): # max(length)の初期値を取得
        if S[len(S) - 1] == 0: # Sが0で終わっている場合
            if i % 2 == 0:
                length.append(index[i + 1] - index[i])
        else: # Sが1で終わっている場合
            if (i % 2 ==0 and (i + 1) < len(index)):
                length.append(index[i + 1] - index[i])
            elif (i % 2 ==0 and (i + 1) == len(index)): # 最後の1の連続を処理
                length.append((len(S) - 1) - index[i] + 1)

    for i in range(len(index)): # Sのindex[i]番目を左端としたときの1の連続回数の最大値をそれぞれ求める
        if K >= zeros: # Kがzeros以上なら0の連続を全て1に置き換えて終了
            print(len(S))
            sys.exit()
        
        elif i + (2 * K) <= (len(index) - 1): # 添字が飛び出ないように注意（飛び出るようなやつはそもそも最大値の候補にならない）
            if i % 2 == 0: # 左端が1の場合
                if i + (2 * K) < (len(index) - 1):
                    length.append(index[i + (2 * K) + 1] - index[i])
                elif i + (2 * K) == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)
                
            else: # 左端が0の場合
                if i + (2 * K) - 1 < (len(index) - 1):
                    length.append(index[(i + (2 * K) - 1) + 1] - index[i])
                elif i + (2 * K) - 1 == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)

                
    print(max(length))
    sys.exit()

Submission status: Wrong Answer

Solution code:
N, k = map(int, input().split())
S = input()
ans = []
state = S[0]
for i in range(1, len(S)):
  if S[i] != state:
    ans.append(i)
    state = S[i]
ans.append(len(S))
if 2*k-1 < len(ans):
  temp = ans[2*k-1]
  for i in range(1, len(ans)-2*k-1):
    dif = ans[i+2*k+1] - ans[i]
    if dif > temp:
      temp = dif
else:
  temp = ans[0]
print(temp)

Submission status: Wrong Answer

Solution code:
import sys

N, K = [int(x) for x in input().split()] # N:Sの長さ K:操作を行える回数の最大値
S = [int(x) for x in list(input())] # S:0と1から成る列
index = [0] # index:Sにおいて0と1が切り替わる部分の添字を集めたリスト
length = [0] # length:1が連続して並んでいる長さの最大値の候補を集めたリスト
zeros = 0 # zeros:Sにおいて0が連続して並んでいる箇所がいくつあるか

for i in range(0, len(S) - 1): # indexの要素を取得
    if S[i] != S[i + 1]: # 0と1の変わり目を探索
        index.append(i + 1) 

if S[0] == 0: # Sが0から始まる場合
    
    for i in range(len(index)): # zerosの値を取得
        if len(index) % 2 == 0: # indexの長さが偶数である場合
            zeros = int(len(index) / 2)
        else: # indexの長さが奇数である場合
            zeros = int((len(index) + 1) / 2) 
            
    for i in range(len(index)): # max(length)の初期値を取得
        if S[len(S) - 1] == 0: # Sが0で終わっている場合
            if i % 2 == 1:
                length.append(index[i + 1] - index[i])
        else: # Sが1で終わっている場合
            if (i % 2 ==1 and (i + 1) < len(index)):
                length.append(index[i + 1] - index[i])
            elif (i % 2 ==1 and (i + 1) == len(index)): # 最後の1の連続を処理
                length.append((len(S) - 1) - index[i] + 1)

    for i in range(len(index)): # Sのindex[i]番目を左端としたときの1の連続回数の最大値をそれぞれ求める
        if K >= zeros: # Kがzeros以上なら0の連続を全て1に置き換えて終了
            print(len(S))
            sys.exit()
        
        elif i + (2 * K) <= (len(index) - 1): # 添字が飛び出ないように注意（飛び出るようなやつはそもそも最大値の候補にならない）
            if i % 2 == 0: # 左端が0の場合
                length.append(index[(i + (2 * K) - 1) + 1] - index[i])
            else: # 左端が1の場合
                if i + (2 * K) < (len(index) - 1):
                    length.append(index[i + (2 * K) + 1] - index[i])
                elif i + (2 * K) == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)
                
    print(max(length))
    sys.exit()

else: # Sが1から始まる場合
    
    for i in range(len(index)): # zerosの値を取得
        if len(index) % 2 == 0: # indexの長さが偶数である場合
            zeros = int(len(index) / 2)
        else: # indexの長さが奇数である場合
            zeros = int((len(index) - 1) / 2) 
            
    for i in range(len(index)): # max(length)の初期値を取得
        if S[len(S) - 1] == 0: # Sが0で終わっている場合
            if i % 2 == 0:
                length.append(index[i + 1] - index[i])
        else: # Sが1で終わっている場合
            if (i % 2 ==0 and (i + 1) < len(index)):
                length.append(index[i + 1] - index[i])
            elif (i % 2 ==0 and (i + 1) == len(index)): # 最後の1の連続を処理
                length.append((len(S) - 1) - index[i] + 1)

    for i in range(len(index)): # Sのindex[i]番目を左端としたときの1の連続回数の最大値をそれぞれ求める
        if K >= zeros: # Kがzeros以上なら0の連続を全て1に置き換えて終了
            print(len(S))
            sys.exit()
        
        elif i + (2 * K) <= (len(index) - 1): # 添字が飛び出ないように注意（飛び出るようなやつはそもそも最大値の候補にならない）
            if i % 2 == 0: # 左端が1の場合
                if i + (2 * K) < (len(index) - 1):
                    length.append(index[i + (2 * K) + 1] - index[i])
                elif i + (2 * K) == (len(index) - 1):
                    length.append((len(S) - 1) - index[i] + 1)
                
            else: # 左端が0の場合
                length.append(index[(i + (2 * K) - 1) + 1] - index[i])

                
    print(max(length))
    sys.exit()

Submission status: Wrong Answer

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

now = 1
cnt = 0
li = []

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        li.append(cnt)
        now = 1 - now
        cnt = 1
        
if len(li)%2 == 0:
    li.append(cnt)


left = 0
right = 2*k + 1
length = sum(li[left:right])
ans = length

for i in range(0, len(li), 2):

    length -= sum(li[left:left+2])
    length += sum(li[right+1:right+3])

    left += 2
    right += 2

    ans = max(ans, length)
            
print(ans)

Submission status: Wrong Answer

Solution code:
N, k = map(int, input().split())
s = input()
l, accum = len(s), []
zeros, ones = [], []
if s[0] == '0':
    ones = [0] 
i = 0 
while i < l:
    ch = s[i]
    if ch == '0':
        count = 0 
        while i < l and s[i] == ch: 
            count += 1
            i += 1
        zeros.append(count)
    elif ch == '1':
        count = 0 
        while i < l and s[i] == ch: 
            count += 1
            i += 1
        ones.append(count)

mx = sum(zeros[:k+1]) + sum(ones[:k])
for i in range(len(zeros)-k+1):                                                                                
    mx = max(sum(zeros[i:k+i]) + sum(ones[i:k+i+1]), mx) 
print(mx)

Submission status: Wrong Answer

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

one_list = []
zero_list = []

cur_char = S[0]
char_num = 0
for i in range(N):
    if S[i] == cur_char:
        char_num += 1
    else:
        if cur_char == '0':
            zero_list.append(char_num)
        else:
            one_list.append(char_num)
        cur_char = S[i]
        char_num = 1
if cur_char == '0':
    zero_list.append(char_num)
else:
    one_list.append(char_num)

len_zero_list = len(zero_list)
len_one_list = len(one_list)
# print(len_one_list)
# print(len_zero_list)

cont_length_list = []

if K >= len(zero_list):
    ans = N
else:
    if S[0] == '1':
        tmp_length = sum(one_list[:K+1])+sum(zero_list[:K])
        cont_length_list.append(tmp_length)
        for i in range(min(len_zero_list,len_one_list)-K):
            if K+1+i<len_one_list:
                tmp_length += one_list[K+1+i]+zero_list[K+i]
            else:
                tmp_length += zero_list[K+i]
            tmp_length -= one_list[i]+zero_list[i]
            cont_length_list.append(tmp_length)
        # print(cont_length_list)
    else:
        tmp_length = sum(one_list[:K])+sum(zero_list[:K])
        cont_length_list.append(tmp_length)
        if K == len_one_list:
            tmp_length+=zero_list[K]
            tmp_length -= zero_list[0]
        if K < len_zero_list-1:
            tmp_length += zero_list[K]+one_list[K]
            tmp_length -= zero_list[0]
            cont_length_list.append(tmp_length)
            for i in range(1, len_zero_list-K):
                if K+i<len_one_list and K+i < len_zero_list:
                    tmp_length += one_list[K+i]+zero_list[K+i]
                else:
                    tmp_length += zero_list[K+i]
                tmp_length -= one_list[i-1]+zero_list[i]
                cont_length_list.append(tmp_length)
        # print(cont_length_list)
    # print(cont_length_list)
    ans = max(cont_length_list)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
lst=[1]
for i in range(1,n):
    if s[i]!=s[i-1]:
        lst.append(1)
    else:
        lst[-1]=lst[-1]+1
L=[0]
for i in lst:
  L.append(L[-1]+i)
l=len(L)
ans=0
if s=='1'*n:
    ans=n
else:
    if s[0]=='1':
        if l%2==0:
            for j in range(1,k+1):
                p=2*j
                q=(l-p)//2
                for i in range(q):
                    ans=max(ans,L[2*i+p+1]-L[2*i])
                    if ans==n:
                        break
        else:
            L.append(L[-1])
            for j in range(k):
                p=2*j
                q=(l-p+1)//2
                for i in range(1,k+1):
                    ans=max(ans,L[2*i+p+1]-L[2*i])
                    if ans==n:
                        break
    else:
        L.insert(0,0)
        if l%2==1:
            L.insert(0,0)
            for j in range(1,k+1):
                p=2*j
                q=(l-p+1)//2
                for i in range(q):
                    ans=max(ans,L[2*i+p+1]-L[2*i])
                    if ans==n:
                         break
        else:
            L.append(L[-1])
            for j in range(1,k+1):
                p=2*j
                q=(l-p+2)//2
                for i in range(q):
                    ans=max(ans,L[2*i+p+1]-L[2*i])
                    if ans==n:
                        break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
lst=[1]
for i in range(1,n):
    if s[i]!=s[i-1]:
        lst.append(1)
    else:
        lst[-1]=lst[-1]+1
p=2*k
L=[0]
for i in lst:
  L.append(L[-1]+i)
l=len(L)
ans=0
if s=='1'*n:
    ans=n
else:
    if s[0]=='1':
        if l%2==0:
            q=(l-p)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
        else:
            L.append(L[-1])
            q=(l-p+1)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
    else:
        L.insert(0,0)
        if l%2==1:
            L.insert(0,0)
            q=(l-p+1)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
        else:
            L.append(L[-1])
            q=(l-p+2)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
print(ans)

Submission status: Wrong Answer

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = '1' + read()
sum_0 = [0]

for s_new, s_next in zip(S[:-2], S[1:-1]):
    # print(s_new, s_next)
    if s_new == '1' and s_next == '0':
        sum_0.append(sum_0[-1] + 1)
    else:
        sum_0.append(sum_0[-1])

S = S[1:-1]
# print(sum_0)

left = 0  # 左端初期値
ans = 1  # 解初期値
right = 0

# right-leftが答え
# sum_0[right]-sum0[left]がKを超えたらleftを進める
# print(sum_0)
# しゃくとり法で溶けそうでは？
for left in range(N-1):
    while (True):
        if right == N - 1:
            break
        right += 1
        if sum_0[right + 1] - sum_0[left] > K:
            right -= 1
            break

        # print(left, right, sum_0[right + 1] - sum_0[left])

    # print(left, right)
    ans = max(ans, right - left+1)  # 大きい方に更新
    # print(ans)

print(ans)

Submission status: Wrong Answer

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = '1' + read()
sum_0 = [0]

for s_new, s_next in zip(S[:-2], S[1:-1]):
    # print(s_new, s_next)
    if s_new == '1' and s_next == '0':
        sum_0.append(sum_0[-1] + 1)
    else:
        sum_0.append(sum_0[-1])

S = S[1:-1]
# print(sum_0)

left = 0  # 左端初期値
ans = 1  # 解初期値
right = 1

# right-leftが答え
# sum_0[right]-sum0[left]がKを超えたらleftを進める
# print(sum_0)
# しゃくとり法で溶けそうでは？
for left in range(N-1):
    while (True):
        if right == N - 1:
            break
        right += 1
        if sum_0[right + 1] - sum_0[left] > K:
            right -= 1
            break

        # print(left, right, sum_0[right + 1] - sum_0[left])

    # print(left, right)
    ans = max(ans, right - left+1)  # 大きい方に更新
    # print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
lst=[1]
for i in range(1,n):
    if s[i]!=s[i-1]:
        lst.append(1)
    else:
        lst[-1]=lst[-1]+1
p=2*k
L=[0]
for i in lst:
  L.append(L[-1]+i)
l=len(L)
ans=0
if s=='1'*n:
    ans=n
else:
    if s[0]=='1':
        if l%2==0:
            q=(l-p)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
        else:
            L.append(0)
            q=(l-p+1)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
    else:
        L.insert(0,0)
        if l%2==1:
            L.insert(0,0)
            q=(l-p+1)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
        else:
            L.append(0)
            q=(l-p+2)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
print(ans)

Submission status: Wrong Answer

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = '1' + read()
sum_0 = [0]

for s_new, s_next in zip(S[:-2], S[1:-1]):
    # print(s_new, s_next)
    if s_new == '1' and s_next == '0':
        sum_0.append(sum_0[-1] + 1)
    else:
        sum_0.append(sum_0[-1])

S = S[1:-1]
# print(sum_0)

left = 0  # 左端初期値
ans = 1  # 解初期値
right = 1

# right-leftが答え
# sum_0[right]-sum0[left]がKを超えたらleftを進める
# print(sum_0)
# しゃくとり法で溶けそうでは？
for left in range(N-1):
    right = left
    while (True):
        right += 1
        if sum_0[right + 1] - sum_0[left] > K:
            right -= 1
            break
        if right == N - 1:
            break
        # print(left, right, sum_0[right + 1] - sum_0[left])

    # print(left, right)
    ans = max(ans, right - left+1)  # 大きい方に更新
    # print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
"""
map(int,input().split())

"""
N,K = map(int,input().split())
S = input()
s = []
for i in range(0,len(S)):
    s.append(S[i])


Nums = []
now = 1
cnt = 0
for i in range(0,N):
    if(s[i] == str(now)):
        cnt+=1
    else:
        Nums.append(cnt)
        now = 1-now
        cnt = 1

if cnt!=0:
    Nums.append(cnt)

if len(Nums)%2 == 0:
    Nums.append(0)

Add = 2*K + 1
ans = 0
W = []

wsm = 0
for i in range(0,len(Nums)):
    wsm = Nums[i] + wsm
    W.append(wsm)

W.append(wsm)
W.append(wsm)

for i in range(0,len(Nums),2):
    tmp = 0
    left = i
    if left == 0:
        left = 1
    right = min(i + Add , len(Nums))
    tmp = W[right-1] - W[left-1]
    #print(tmp,left,right)
    ans = max(tmp,ans)
if  N == 1:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

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

now = 1
cnt = 0
li = []

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        li.append(cnt)
        now = 1 - now
        cnt = 1
        
if len(li)%2 == 0:
    li.append(cnt)

ans = -1
for i in range(n):
    left = 2*i
    right = 2*i + 2*k + 1
    length = sum(li[left:right])
    ans = max(ans, length)
    
    if right >= len(li):
        break

print(ans)

Submission status: Wrong Answer

Solution code:
"""
map(int,input().split())

"""
N,K = map(int,input().split())
S = input()
s = []
for i in range(0,len(S)):
    s.append(S[i])


Nums = []
now = 1
cnt = 0
for i in range(0,N):
    if(s[i] == str(now)):
        cnt+=1
    else:
        Nums.append(cnt)
        now = 1-now
        cnt = 1

if cnt!=0:
    Nums.append(cnt)

if len(Nums)%2 == 0:
    Nums.append(0)

Add = 2*K + 1
ans = 0
W = []

wsm = 0
for i in range(0,len(Nums)):
    wsm = Nums[i] + wsm
    W.append(wsm)

W.append(wsm)
W.append(wsm)

for i in range(0,len(Nums),2):
    tmp = 0
    left = i
    right = min(i + Add , len(Nums))

    tmp = W[right] - W[left-1]
    ans = max(tmp,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
lst=[1]
for i in range(1,n):
    if s[i]!=s[i-1]:
        lst.append(1)
    else:
        lst[-1]=lst[-1]+1
p=2*k
L=[0]
for i in lst:
  L.append(L[-1]+i)
l=len(L)
ans=0
if s=='1'*n:
    ans=n
else:
    if s[0]=='1':
        if l%2==0:
            q=(l-p)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
        else:
            L.append(0)
            q=(l-p+1)//2
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
    else:
        L.insert(0,0)
        if (l+1)%2==1:
            L.append(0)
            q=(l-p)//2+1
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
        else:
            q=(l-p)//2+1
            for i in range(q):
                ans=max(ans,L[2*i+p+1]-L[2*i])
print(ans)

Submission status: Wrong Answer

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

dic = {'0': '1', '1':'0'}


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

cum_sum = [0] * (len(L) + 1)

for j in range(len(L)):
    cum_sum[j + 1] = cum_sum[j] + L[j]
    
ans = 0

if S[0] == '0':
    for k in range(len(L) + 1):
        if k + (2 * K) <= len(L):
            saksadati = cum_sum[k + (2 * K)] - cum_sum[k]
            ans = max(ans, saksadati)

else:
    for k in range(len(L) + 1):
        if k + (2 * K) + 1 <= len(L):
            saksadati = cum_sum[k + (2 * K) + 1] - cum_sum[k] 
            ans = max(ans, saksadati)
        else:
            ans = 1
            break
            
print(ans)