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 = 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)

    print(sl)
    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):
                print(st, ed, sl[st:ed])
                print(i, sl[st:ed], sum(sl[st:ed]))
                cl.append(sum(sl[st:ed]))
        else:  # kが偶数の時、1の箇所（すなわちiが奇数の箇所）を中心に反転
            if (i % 2 == 1):
                print(st, ed, sl[st:ed])
                print(i, sl[st:ed], sum(sl[st:ed]))
                cl.append(sum(sl[st:ed]))

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

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = np.array(
  [int(i) for i in input().split()])
s = input()

ones = [len(x) for x in 
   s.replace('0',  ' ').split()]
zeros = [len(x) for x in 
   s.replace('1',  ' ').split()]

# 1から始まり1で終わると仮定
if s[0]=='0':
  ones = [0] + ones
if s[-1]=='0':
  ones = ones + [0]
  
if k>=len(zeros):
  print(n)
  
else:
  for _ in range(k):
    if len(zeros)==0:
      break

    # 当該0を潰すことで得られる効果
    zeros_new = [
      zeros[i]+ones[i]+ones[i+1]
      for i in range(len(zeros))]

    # 一番大きいものを消す
    idx_del = np.argmax(zeros_new)

    # 更新
    del ones[idx_del:idx_del+2]
    del zeros[idx_del]
    ones.insert(
      idx_del, zeros_new[idx_del])

    if len(zeros)==0:
      break

  print(np.max(ones))

Submission status: Wrong Answer

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

S = input()
para = [0]
for i, s in enumerate(S):
    if i == 0:
        para.append(1)
    else:
        if S[i] == S[i-1]:
            para[-1] += 1
        else:
            para.append(1+para[-1])


i = 0

tmpmax = 0

if S[0] == '1':
    if i + 2*k + 1 >= len(para) - 1:
        print(n)

    while i + 2*k + 1 <= len(para) - 1:
        j = i + 2*k + 1
        if para[j] - para[i-1] > tmpmax:
            tmpmax = para[j] - para[i]

        i += 2
else:
    if i + 2*k >= len(para) - 1:
        print(n)

    while i + 2*k <= len(para) - 1:
        j = i + 2*k
        if i == 0:
            if para[j] - para[i] > tmpmax:
                tmpmax = para[j] - para[i]
        else:
            if para[j] - para[i-1] > tmpmax:
                tmpmax = para[j] - para[i-1]

        i += 2
print(tmpmax)

Submission status: Wrong Answer

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

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

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

ss = array_count(s)

if ss[0][0] == 0:
    ss = [[1,0]] + ss

if ss[-1][0] == 1:
    ss.append([0,0])

ss_sum = []
temp = 0
for i in range(len(ss)):
    temp += ss[i][1]
    ss_sum.append(temp)

ans = -1
for i in range(len(ss_sum)):
    temp = 0
    if i % 2 == 0:
        if i + k * 2 < len(ss_sum):
            temp = ss_sum[i+k*2] - ss_sum[i]
    else:
        if i + k * 2 + 1 < len(ss_sum):
            temp = ss_sum[i+k*2+1] -  ss_sum[i]
    ans = max(temp,ans)

if ans == -1:
    ans = ss_sum[-1]

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
s = "1"+input().strip()+"1"
i = 0
dp = []
while i < len(s):
    l = i
    while i < len(s) and s[i] == '1':
        i += 1
    if l < i:
        dp.append([l, i-1])
    while i < len(s) and s[i] == '0':
        i += 1


if len(dp) <= K:
    print(N)
else:
    ans = 0
    for i in range(0, len(dp)-K):
        t = dp[i+K][1]-dp[i][0]
        if t > ans:
            ans = t
    print(ans)

Submission status: Wrong Answer

Solution code:

def get_input():
    N,K = [int(_) for _ in input().split()]
    S = [int(_) for _  in list(input())]
    return N,K,S

def solve(N,K,S):
    length = len(S)
    array = count_array(S)
    start_char = S[0]
    ans = find_max(array,K,start_char)
    return ans

def find_max(array,K,start_char):
    if start_char ==0 and len(array) <= 2 * K:
        return sum(array)
    elif start_char == 1 and len(array) <=2 * K+1 :
        return sum(array)
    else:
        if start_char == 0:
            start,end = 1,2*K+2
        else:
            start,end = 0,2*K+1
        idx = 0
                    
        current_sum = sum(array[start:end])
        ret = [current_sum]
        if start_char == 0:
            ret.append(sum(array[0:2*K]))
        while(1):
            start+=2
            end+=2
            if end > len(array):
                break
            current_sum = current_sum- sum(array[start-2:start]) + sum(array[end-2:end])
            ret.append(current_sum)
    return max(ret)
            

