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: Accepted

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

# ランレングス符号化
# (1 0 1 0 ... 0 1)の数を数える
count = []

if S[0] == 0 :
    count.append(0)

index = 0

while index < N :
    now = S[index]
    end = index + 1  # 異なる値の左端のインデックス
    while end < N :
        if S[end] != now :
            break
        end += 1
    count.append(end - index)
    index = end

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

L = len(count)

sub = sum(count[0 : 2 * K + 1])
ans = sub

i = 2
while (i + 2*K) < L :
    sub = sub - count[i-1] - count[i-2] + count[i+2*K] + count[i+2*K - 1]
    if sub > ans :
        ans = sub
    i += 2

print(ans)

Submission status: Accepted

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

end = []
start = []

if s[0] == "1":
	start.append(0)
else:
	#仮想的な1の区間を作る
	start.append(0)
	end.append(0)

for i in range(n-1):
	if s[i] == "1" and s[i+1] == "0":
		end.append(i)
for i in range(1, n):
	if s[i-1] == "0" and s[i] == "1":
		start.append(i)

if s[-1] == "1":
	end.append(n-1)
else:
	#仮想的な1の区間を作る
	start.append(n-1)
	end.append(n-1)

ans = 0

"""print(start, end, ans)
print(len(start), len(end), ans)"""

for j in range(len(start) - k):
	temp = end[j+k] - start[j] + 1 
	if temp > ans:
		ans = temp

if len(start) <= k:
	ans = n

print(ans)

Submission status: Accepted

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 or not "1" 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

len_zero = len(A[1:j+1:2])
Acc = list(accumulate(A))

i = 0

ch_num = min(K, len_zero)
while 2*ch_num+2*i <= j+1:
    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: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    s = [int(c) for c in input()]
    bl = []
    if s[0] == 0:
        bl.append(0)
    bl.append(0)
    for i in range(1, n):
        if s[i-1] != s[i]:
            bl.append(i)
    bl.append(n)
    bl.append(n)

    nbl = len(bl)
    m = [bl[i+2*k+1] - bl[i]
         for i in range(nbl - 2*k-1) if i % 2 == 0]
    if len(m) == 0:
        print(n)
    else:
        print(max(m))


main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    s = [int(c) for c in input()]
    bl = []
    # block[0] corresponds to '0'
    if s[0] == 0:
        bl.append(0)
    bl.append(0)
    for i in range(1, n):
        if s[i-1] != s[i]:
            bl.append(i)
    bl.append(n)
    bl.append(n)

    nbl = len(bl)
    m = [bl[i+2*k+1] - bl[i]
         for i in range(nbl - 2*k-1) if i % 2 == 0]
    if len(m) == 0:
        print(n)
    else:
        print(max(m))


main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
x = None
count = 0
u = []
for c in s:
    if x != c and count > 0:
        if x == '0':
            u.append(count * -1)
        else:
            u.append(count)
        count = 0
    x = c
    count = count + 1
if x == '0':
    u.append(count * -1)
else:
    u.append(count)

x = 0
st = 0
ans = []
num = 0
for i in range(len(u)):
    if u[i] < 0:
        if x + 1 > k:
            #print("i({}), st({}), num({})".format(i, st, num))
            x = x - 1
            ans.append(num)
            while True: 
                num = num - abs(u[st])
                st = st + 1
                if u[st - 1] < 0:
                    break
        x = x + 1
    num = num + abs(u[i])
if num > 0:
    ans.append(num)
#print(ans)
print(max(ans))

Submission status: Accepted

Solution code:
import numpy

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

ans = 0
cnt = 1
l = []


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


if s[0] == '0':
    l.insert(0,0)

#print(s[-1] == '0')

if s[-1] == '0':
    l.append(0)
    
l_rui = numpy.cumsum(l)
l_rui = numpy.insert(l_rui,0,0)

k = 2*k

for i in range(n):
    if 2*i >= len(l_rui):
        break
    elif k+1+2*i >= len(l_rui):
        ans = max(ans, l_rui[-1] - l_rui[2*i])
    else:
        ans = max(ans, l_rui[k+1+2*i] - l_rui[2*i])

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
loc=[1]
for i in range(1,n):
  if s[i]!=s[i-1]:
    loc.append(i+1)
