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: Runtime Error

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# ----------------------------------
# main
N, K = R()
S = r()
A = [0] * (N+2)

if not "0" in S:
    print(len(S))
    exit()

tmp = "1"
j = 0
count = 0
for i in range(N):
    if S[i] != tmp:
        A[j] = count
        tmp = S[i]
        j += 1
        count = 1
    else:
        count += 1
else:
    A[j] = count

Acc = list(accumulate(A))

i = 0
while 2*K+2*i <= j:
    if i == 0:
        ans = Acc[2*K]
    else:
        ans = max(ans, Acc[2*K+2*i]-Acc[2*i-1])
    i += 1
print(ans)

# end of main
# ----------------------------------

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append / extend
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

# if __name__ == '__main__':
#     main()

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = input()
li = ["1","0"]
li2 = ["0","1"]
lis = []
g = 0
if c[0]=="1":
  for i in range(a):
    if c[i]==li[0]:
      g+=1
    else:
      lis.append(g)
      g=0
      li = [li[1],li[0]]
  for j in range(b):
    ma = 0
    if len(lis)%2==0:
      lis.append(0)
    for k in range(int(len(lis)/2)):
      if ma<lis[2*k]+lis[2*k+1]+lis[2*k+2]:
        ma = lis[2*k]+lis[2*k+1]+lis[2*k+2]
lis.sort()
print(lis[-1])

if c[0]=="0":
  for i in range(a):
    if c[i]==li2[0]:
      g+=1
    else:
      lis.append(g)
      g=0
      li2 = [li2[1],li2[0]]
  for j in range(b):
    ma = 0
    if len(lis)%2==0:
      lis.append(0)
    for k in range(int(len(lis)/2)):
      if ma<lis[2*k]+lis[2*k+1]+lis[2*k+2]:
        ma = lis[2*k]+lis[2*k+1]+lis[2*k+2]
lis.sort()
print(lis[-1])

Submission status: Runtime Error

Solution code:
s = list(input())
is_count_zero = True
sl = [0]
sl_ptr = 0
for c in s:
    if is_count_zero and c == '1':
        sl.append(1)
        sl_ptr += 1
        is_count_zero = False
    elif not is_count_zero and c == '0':
        sl.append(1)
        sl_ptr += 1
        is_count_zero = True
    else:
        sl[sl_ptr] += 1

# print(sl)
# print("len(sl):{} len(sl)-1)//2:{}".format(len(sl), (len(sl)-1)//2))

if k > (len(sl)-1)//2:
    print(sum(sl))
elif k == (len(sl)-1)//2:
    if sl[0] == 0:
        print(sum(sl))
    else:
        print(max(sum(sl[1:]), sum(sl[:-1])))