def count_array(S):
    array = []
    cur_char = S[0]
    cur_val = 1
    for char in S[1:]:
        if cur_char != char:
            array.append(cur_val)
            cur_char = char
            cur_val = 1
        else:
            cur_val+=1
    array.append(cur_val)

    return array


if __name__ == "__main__":
    N,K,S = get_input()
    ans = solve(N,K,S)
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

l = []

if s.count("1")==N:
    print(N)
else:
    cnt = 1
    for i in range(N):
        if s[i] == "1":
            cnt += 1
        else:
            if i != N-1:
                if s[i+1]=="0":
                    l.append([cnt,0])
                else:
                    l.append([cnt,-1])
            else:
                l.append([cnt,-1])
            cnt = 1
    else:
        l.append([cnt,-1])
    tmp = 0
    ccnt = 0
    nn = 0
    ans = 0
    while True:
        for i in range(tmp,len(l)-1):
            if l[i][1]==-1:
                ccnt += 1
                if ccnt == 1:
                    tmp = i
            nn += l[i][0]
            if ccnt == K:
                nn += l[i+1][0] -1
                ans = max(ans,nn)
                nn = 0
                ccnt = 0
        else:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
List=[]
i=1
j=1
while i<n:
  if s[i-1]==s[i]:
    j+=1
    i+=1
  else:
    List.append(j)
    i+=1
    j=1
List.append(j)
if s[0]=="0":
  List.insert(0,0)
ans=max(List)
rg=2*k+1
for i in range(0,len(List)-rg+1,2):
  ans=max(ans,sum(List[i:i+rg]))
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
S = input()
if N==1:
  print(1)
  exit()
a = []
b = []
bef = S[0]
cou = 0
for i in range(N):
  if bef==S[i]:
    cou+=1
  else:
    if bef=='0':
      a.append(cou)
    else:
      b.append(cou)
    bef=S[i]
    cou = 1
  if i==N-1:
    if bef=='0':
      a.append(cou)
    else:
      b.append(cou)
if len(a)==0 or len(b)==0:
  print(N)
  exit()
jud = S[0]+S[N-1]
if jud=='00':
  b =[0]+b+[0]
elif jud=='01':
  b = [0]+b
elif jud=='10':
  b = b+[0]
max_cou = 0
for i in range(len(a)-K+1):
  cou = sum(a[i:i+K])+sum(b[i:i+K+1])
  max_cou = max(cou,max_cou)
print(max_cou)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
S= [i for i in input()]
list_1 = []
max = 0
if S[0] == '0':
	list_1.append(0)
for i in range(N-1):
	if S[i] == '1' and S[i+1] == '0':
		list_1.append(i)
if S[N-1] == '0':
	list_1.append(N-1)
if K>=len(list_1) or '0' not in S:
	print(len(S))
else:
	for i in range(len(list_1)-K):
		if list_1[i+K]-list_1[i]+1 > max:
			max = list_1[i+K]-list_1[i]+1
	print(max)

Submission status: Wrong Answer

Solution code:
import sys
n,k = list(map(int, input().split()))
s = input()
s = s[:n]
un = False
ww = [w for w in range(n)]
ww.reverse()

for gaha in range(k-1):
	for _ in ww:
		a = "0" * _
		if not un and a != "0":
			if a in s:
				un = True
				s = s.replace(a,"1"*_,1)
		if un:
			break
				
	un = False


ww = [w for w in range(n)]
ww.reverse()

			
for da in ww:
	r = "1" * da
	if r in s:
		print(len(r))
		sys.exit()

Submission status: Wrong Answer

Solution code:
import numpy as np

N,K = map(int, input().split())
s = list(input())
sl = []
S = np.array(s, dtype=np.int64)

S = np.append(S, 1 - S[-1])

#print(S)
a = 1
for i in range(1,len(s)+1):
    
    if S[i] != S[i-1]:
        
        sl.append(a)
        #print(i,a)
        a = 1
    else :
        a += 1

slm = [] 
for i in range (len(sl) - (2*K)):
    #print(i,K)
    #print(sl[0:2])
    if i == 0:
        slm.append(sum(sl[i:i+2*K]))
    else:
        slm.append(sum(sl[i:i+2*K+1]))