loc.append(n+1)
r=len(loc)
x=[]
for j in range(r-1):
  y=loc[j]
  if s[y-1]==str(0):
    x.append(loc[min(r-1,j+2*k)]-loc[j])
  else:
    x.append(loc[min(r-1,j+2*k+1)]-loc[j])
print(max(x))

Submission status: Accepted

Solution code:
import sys

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


d=0
for s in S:
    if int(s) == 1:
        d+=1
    else:
        break

S1=[d]
S0=[0]
ic=0
st=0
for i,s in enumerate(S):
    if int(s)==0 and st==1 and i>d:
        S0.append(i-d)
        S1.append(ic)
        ic=0
    if int(s)==1 and i>d:
        ic+=1
    st=int(s)
S0.append(i+1-d)

if st==1:
    S1.append(ic)
else:
    S1.append(0)
    
if K>=(len(S0)-1):
    print(N)
    sys.exit()

ans=[]
for i in range(len(S0)-K):
    tmp=S0[i+K]-S0[i]+S1[i]
    ans.append(tmp)
    
print(max(ans))

Submission status: Accepted

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

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

change.append(len(S))

ans = 0
len_ = len(change)
for i in range(len_-1):
    if S[change[i]] == "1":
        ans = max(ans, change[min(len_-1, i+2*(max(1, K-1)))] - change[i])
    else:
        ans = max(ans, change[min(len_-1, i+2*K)] - change[max(0, i-1)])

print(ans)

Submission status: Accepted

Solution code:
def runlen(a):
    n = len(a)
    result = []
    count = 1
    for i in range(n):
        if i == n - 1 or a[i] != a[i + 1]:
            result.append((count, a[i]))
            count = 1
        else:
            count += 1
    return result

N, K = map(int, input().split())
S = input()
rl = runlen(S)
if rl[0][1] == '0':
    rl.insert(0, (0, '1'))
if rl[-1][1] == '0':
    rl.append((0, '1'))
rl, _ = zip(*rl)
l = len(rl)
first = 0
last = 2 * K + 1
stands = sum(rl[first: last])
result = stands
while last + 2 <= l:
    stands += -sum(rl[first: first + 2]) + sum(rl[last: last + 2])
    result = max(result, stands)
    first += 2
    last += 2
print(result)

Submission status: Accepted

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 = [0]

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)

total = 0
for i in range(len(nums)):
    total += nums[i]
    nums[i] = total

first = 0
if first_zero:
   first = -1

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

print(res)

Submission status: Accepted

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

def continuous_list(S):
    # 番兵
    S += '0'

    continuous_list = []
    
    index_1 = 0
    index_0 = 0

    while True:
        index_1 = S.find('1', index_0)
        index_0 = S.find('0', index_1)
        
        if index_1 == -1:
            break
        elif index_0 == len(S) - 1:
            continuous_list.append((index_1, index_0 - 1))
            break
        
        continuous_list.append((index_1, index_0 - 1))
        
    return continuous_list

def hand_stand_operation(continuous_list, K, N):
    '''
    となりあった2つ以上のタプルの結合操作を行い、その結合でできる連続した逆立ちパフォーマーの人数を数える。
    '''
    candidate = 0
    
    # 両端チェック
    KF = min(K, len(continuous_list) + 1)
    
    if KF == len(continuous_list) + 1:
        return N
    
    else:
        candidate = max(candidate, continuous_list[KF - 1][1] + 1)
        candidate = max(candidate, N - continuous_list[-KF][0])
    
    # 両端を含まない場合
    KG = min(K, len(continuous_list) - 1)
    
    for i in range(len(continuous_list) - KG):
        candidate = max(candidate, continuous_list[i + KG][1] - continuous_list[i][0] + 1)
    
    return candidate
  
print(hand_stand_operation(continuous_list(S), K, N))