else:
    ans = 0
    for i in range((len(sl)+1)//2-(k-1)):
        if i == 0:
            ans = max(ans, sum(sl[:k*2-1]))
            # print("sl[:k*2-1]:{} sum:{}".format(sl[:k*2-1], sum(sl[:k*2-1])))
        else:
            ans = max(ans, sum(sl[i*2-1:(i+k)*2]))
            # print("sl[i*2-1:(i+k)*2-1]: {}".format(sl[i*2-1:(i+k)*2]))
    print(ans)

Submission status: Runtime Error

Solution code:
N, K  = (map(int, input().split()))
S = list(map(int, input()))
length = len(S)
lst = []

# 前処理
for i in range(length):
	if i == 0:
		lst.append(1)
		start = S[0]
	else:
		if S[i - 1] == S[i]:
			lst[-1] += 1
		else:
			lst.append(1)
				
# print(lst)
if (len(lst) + 1) / 2 < K:
	# print(sum(lst))
else:
	# 探索
	# 始点
	maximum = 0
	score = 0
	for i in range(start, length, 2):
		if len(lst) >= i + 2 * (K - 1) + 2:
			if i == start:
				score = sum(lst[max(0, i - 1) : min(len(lst), i + 2 * (K - 1) + 2)])
			else:
				# print(score)
				score -= sum(lst[i - 3 : i - 1])
				# print(sum(lst[i - 3 : i - 1]))
				score += sum(lst[i + 2 * (K - 1) : i + 2 * (K - 1) + 2])
				# print(sum(lst[i + 2 * (K - 1) : i + 2 * (K - 1) + 2]))
			# print(max(0, i - 1), min(len(lst), i + 2 * (K - 1) + 2))
			# print("score={}".format(score))
			if score > maximum:
				maximum = score
	print(maximum)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
from collections import deque

input = sys.stdin.readline

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

    l = 0
    right = 0
    k = 0
    max_n = 0
    pos = deque()
    for r in range(N):
        if S[r] == "1" and (r == 0 or S[r-1] == "0"):
            k += 1
            pos.append(r)
        if k > K:
            k -= 1
            l = pos.popleft()
        if r+1 == N and S[r] == "0":
            max_n = max(max_n, pos.pop() - l + 1)
        else:
            max_n = max(max_n, r - l + 1)

    print(max_n)

main()

Submission status: Runtime Error

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

now = 1
cnt = 0
nums = []

for i in range(n):
    if s[i] == now: cnt+=1
    else:
        nums.append(cnt)
        now = 1 - now  # 0, 1の切り替え
        cnt = 1  # カウントを始める

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

# 計算しやすさのため、1の個数-0の個数...1の個数という配列が欲しい
if (len(nums) % 2 == 0): nums.append(0)

add = 2 * k + 1
tmp_sum = 0

left = 0
right = 0

ans = 0

for i in range(0, n, 2):

    next_right = i
    next_left = min(i + add, n)

    while left < next_left:
        tmp_sum -= nums[left]
        left++

    while right < next_right:
        tmp_sum += nums[right]
        right++

    ans = max(tmp_sum, ans)

print(ans)

Submission status: Runtime Error

Solution code:
rom 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)
X = [sum(run[j: j + 2 * K + 1]) for j in range(max(len(run) - 2 * K, 1))]
if len(X) == 0:
    print(1)
else:
    print(max(X))

Submission status: Runtime Error

Solution code:

n, k = [ int(v) for v in input().split() ]
s = list(map(int,list(input())))
binary_list = [0]
b = 0
for i in range(n):
	if s[i] == 1:
		b += 1
	else:
		b -= 1
	if i < n-1 and s[i] != s[i+1]:
		binary_list.append(b)
		b = 0
binary_list.append(b)
binary_list.append(0)

k = 2 * k + 1
ans = 0
for i in range(len(binary_list)-k+1):
	sumpart = collect(binary_list[i:i+k])
	ans = max(ans,sumpart)

print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
w=input()
l=[]
c=0
w="1"+w
for i in range(1,1+n):
  if w[i]!=w[i-1]:
    l.append(c)
    c=1
  else:
    c+=1
l.append(c)
if w[-1]=="0":
  l.append(0)
s=l[0]
for i in range(1,1+k):
  s+=l[2*i]+l[2*i-1]