if len(sl) - (2*K) > 0:
    print(max(slm))
else:
    print(max(sl))

Submission status: Wrong Answer

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)):
    if row[i][1] == 1:
        ans.append(sum([row[i][0] for i in range(i,min(K*2+i+1,len(row)))]))
if ans == []:
    for i in range(max(len(row)-K*2,1)):
        if row[i][1] == 0:
          ans.append(sum([row[i][0] for i in range(i,min(K*2+i,len(row)))]))
print(max(ans))

Submission status: Wrong Answer

Solution code:

from itertools import groupby
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, K = tuple(li())
S = stdin.readline() + "2"
# use window
l, r = 0, 0
cnt = 0
r_iter = groupby(S)
l_iter = groupby(S)
r_next = next(r_iter)
l_next = next(l_iter)
while r_next[0] != "2":
    # print(l, r)
    if r_next[0] == '1' and K >= 0:
        r += len(list(r_next[1]))
        r_next = next(r_iter)
        cnt = max(cnt, r - l)
        K -= 1
        continue
    elif K >=0:
        if r_next[0] == "0":
            pass
        r += len(list(r_next[1]))
        r_next = next(r_iter)
        continue
    if l_next[0] == "0":
        K += 1
    elif l_next[0] == "1":
        pass
    l += len(list(l_next[1]))
    l_next = next(l_iter)
if K > 0:
    cnt = max(cnt, r-l)
print(cnt)

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]
# prev = S[0]
for s, s_next in zip(S[:-2], S[1:-1]):
    if s == s_next:
        sum_0.append(sum_0[-1])
        continue

    if s == '1' and s_next == '0':
        sum_0.append(sum_0[-1] + 1)
        continue

    sum_0.append(sum_0[-1])


# def get_1length(left, right):
#     return len()


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

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

    while sum_0[right] - sum_0[left] <= K:
        if right == N:
            break
        right += 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
s=[bool(int(s[i])) for i in range(n)]
true_index_list=[]
for i in range(k):
    true_index_list =[]
    for state_index in range(len(s)):
        if s[state_index] is True:
            true_index_list.append(state_index)
    if len(true_index_list) == 0:
        for false_index in range(n):
            s[false_index] = not s[false_index]
    elif len(true_index_list) == 1:
        for false_index in range(true_index_list[0]):
            s[false_index] = not s[false_index]
    else:
        start = 0
        end = 0
        diff = 0
        for index in range(len(true_index_list)):
            if index == len(true_index_list) - 1:
                break
            if true_index_list[index+1] - true_index_list[index] >= diff:
                start = true_index_list[index]
                end = true_index_list[index+1] 
                diff =  true_index_list[index+1] - true_index_list[index]
        for false_index in range(start+1, end):
            s[false_index] = not s[false_index]




cnt=0
max_cnt = 0
for state in s:
    if state:
        cnt+=1
    else:
      cnt = 0
      max_cnt = cnt

if cnt >= max_cnt:
  max_cnt = cnt