Submission status: Accepted

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, K = MAP()
    S = input() + 'e'

    num = []
    count = []
    tmp0 = 0
    tmp1 = 0
    for i in range(N):
        if S[i] == '0':
            tmp0 += 1
            if S[i + 1] == '1' or S[i + 1] == 'e':
                num += [0]
                count += [tmp0]
                tmp0 = 0
        else:
            tmp1 += 1
            if S[i + 1] == '0' or S[i + 1] == 'e':
                num += [1]
                count += [tmp1]
                tmp1 = 0
    if num[0] == 0:
        num = [1] + num
        count = [0] + count
    if num[-1] == 0:
        num += [1]
        count += [0]
    k = 0
    sumv = sum(count[:2*K+1])
    maxv = sumv
    l = 0
    r = 2*K+1
    for j in range(1, len(num)//2 - K + 1):
        sumv += sum(count[r:r+2])
        sumv -= sum(count[l:l+2])
        r += 2
        l += 2
        maxv = max(maxv, sumv)
    print(maxv)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
S = input()
X = [-1]*N
k = 0
i = 1
c = 0
for s in S:
	if s == str(i):
		c += 1
	else:
		X[k] =c
		i = (i+1)%2
		c = 1
		k+= 1
X[k] = c
for n in range(N):
	if X[N-n-1] != -1:
		b = N-n
		break
X = X[:b]
M = len(X)
ko = M //2
if M == 2*ko:
	X.append(0)
#print(X)
if ko <= K:
	print(N) 
else:
	now = sum(X[0:2*K+1])
	#print(now)
	maxm = now
	for t in range(ko-K):
		a = X[2*t] +X[2*t+1]
		b = X[2*(K+t)+1]+X[2*(K+t)+2]
		now += b - a
		#print(now, a, b)
		maxm = max(maxm, now)
	print(maxm)

Submission status: Accepted

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

S = S + 'end'
if S[0] == '0':
    stand = 1
else:
    stand = 0

r = 0
l = 0
ans = 0
while r < N:
    if stand <= K:
        if S[r] == '1' and S[r+1] == '0':
            stand += 1
        r += 1
        ans = max(ans, r - l)
    elif l == r:
        l += 1
        r += 1
    else:
        if S[l] == '0' and S[l+1] == '1':
            stand -= 1
        l += 1

print(ans)

Submission status: Accepted

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
    sum_range = 0
    n = len(s0)-k+1
    for i in range(n):
        if i == 0:
            sum_range = sum(s0[:k]) + sum(s1[:k])
            ans = max(ans, sum_range)
        elif i == n-1:
            sum_range = sum(s0[i:]) + sum(s1[i-1:])
            ans = max(ans, sum_range)
        elif i == 1:
            sum_range = sum_range - s0[0] + s0[k] + s1[k]
            ans = max(ans, sum_range)
        elif i != 0:
            sum_range = sum_range - s0[i-1] + s0[i+k-1] - s1[i-2] + s1[i+k-1]
            ans = max(ans, sum_range)
    print(ans)

Submission status: Accepted

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

left = 0
right = 0
op = 0
prev = '1'
ans = 0
while right < N:
    while right < N:
        if prev == '1' and S[right] == '0':
            op += 1
            if op > K:
                break
        prev = S[right]
        right += 1
    ans = max(ans, right - left)
    prev = S[left]
    while left < right:
        if prev == '0' and S[left] == '1':
            break
        prev = S[left]
        left += 1
    op -= 1
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
l=[[],[]]
l[int(s[0])].append(1)
mae=s[0]
for i in range(1,n):
    if s[i]==mae:
        l[int(s[i])][-1]+=1
    else:
        l[int(s[i])].append(1)
        mae=s[i]
if len(l[0])<=k:
    print(sum(l[0])+sum(l[1]))
else:
    if s[0]=="0":
        l[1]=[0]+l[1]
    if s[-1]=="0":
        l[1]=l[1]+[0]
    cnt=[]
    num0=l[1][0]
    for j in range(k):
        num0+=l[0][j]+l[1][j+1]
        mem=j
    cnt.append(num0)
    for x in range(1,len(l[0])-k+1):
        num=cnt[x-1]+(l[0][mem+x]+l[1][mem+1+x])-(l[0][mem+x-k]+l[1][mem+x-k])
        cnt.append(num)
    print(max(cnt))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
A=[]
cur=s[0]
for i in range(1,n):
  if s[i]!=cur:
    A.append(i)
    cur=s[i]
A.append(n)
start,end=s[0],s[-1]
nn=len(A)
ans=0
if start=="0" and nn<=2*k:
  ans=n
elif start=="1" and nn<=2*k+1:
  ans=n
elif start=="0":
  ans=A[2*k-1]
  for i in range(1,nn//2-k+1):
    ans=max(ans,A[2*k-1+2*i]-A[2*i-2])
  if end=="0":
    ans=max(ans,A[-1]-A[-2*(k+1)+1])
else:
  ans=A[2*k]
  for i in range(1,(nn-1)//2-k+1):
    ans=max(ans,A[2*k+2*i]-A[2*i-1])
  if end=="0":
    ans=max(ans,A[-1]-A[-2*(k+1)+1])
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
zo = []
if s[0:1] == "0":
    zo.append(0)
count = 0
zero_one = s[0:1]
for i in range(n):
    if zero_one == s[i:i+1]:
        count += 1
    else:
        zo.append(count)
        count = 1
        zero_one = s[i:i+1]
zo.append(count)
if s[n-1:n] == "0":
    zo.append(0)

a = sum(zo[0:2*k+1])
ans = a
for i in range(int((n-(2*k+1))/2)):
    a += sum(zo[(2*k+1)+i*2:(2*k+1)+i*2+2])
    a -= sum(zo[i*2:i*2+2])
    if a > ans:
        ans = a
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools


def solve(N: int, K: int, S: int):
    L = [len(list(v))for k,v in itertools.groupby(S)]
    LL = list(itertools.accumulate(L))
    isFirstZero = (S[0] == "0")
    NN = 2 * K + 1

    res = 0
    start_index = 0
    if isFirstZero:
        start_index = 1
        res = LL[min(2*K-1,len(LL)-1)]

    for i in range(start_index,len(LL),2):
        s = LL[min(i+NN-1,len(LL)-1)]
        if i > 0:
            s -= LL[i-1]
        res = max(res,s)

    print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, K, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n, k = [int(i) for i in input().split()]
    s = input() + "3"
    s0 = []
    s1 = []
    cnt = 0
    start = 1
    for i in range(n+1):
        if start == 1 and s[i] != "1":
            s1.append(cnt)
            cnt = 1
            start = 0
        elif start == 0 and s[i] != "0":
            s0.append(cnt)
            cnt = 1
            start = 1
        else:
            cnt += 1

    #ans = max(s1)
    #for i in range(n // 2 +1):
    #    ans = max(ans, sum(s1[i:i+k+1]) + sum(s0[i:i+k]))

    ans = sum(s1[0:0+k+1]) + sum(s0[0:0+k])
    n_ans = ans

    for i in range(n):
        try:
            n_ans = n_ans + s1[k+1+i] + s0[k+i] - s1[i] - s0[i]
            ans = max(ans, n_ans)
        except:
            try:
                n_ans = n_ans + s0[k+i] - s1[i] - s0[i]
                ans = max(ans, n_ans)
            except:
                pass

    print(ans)
    #print(s1, s0)

main()

Submission status: Accepted

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

start = [0]
for i in range(n - 1):
    if s[i] != s[i + 1]:
        start.append(i + 1)
x = [0] * (len(start))
for i in range(len(start)):
    if s[start[i]] == "1":
        if i + 2 * k + 1 >= len(start):
            x[i] = n - start[i]
        else:
            x[i] = start[i + 2 * k + 1] - start[i]
    else:
        if i + 2 * k >= len(start):
            x[i] = n - start[i]
        else:
            x[i] = start[i + 2 * k] - start[i]
print(max(x))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(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, len(nums), 2):

    next_left = i
    next_right = min(i + add, len(nums))

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

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

    ans = max(tmp_sum, ans)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
cnt = 1
run = []
if len(S) == 1:
    run.append(1)
else:
    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]
if len(run) < 2 * K + 1:
    print(sum(run))
    exit()
ans = sum(run[0: 2 * K + 1])
sb = ans
for j in range(2, len(run) - 2 * K):
    if j % 2 == 1:
        continue
    else:
        sb = sb - run[j - 1] - run[j - 2] + run[j + 2 * K] + run[j + 2 * K - 1]
        if sb > ans:
            ans = sb
print(ans)

Submission status: Accepted

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

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

if S[0] == '1':
    ans = 0
    tmp = 0
    dist = 2 * (K + 1)
    for i in range(len(L)):
        tmp += L[i]
        if i % 2 == 1:
            if i - dist >= 0:
                tmp -= L[i-dist]
                tmp -= L[i-dist+1]
            ans = max(ans, tmp)
        else:
            if i == N - 1:
                ans = max(ans, tmp)
    print(ans)

if S[0] == '0':
    ans = 0
    tmp = 0
    dist = 2 * (K + 1)
    for i in range(len(L)):
        tmp += L[i]
        if i % 2 == 0:
            if i - dist + 1 >= 0:
                tmp -= L[i-dist+1]
            if i - dist >= 0:
                tmp -= L[i-dist]
            ans = max(ans, tmp)
        else:
            if i == N - 1:
                ans = max(ans, tmp)
    print(ans)

Submission status: Accepted

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 k>=len(l)//2:
  print(n)
else:
  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: Accepted

Solution code:
n,k=map(int,input().split())
l=input()
b=True
if l[0]=="1":
  b=True
else:
  b=False
l1=[]
c=1
l11=l[0]
for i in range(1,len(l)):
  if l[i]!=l[i-1]:
    l1.append(c)
    c=1
  else:
    c+=1
l1.append(c)
if b:
  if k>=len(l1)//2:
    print(n)
  else:
    l2=[]
    c1=0
    for i in range(0,(len(l1)//2)):
      c1+=l1[i*2+1]+l1[i*2]
      l2.append(c1)
    if len(l1)%2==1:
      c2=l2[k-1]+l1[2*k]
      for j in range(k,len(l2)):
        c3=l2[j]-l2[j-k]+l1[2*(j+1)]
        if c3>c2:
          c2=c3
      print(c2)
    else:
      c2=l2[k-1]+l1[2*k]
      for j in range(k,len(l2)-1):
        c3=l2[j]-l2[j-k]+l1[2*(j+1)]
        if c3>c2:
          c2=c3
      c3=l2[-1]-l2[-1-k]
      if c3>c2:
        c2=c3
      print(c2)
else:
  if k>=(len(l1)//2)+1:
    print(n)
  else:
    l2=[l1[0]]
    c1=l1[0]
    if len(l1)%2==1:
      for i in range(1,(len(l1)//2)+1):
        c1+=l1[2*i]+l1[2*i-1]
        l2.append(c1)
      c2=l2[k-1]+l1[2*k-1]
      for i in range(k,len(l2)-1):
        c3=l2[i]-l2[i-k]+l1[i*2+1]
        if c3>c2:
          c2=c3
      c3=l2[len(l2)-1]-l2[len(l2)-1-k]
      if c3>c2:
        c2=c3
      print(c2)
    else:
      for i in range(1,(len(l1)//2)):
        c1+=l1[2*i]+l1[2*i-1]
        l2.append(c1)
      c2=l2[k-1]+l1[2*k-1]
      for i in range(k,len(l2)):
        c3=l2[i]-l2[i-k]+l1[i*2+1]
        if c3>c2:
          c2=c3
      print(c2)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
S.split('0')
c0 = [len(s) for s in S.split('1') if len(s) != 0]
c1 = [len(s) for s in S.split('0') if len(s) != 0]
if S[0] == '0':
    c1 = [0]+c1


ref = sum(c1[:K+1])+sum(c0[:K])
ans = ref
for i in range(N):
    if i < len(c0):
        ref -= c0[i]
    if i < len(c1):
        ref -= c1[i]
    if i+K < len(c0):
        ref += c0[i+K]
    if i+K+1 < len(c1):
        ref += c1[i+K+1]
    ans = max(ans,ref)

print(ans)

Submission status: Accepted

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

ans = 0
s = s + 'E'

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

l, r = 0, 0

while r < n:
    if order <= k:
        if (s[r] == '1' and s[r+1] == '0'):
            order += 1
        ans = max(ans, r - l + 1)
        r += 1
    elif l == r:
        l += 1
        r += 1
    else:
        if s[l] == '0' and s[l+1] == '1':
            order -= 1
        l += 1

print(ans)