s1=s
c1=l[0]+l[1]
for i in range(1,(len(l)+1)//2-k):
  s1=s1-l[2*i-2]-l[2*i-1]+l[2*i-1+2*k]+l[2*i+2*k]
  if s1>s:
    s=s1
print(s)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
w=input()
l=[]
c=0
w="1"+w
for i in range(1,1+n):
  if w[i]!=w[i-1]:
    l.append(c)
    c=1
  else:
    c+=1
l.append(c)
if w[-1]=="0":
  l.append(0)
s=l[0]
for i in range(1,1+k):
  s+=l[2*i]+l[2*i-1]
s1=s
c1=l[0]+l[1]
for i in range(1,(len(l)+1)/2):
  s1=s1-l[2*i-2]-l[2*i-1]+l[2*i-2+2*k+1]+l[2*i+2*k]
  if s1>s:
    s=s1
print(s)

Submission status: Runtime Error

Solution code:
# -*- Coding: utf-8 -*-
import numpy as np

def sort_arr(n,arr,f):
  d_idx = np.zeros((n,2))
  d = np.zeros((n))
  for i in xrange(n):
    d[i] = arr[i][1]-arr[i][0]

  #flag=0:ascending order,flag=1:descending order
  if f == 0: 
    sort_didx = np.argsort(d)
  else:
    sort_didx = np.argsort(d)[::-1]

  for i in xrange(sort_didx.size):
    d_idx[i] = arr[sort_didx[i]]

  return d_idx

N,K = map(int,raw_input().split())
S = raw_input()
S = map(int,list(S))
S = np.array(S)
S_sum = np.sum(S)


one_idx = []
zero_idx = []
flag = 0
one_start = 0
zero_start = 0
for i in xrange(N-1):
  if S[i]!=S[i+1]:
    if flag == 0:
      if S[i] == 0:
        zero_idx.append((i,i))
        one_start = i+1
      else:
        one_idx.append((i,i))
        zero_start = i+1
    else:
      if S[i] == 0:
        zero_idx.append((zero_start,i))
        one_start = i+1
      else:
        one_idx.append((one_start,i))
        zero_start = i+1
      flag = 0
  if flag == 0:
    flag = 1
    if S[i] == 0:
      zero_start = i
    else:
      one_start = i

#one_sortidx = sort_arr(len(one_idx),one_idx,1)
zero_sortidx = sort_arr(len(zero_idx),zero_idx,1)

if np.sum(S) == N:
  print 1
else:
  for i in xrange(K):
      for j in xrange(int(zero_sortidx[i][0]),int(zero_sortidx[i][1]+1)):
        S[j] = 1
  

  cnt = 0
  ans = 0

  if S[i] == 1:
    cnt =1
  for i in xrange(1,N):
    if S[i] == 1:
      cnt += 1
    else:
      if S[i-1] == 1:
        ans = max(ans,cnt)
        cnt = 0
        continue
    ans = max(ans,cnt)

  print ans

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s = input()
bl = []

left = -1
right = 0
for i in range(len(s)):
    if s[i] == '0':
        if left < 0:
            left = i
        if i == n - 1:
            right = n
            bl.append((left, right))
    else:
        if left >= 0:
            right = i
            bl.append((left, right))
            left = -1


def change(index, count, ts):
    if count >= k or index >= len(bl):
        max_seq = 0
        seq = 0
        for i in range(len(ts)):
            if ts[i] == '1':
                seq += 1
                if i == n - 1:
                    max_seq = max(max_seq, seq)
            else:
                max_seq = max(max_seq, seq)
                seq = 0
        return max_seq

    new_s = ts[:bl[index][0]] + '1' * \
        (bl[index][1] - bl[index][0]) + ts[bl[index][1]:]
    return max(change(index + 1, count + 1, new_s),
               change(index + 1, count, ts))


if k >= len(bl):
    print(len(s))
else:
    print(change(0, 0, s))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=list(map(int,input()))
if s.count(0)==0 or s.count(1)==0:
  print(n)
else:
  l=[]
  l1=[]
  for i in range(n):
    if i==0:
      l.append(i)
    else:
      if (s[i]==0 and s[i-1]!=0) or (s[i]==1 and s[i-1]!=1):
        l1.append(i-l[-1])
        l.append(i)
  l1.append(n-l[-1])
  l.append(n)
  
  l2=[sum(l1[i:i+2*k+1]) if s[0]==1 else sum(l1[i:i+2*k]) for i in range(0,len(l1)-2*k,2)]
  print(max(l2))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=list(map(int,input()))
if s.count(0)==0 or s.count(1)==0:
  print(n)
else:
  l=[]
  l1=[]
  for i in range(n):
    if i==0:
      l.append(i)
    elif i==n-1:
      l1.append(n-l[-1])
      l.append(n)
    else:
      if (s[i]==0 and s[i-1]!=0) or (s[i]==1 and s[i-1]!=1):
        l1.append(i-l[-1])
        l.append(i)
  
  l2=[sum(l1[i:i+2*k+1]) for i in range(0,len(l1)-2*k,2)]
  print(max(l2))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=list(map(int,input()))
if s.count(0)==0 or s.count(1)==0:
  print(n)
else:
  l=[]
  for i in range(n):
    if i==0:
      l.append(i)
    elif i==n-1:
      l.append(n)
    else:
      if s[i]==0 and s[i-1]!=0:
        l.append(i)
      if s[i]==1 and s[i-1]!=1:
        l.append(i)
  l1=[l[i+1]-l[i] for i in range(len(l)-1)]
  if s[0]==0:
    m=2*k
  else:
    m=2*k+1
  l2=[sum(l1[i:i+m]) for i in range(len(l1)-m+1)]
  print(max(l2))

Submission status: Runtime Error

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

l=[]
for i in range(n):
  if i==0:
    l.append(i)
  elif i==n-1:
    l.append(n)
  else:
    if s[i]==0 and s[i-1]!=0:
      l.append(i)
    if s[i]==1 and s[i-1]!=1:
      l.append(i)
l1=[l[i+1]-l[i] for i in range(len(l)-1)]
if s[0]==0:
  m=2*k
else:
  m=2*k+1
l2=[sum(l1[i:i+m]) for i in range(len(l1)-m+1)]
print(max(l2))

Submission status: Runtime Error

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

l0=[i for i in range(n) if s[i]==0]
l1=[i for i in range(n) if s[i]==1]
l0_pop=[l0[i+1] for i in range(len(l0)-1) if l0[i+1]==l0[i]+1]
l1_pop=[l1[i+1]for i in range(len(l1)-1) if l1[i+1]==l1[i]+1]
if len(l0)==0 or len(l1)==0:
  print(n)
else:
  for item0 in l0_pop:
    l0.remove(item0)
  for item1 in l1_pop:
    l1.remove(item1)
  l=l0.copy()
  l.extend(l1)
  l.sort()
  l_i=[l[i+1]-l[i]for i in range(len(l)-1)]
  l_i.append(n-l[-1])
  if l0[0]==0:
    m=2*k
  else:
    m=2*k+1
  ll=[sum(l_i[i:i+m]) for i in range(len(l_i)-m+1)]
  print(max(ll))

Submission status: Runtime Error

Solution code:
#何も考えずに全探索したらO(N^2)で間に合わない

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

#左端の文字は前の文字と変わった直後のみが候補
lst = [0]
for i in range(0, N-1):
    if S[i] != S[i+1]:
        lst += [i+1]

ans = 0
roop = len(lst)
lst = lst + [N]*(N+100)
# print (lst)
# print ('roop', roop)
for i in range(roop):
    if S[lst[i]] == '0':
        # print ('A', lst[i+2*K]- lst[i])
        ans = max(ans, lst[i+2*K]- lst[i])
    if S[lst[i]] == '1':
        # print ('B', lst[i+2*K +1]- lst[i])
        ans = max(ans, lst[i+2*K +1]- lst[i])
print (ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
M = [[0], [0]]
start = int(S[0])
M[start].append(1)
prev = start
for s in S[1:]:
    if int(s) == prev:
        M[prev][-1] += 1
    else:
        prev = (prev + 1) % 2
        M[prev].append(M[prev][-1] + 1)
if len(M[0]) - 1 <= K:
    print(N)
else:
    ans = 0
    if start == 0:
        for i in range(len(M[1]) - K):
            ns = M[0][i + K] - M[0][i]
            hs = M[1][i + K] - M[1][i]
            ans = max(ans, ns + hs)
    else:
        for i in range(len(M[0]) - K):
            ns = M[0][i + K] - M[0][i]
            hs = M[1][i + K + 1] - M[1][i]
            ans = max(ans, ns + hs)
    print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
S=input()+"2"
_list=[]
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
if S[-2]=="0":
    _list.append(0)
import itertools
__list=[0]+list(itertools.accumulate(_list))
C=len(__list)
K=min(C,K)
if C//2==K:
    print(_list[0])
else:
    print(max([__list[2*i+2*K+1]-__list[2*i] for i in range(C//2-K)]))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
S=input()+"2"
_list=[]
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
if S[-2]=="0":
    _list.append(0)
import itertools
__list=[0]+list(itertools.accumulate(_list))
print(_list)
print(__list)
C=len(__list)
K=min(C,K)
if C//2==K:
    print(_list[0])
else:
    print(max([__list[2*i+2*K+1]-__list[2*i] for i in range(C//2-K)]))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
S=input()
A=[]
a=S[0]
count=1
for i in range(1,N):
  if S[i]==a:
    count+=1
  else:
    A.append([a,count])
    count=1
    a=S[i]
A.append([a,count])
B=[]
C=[]
for i in range(len(A)):
  if A[i][0]=='0':
    B.append(A[i][1])
  else:
    C.append(A[i][1])
if K>=len(B):
  print(sum(B)+sum(C))
else:
  D=[]
  if S[0]=='0':
    D.append(sum(B[:K])+sum(C[:K]))
    if len(B)==len(C):
      for i in range(1,len(B)-K+1):
        D.append(sum(B[i:K+i])+sum(C[i-1:K+i]))
        prin(max(D))
    else:
      for i in range(1,len(B)-K):
        D.append(sum(B[i:K+i])+sum(C[i-1:K+i]))
      D.append(sum(B[len(B)-K:len(B)+1])+sum(C[len(B)-K-1:len(B)]))
      print(max(D))
  else:
    if len(C)>len(B):
      for i in range(len(B)-K+1):
        D.append(sum(B[i:K+i])+sum(C[i:K+i+1]))
      print(max(D))
    else:
      for i in range(len(B)-K):
        D.append(sum(B[i:K+i])+sum(C[i:K+i+1]))
      D.append(sum(B[len(B)-K:len(B)+1])+sum(C[len(B)-K:len(B)+1]))
      print(max(D))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
S=input()
A=[]
a=S[0]
count=1
for i in range(1,N):
  if S[i]==a:
    count+=1
  else:
    A.append([a,count])
    count=1
    a=S[i]
A.append([a,count])
B=[]
C=[]
for i in range(len(A)):
  if A[i][0]=='0':
    B.append(A[i][1])
  else:
    C.append(A[i][1])
if K>=len(B):
  print(sum(B)+sum(C))
else:
  D=[]
  if S[0]=='0':
    D.append(sum(B[:K])+sum(C[:K]))
    if len(B)<=len(C):
      for i in range(1,len(B)-K+1):
        D.append(sum(B[i:K+i])+sum(C[i-1:K+i]))
        prin(max(D))
    else:
      for i in range(len(B)-K):
        D.append(sum(B[i:K+i])+sum(C[i-1:K+i]))
      D.append(sum(B[len(B)-K+1:len(B)-K+1])+sum(C[len(B)-K:len(B)-K]))
      print(max(D))
  else:
    D.append(sum(B[:K])+sum(C[:K+1]))
    if len(C)>len(B):
      for i in range(1,len(B)-K+1):
        D.append(sum(B[i:K+i])+sum(C[i:K+i+1]))
      print(max(D))
    else:
      for i in range(1,len(B)-K):
        D.append(sum(B[i:K+i])+sum(C[i:K+i+1]))
      D.append(sum(B[len(B)-K+1:len(B)+1])+sum(C[len(B)-K+1:len(B)+1]))
      print(max(D))
print(D)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline()

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, K = map(int, input().split())
S = list(input())
S = [int(i) for i in S]

L = [0]
R = [0]

for i in range(N):
	if S[i] == 0:
		if i == N - 1:
			L.append(i + 1)
		elif S[i + 1] == 1:
			L.append(i + 1)
	if S[N - i -1] == 0:
		if i == N - 1:
			R.append(i + 1)
		elif S[N - i -2] == 1:
			R.append(i + 1)

ans = 0
M = len(L) - K

if M <= 0:
	ans = N
	
for i in range(M):
	tmp = N - L[i] - R[M - i - 1]
	if tmp > ans:
		ans = tmp

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, K = map(int, input().split())
S = list(input())
S = [int(i) for i in S]

L = [0]
R = [0]

for i in range(N):
	if S[i] == 0:
		if i == N - 1:
			L.append(i + 1)
		elif S[i + 1] == 1:
			L.append(i + 1)
	if S[N - i -1] == 0:
		if i == N - 1:
			R.append(i + 1)
		elif S[N - i -2] == 1:
			R.append(i + 1)

ans = 0
M = len(L) - K

if M <= 0:
	ans = N
	
for i in range(M):
	tmp = N - L[i] - R[M - i - 1]
	if tmp > ans:
		ans = tmp

print(ans)

Submission status: Runtime Error

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

t = []
accum_mode = False
l = r = 0

for i in range(1, n + 1):
    if s[i - 1] == '0' and s[i] == '1':
        l = i
    if s[i] == '1' and s[i + 1] == '0':
        r = i
        t.append((l, r))

res = 0

if k < len(t):
    for i in range(len(t) - k):
        tmp = t[i + k][1] - t[i][0]
        res = max(res, tmp)
    if t[0][0] != 1:
        tmp = t[k - 1][1] - 1
        res = max(res, tmp)
else:
    for i in range(len(t)):
        res = t[-1][1] - t[0][0]
    if t[0][0] != 1:
        tmp = t[min(k, len(t))-1][1] - 1
        res = max(res, tmp)

print(res + 1)

Submission status: Runtime Error

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

t = []
accum_mode = False
l = r = 0

for i in range(1, n + 1):
    if s[i - 1] == '0' and s[i] == '1':
        l = i
    if s[i] == '1' and s[i + 1] == '0':
        r = i
        t.append((l, r))

res = 0

if k < len(t):
    for i in range(len(t) - k):
        tmp = t[i + k][1] - t[i][0]
        res = max(res, tmp)
    if t[0][0] != 1:
        tmp = t[k - 1][1]
        res = max(res, tmp)
else:
    for i in range(len(t)):
        res = t[-1][1] - t[0][0]
    if t[0][0] != 1:
        tmp = t[min(k, len(t))-1][1]
        res = max(res, tmp)

print(res)

Submission status: Runtime Error

Solution code:
N,K= (int(i) for i in input().split()) 
S = str(input())
a=0
b=0
c=0
s=0
T=[]
P=[]
an=[]
ans=0
for i in range(N):
	if S[i]=='1':
		T.append(i)
    
s=len(T)
for i in range(s-1):
	c=T[i+1]-T[i]-1
	an.append(c)

an.sort
if s-1>=K:
	for i in range(K):
		ans=ans+an[i]
else:
	for i in range(s-1):
		ans=ans+an[i]
  
ans=ans+T[0]+s
print('%d'% ans)

Submission status: Runtime Error

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

    foo = sum(lis[0][0:K]) + sum(lis[1][0:K+1])
    for i in range(len(lis[0])+1-K):
        foo += lis[0][K+i] -lis[0][i] +lis[1][K+1+i] -lis[1][i]
        if ans < foo:
            ans = foo
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

# s = input()
# n = int(input())

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def __call__(self, a, b=None): # calc [a, b) summation by O(1)
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[min(self.n-1, a-1)]
        return res


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

s = input()
ar = np.array(list(map(int, s)))

idx = -1
b = []

for i in np.where(ar[:-1] - ar[1:] != 0)[0]:
    b.append(i-idx)
    idx = i

b.append(N-1-idx)

b_int = Interval(b)

if s[0] == '1':
    print(max(
        b_int(i, i+2*K+1) for i in range(0, b_int.n) if i%2 == 0
    ))    
else:
    res = b_int(0, 2*K)
    print(max(res, max(
        b_int(i, i+2*K+1) for i in range(1, b_int.n) if i%2 == 1
    )))

Submission status: Runtime Error

Solution code:
import numpy as np

# s = input()
# n = int(input())

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def __call__(self, a, b=None): # calc [a, b) summation by O(1)
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[min(self.n-1, a-1)]
        return res


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

s = input()
ar = np.array(list(map(int, s)))

idx = -1
b = []

for i in np.where(ar[:-1] - ar[1:] != 0)[0]:
    b.append(i-idx)
    idx = i

b.append(N-1-idx)

b_int = Interval(b)

if s[0] == '1':
    print(max(
        b_int(i, i+2*K+1) for i in range(0, b_int.n) if i%2 == 0
    ))    
else:
    res = b_int(0, 2*K)
    print(max(res, max(
        b_int(i, i+2*K+1) for i in range(1, b_int.n) if i%2 == 0        
    )))

Submission status: Runtime Error

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

# 累積和
a = [0]
if s[0] == "0":
	a.append(0)
for i in range(n):
	if i == n-1 or s[i+1] != s[i]:
		a.append(i+1) # 累積和

# print(s[-1])
if s[-1] == "0":
	a.append(s[-1])

if len(a) <= 2*k+1: # 2*k+1
	print(n)
else:
	ans = 0
	for j in range(0, len(a) - 2*k - 1, 2): # len(a)は奇数
		ans = max(ans, a[j+2*k+1] - a[j])
	print(ans)