print(max_cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = list(str(input()))
list = [int(s) for s in S]
L = []
if list[0] == 0:
    L.append(0)
cnt = 1
for i in range(len(list) - 1):
    if list[i] == list[i + 1]:
        cnt += 1
    else:
        L.append(cnt)
        cnt = 1
L.append(cnt)
if list[N - 1] == 0:
    L.append(0)
ans = 0
for i in range((len(L) + 1)//2 - K):
    print(sum(L[(2 * i):(2 * i) + (K * 2) + 1]))
    if sum(L[(2 * i):(2 * i) + (K * 2) + 1]) > ans:
        ans = sum(L[(2 * i):(2 * i) + (K * 2) + 1])
if len(L) == 1:
    ans = max(ans, L[0])


print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
s = "1"+input().strip()+"1"
i = 0
dp = []
while i < len(s):
    l = i
    while i < len(s) and s[i] == '1':
        i += 1
    if l < i:
        dp.append([l, i-1])
    while i < len(s) and s[i] == '0':
        i += 1


if len(dp) <= K:
    print(N)
else:
    ans = 0
    for i in range(0, len(dp)-K):
        t = dp[i+K][1]-dp[i][0]
        print(dp[i][0], dp[i+K][1])
        if t > ans:
            ans = t
    print(ans)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

"""
逆立ちを連続で何人
まず1を反転させることはないだろう
どの0を選ぶかという問題になる
仮に0が010101...と10**5/2個あったとすると、K個選ぶのを愚直にやると間に合わない
1が一番つながってるところは使いたいみたいな？
もしくは0が一番つながってるところは使いたい？
dpやるなら、何回操作してて、何番目までやってるか
メモ化再起でやりたいい
memo.get('i箇所目でk回反転したとき最長がL')

ある0の場所を反転させる時、そこから離れたところは反転させる必要がないことに着目
計算を無駄にしないようにメモする？

K回指示する場合
K回以下指示はありえない
"""
positions = []
idx = 0
keep = None
one_keep = None
ones = []
while idx < N:
    if S[idx] == '0':
        if keep == None:
            keep = idx
        if one_keep != None:
            ones.append(idx - one_keep)
            one_keep = None
    else:
        if one_keep == None:
            one_keep = idx
        else:
            pass

        # 1の場合は無視
        if keep != None:
            positions.append([keep, idx])
            keep = None
        else:
            # keepしない場合
            keep = None
    idx += 1
else:
    if keep != None:
        positions.append([keep, keep+1])
#  print(positions)
if len(positions) == 0:
    print(N)
    exit()

#もともと右のほうが長い可能性もあり
if len(ones) == 0:
    # 全部0
    print(N)
    exit()
ans = max(ones)

left = 0
for idx in range(len(positions)):
    left = positions[idx][0]
    if left != 0:
        minus = 1
        while True:
            if left - minus < 0:
                #  minus -= 1
                break
            if S[left - minus] == '1':
                # 1ならまだ伸ばせる
                minus += 1
            else:
                # 0の場合はもう終わり
                #  minus -= 1
                break
        left -= minus
    # positionから右にk個反転させる
    if idx + K -1 >= len(positions):
        break
    # endはplus1idxになってる
    end = positions[idx + K-1][1]
    if end != N:
        a = 0
        while True:
            #  print(end, a)
            if end + a >= N:
                a -= 1
                break
            if S[end + a] == '1':
                a += 1
            else:
                break
        end += a

    ans = max(ans, end - left)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
s=input()
a0=[len(n) for n in s.split('1')]
a0=[i for i in a0 if i!=0]
a1=[len(n) for n in s.split('0')]
a1=[i for i in a1 if i!=0]
if len(a0)<=k:
  print(n)
else:
  ans=0
  if s[0]=='0':
    for i in range(len(a0)-k+1):
      tmp=sum(a0[i:i+k])+sum(a1[i-1:i+k])
      if ans<tmp:
        ans=tmp
  else:
    for i in range(len(a0)-k+1):
      tmp=sum(a0[i:i+k])+sum(a1[i:i+k+1])
      if ans<tmp:
        ans=tmp
  print(ans)

Submission status: Wrong Answer

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

if S[0] == '1':
    X = []
else:
    X = [0]
Y = []

count = 0
if len(S) == 1:
    if S[0] == '1':
        print(1)
    else:
        print(0)
else:
    for i,c in enumerate(S[1::]):
        count += 1
        if S[i] == '1' and c == '0':
            X.append(count)
            count = 0
        elif S[i] == '0' and c == '1':
            Y.append(count)
            count = 0
        if i == len(S)-2:
            if c == '1':
                X.append(count+1)
            else:
                Y.append(count+1)
                X.append(0)
    
    d = min(len(Y),K)
    ans = 0
    for i in range(d-1,len(Y)):
        ans = max(ans,sum(Y[i:i+d]) + sum(X[i:i+d+1]))

    print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l1=tuple(input())
l=[]
lm=[]
c=0
d=l1[0]
for i in l1:
  if i==d:
    c+=1
  else:
    d=i
    l.append(c)
    c=1
l.append(c)
l.append(0)
if l1[0]=="1":
  if len(l)//2<=m:
    print(n)
  else:
    j=0
    for i in range(((len(l)-2*m-1)//2)+1):
      lm.append(sum(l[j:j+2*m])+l[j+2*m])
      j+=2
      if j+2*m+1>len(l):
        break
    print(max(lm))
else:
  if (len(l)+1)//2<=m:
    print(n)
  else:
    j=0
    for i in range((len(l)//2)-m+1):
      lm.append(sum(l[j:j+2*m]))
      j+=2
    print(max(lm))

Submission status: Wrong Answer

Solution code:

def hanten(S,l,r):
	T = list(S.copy())
	if l == r :
		T[l-1] = "0" if T[l-1] == "1" else "1"
		return T
	for i,t in enumerate(T[l:r]) :
		T[l+i] = "0" if t == "1" else "1"
	return T

def judge_renzoku(S) :
	count_old = 0
	res = 0
	#print(S)
	if len(S) == 1 :
		return 1 if S[0]=="1" else 0

	for s in S:
		if s=="1" :
			count_old+=1
		if s=="0" :
			if count_old >= res :
				res = count_old
			count_old =0
	return res

def calc(S,N):
	res = 0
	for l in range(N+1) :
		for r in range(l,N+1) :
			T = hanten(S,l,r)
			ichi = judge_renzoku(T)
			#print("l={},r={}\nT={}".format(l,r,T))
			#print(ichi)
			if ichi >= res:
				
				res = ichi
				rT = T.copy()
	return res,rT

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

	rT = S.copy()
	for k in range(K) :
		ret,rT = calc(rT,N)
	print(judge_renzoku(rT))
			
	

if __name__ == "__main__" :
	main()

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]
# prev = S[0]
for s, s_next in zip(S[:-2], S[1:-1]):
    if s == s_next:
        sum_0.append(sum_0[-1])
        continue

    if s == '1' and s_next == '0':
        sum_0.append(sum_0[-1] + 1)
        continue

    sum_0.append(sum_0[-1])


def get_1length(left, right):
    return len()


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

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

    while sum_0[right] - sum_0[left] <= K:
        if right == N:
            break
        right += 1

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

print(ans)

Submission status: Wrong Answer

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

#K回範囲を選択して反転、を繰り返し、1の連続数を最大にする
#連続した0を１度しか含まないK+1個の1の連続を探して範囲を出力する……？

change = [0]
for i in range(1,N):
    if S[i] == '1' and S[i-1] != '1':
        change.append(i)
    elif S[i] == '0' and S[i-1] != '0':
        change.append(i)

if S[0] == '1':
    if K >= len(change)//2:
        print(N)
        quit()
else:
    if K >= (len(change)+1)//2:
        print(N)
        quit()

result = 0
if S[0] == '1':
    for i, point in enumerate(change):
        if i + K*2 + 2 > len(change):
            if i % 2 == 0:
                if result < N - point:
                    result = N - point
            else:
                if result < N - point - 1:
                    result = N - point - 1
            break
        if i % 2 == 0:
            if result < change[i + 1 + K*2] - point:
                result = change[i + 1 + K*2] - point
        else:
            if result < change[i + K*2] - change[i-1]:
                result = change[i + K*2] - change[i-1]
else:
    for i, point in enumerate(change):
        if i + K*2 + 2 > len(change):
            if i % 2 == 0:
                if result < N - point - 1:
                    result = N - point - 1
            else:
                if result < N - point:
                    result = N - point
            break
        if i % 2 == 0:
            if i == 0:
                if result < change[i + K*2] - change[i]:
                    result = change[i + K*2] - change[i]
                continue
            if result < change[i + K*2] - change[i-1]:
                result = change[i + K*2] - change[i-1]
        else:
            if result < change[i + 1 + K*2] - point:
                result = change[i + 1 + K*2] - point
print(result)

Submission status: Wrong Answer

Solution code:
22

Submission status: Wrong Answer

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

def readInts():
  return [int(s) for s in input().split(" ")]

class Node:
  def __init__(self, type, size):
    self.type = type
    self.size = size
    self.left = None
    self.right = None

  def sizeRight(self):
    if self.type == '0':
      if self.right:
        return self.size + self.right.size
      else:
        return self.size
    else:
      if self.right:
        return self.size + self.right.sizeRight()
      else:
        return self.size

  def sizeLeft(self):
    if self.type == '0':
      if self.left:
        return self.size + self.left.size
      else:
        return self.size
    else:
      if self.left:
        return self.size + self.left.sizeLeft()
      else:
        return self.size

  def unionRight(self):
    if self.right is None:
      return

    if self.type == '1':
      self.right.unionRight()

    nextRight = self.right.right
    self.size += self.right.size
    self.right = nextRight

  def unionLeft(self):
    if self.left is None:
      return

    if self.type == '1':
      self.left.unionLeft()

    nextLeft = self.left.left
    self.size += self.left.size
    self.left = nextLeft

def solve(N, K, S):
  chunks = []
  left = 0
  for i, c in enumerate(S):
    if S[left] != c:
      chunks.append( ((left, i - 1), S[left]) )
      left = i
  chunks.append( ((left, len(S) - 1), S[left]) )

  nodes = [Node(c, rs[1] - rs[0] + 1) for rs, c in chunks]
  for i in range(len(nodes)):
    if i > 0:
      nodes[i].left = nodes[i-1]
    if i < len(nodes) - 1:
      nodes[i].right = nodes[i+1]

  if len(nodes) == 1 and nodes[0].type == '1':
    return nodes[0].size

  maxNode = None
  maxSize = -1
  maxSizeLeft = -1
  for node in nodes:
    sr = node.sizeRight()
    if sr > maxSize or (sr == maxSize and node.sizeLeft() > maxSizeLeft):
      maxSize = sr
      maxSizeLeft = node.sizeLeft()
      maxNode = node

  while K > 0 and (maxNode.left or maxNode.right):
    if maxNode.sizeRight() > maxNode.sizeLeft():
      maxNode.unionRight()
    else:
      maxNode.unionLeft()
    maxNode.type = '1'
    K -= 1

  return maxNode.size

def main():
  N, K = readInts()
  S = input()

  print(solve(N, K, S))

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

if N == 1:
    print(1)
else:
    num_list = []
    wk = 1
    one_flg = SS[0] == "1"
    for i,S in enumerate(SS):
        if not i == 0:
            if S == SS[i-1]:
                wk += 1  
            else:
                num_list.append(wk)
                wk = 1
                
    num_list.append(wk)
    
#     print(num_list)
    
    one_flg = SS[0] == "1"
    chk_num = min(K * 2 + 1,len(num_list))
    ans = 0
    for i,num in enumerate(num_list[:-chk_num+1]):
        if i == 0:
            if one_flg:
                ans = sum(num_list[0:min(K * 2 + 1,len(num_list))])
            else:
                ans = sum(num_list[0:min(K * 2,len(num_list))])
        else:
            if i % 2 == 0:
                ans = max(ans,sum(num_list[i:i+chk_num]))
            
#         print(ans)

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,k = list(map(int, input().split()))
s = input()
s = s[:n]
un = False
ww = [w for w in range(n)]
ww.reverse()

for gaha in range(k-1):
	for _ in ww:
		a = "0" * _
		if not un and a != "0":
			if a in s:
				un = True
				s = s.replace(a,"1"*_,1)
				
	un = False


ww = [w for w in range(n)]
ww.reverse()

			
for da in ww:
	r = "1" * da
	if r in s:
		print(len(s))
		sys.exit()

Submission status: Wrong Answer

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

zero_ind = [m.start() for m in re.finditer('0+', S)]
one_ind = [m.start() for m in re.finditer('1+', S)]

lz = len(zero_ind)

if lz <= K:
    print(N)
else:
    if zero_ind[0] != 0:
        zero_ind = [0] + zero_ind
    else:
        one_ind = [0] + one_ind

    count = 0

    for k in range(lz -1- K):
        count = max(count, zero_ind[k+K] - one_ind[k])
        
    if S[-1] == "0":
        count = max(count, N - one_ind[-K])
    else:
        count = max(count, N - one_ind[-K-1])
    
    print(count)

Submission status: Wrong Answer

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

from sys import stdin

def indexing(s):
    index = []
    one_counter = 0
    zero_counter = 0

    for x in s:
        if x == '1':
            one_counter += 1
            if zero_counter > 0:
                index.append(zero_counter)
                zero_counter = 0
        else:
            zero_counter += 1
            if one_counter > 0:
                index.append(one_counter)
                one_counter = 0

    if zero_counter > 0:
        index.append(-zero_counter)
    elif one_counter > 0:
        index.append(one_counter)

    return index

def calc(k, s):
    nums = indexing(s)
    _max = -1
    first = 0

    if s[0] == '0':
        _max = sum(nums[:k*2])
        nums = nums[1:]
    
    if s[-1] == '0':
        last = sum(nums[-k*2:])
        _max = max(last, _max)
        nums = nums[:-1]

    _range = k*2+1

    last = sum(nums[:_range])
    _max = max(last, _max)

    for i in range(_range, len(nums), 2):
        delete = sum(nums[i-_range:i+2-_range])
        add    = sum(nums[i:i+2])
        curr = last + add - delete

        _max = max(curr, last)
        last = curr

    return _max

def main():
    n,k = [int(x) for x in stdin.readline().split()]
    s = stdin.readline().rstrip()
    ans = calc(k, s)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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
for i in range(len(S)-1):
    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)

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