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:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

N, K = map(int, input().split())
S = list(input())
a = []
rei = 0
ichi = 0
reicnt = 0
ichicnt = 0
for i in S:
    if i == '1':
        if rei > 0:
            a.append((0, rei))
            reicnt+=1
        rei = 0
        ichi += 1
    else:
        if ichi > 0:
            a.append((1, ichi))
            ichicnt += 1
        rei += 1
        ichi = 0
if rei > 0:
    a.append((0, rei))
    reicnt += 1
if ichi > 0:
    a.append((1, ichi))
    ichicnt+=1
if reicnt <= K:
    print(N)
else:
    zero = deque([0])
    kk = 0
    count = 0
    mx = 0
    ind = 0
    for i in a:
        if i[0] == 0:
            count += i[1]
            zero.append(count)
            kk += 1
            if kk > K:
                ind += 1
            mx = max(mx, count - zero[ind])
        else:
            count += i[1]
            mx = max(count - zero[ind], mx)
    print(mx)

Submission status: Accepted

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

Solution code:

import queue

def read_input():
    n, k = map(int, input().split())
    s = list(map(int, list(str(input()))))

    return n, k, s


# 0, 1, ....を(0, n1), (1, n2)みたいな形にする
def convert_01(s):
    result = []

    result.append([s[0], 1])
    for ss in s[1:]:
        if result[-1][0] == ss:
            result[-1][1] += 1
        else:
            result.append([ss, 1])

    return result


# index以降の要素、かつ0の数がKを下回るサブリストにある要素をカウントする
def get_count(r,k):
    count = 0
    max_count = 0
    zeros = 0

    q = queue.Queue()

    for e in r:
        if e[0] == 0 and zeros >= k:
        # すでにk回0を操作した
            while True:
                t = q.get()
                count -= t[1]

                if t[0] == 0:
                    zeros -= 1
                    break

        q.put(e)
        count += e[1]

        if e[0] == 0:
            zeros += 1

        if max_count < count:
            max_count = count

    return max_count






if __name__ == '__main__':
    n, k, s = read_input()
    r = convert_01(s)

    print(get_count(r, k))

Submission status: Accepted

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

change_points = [i for i in range(n) if i == 0 or s[i-1] != s[i]]
change_points.append(n)
max_ = 0
for i, p in enumerate(change_points):
    if i == len(change_points) - 1:
        continue
    if s[p] == '0':
        if i == 0:
            idx = min(i + 2 * k, len(change_points) - 1)
            tmp = change_points[idx] - p
        else:
            continue
    else:
        idx = min(i + 2 * k + 1, len(change_points) - 1)
        tmp = change_points[idx] - p
    if tmp > max_:
        max_ = tmp

print(max_)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
if n == 1:
    print(1)
if n != 1:
    nums = []
    cnt = 1
    for i in range(1, n):
        if s[i - 1] != s[i]:
            nums.append([s[i - 1], cnt])
            cnt = 1
            if i == n - 1:
                nums.append([s[i], cnt])
        else:
            cnt += 1
            if i == n - 1:
                nums.append([s[i - 1], cnt])

    candi = 0
    ansli = []
    p = 0
    for i in range(len(nums)):
        if nums[i][0] == "0":
            p += 1
    k = min(k, p)

    i1 = 0
    j1 = 0
    while i1 <= k and j1 < len(nums):
        if i1 == k and nums[j1][0] == "0":
            pass
        else:
            candi += nums[j1][1]
        if nums[j1][0] == "0":
            i1 += 1
        j1 += 1
    ansli.append(candi)
    if candi == n:
        print(n)
        exit()

    a = 0
    b = j1 - 1
    while b < len(nums):
        for i in range(2):
            if nums[a + i][0] == "1":
                candi -= nums[a + i][1]
            elif nums[a + i][0] == "0":
                candi -= nums[a + i][1]
                a += i + 1
                break
        for i in range(2):
            if b + i >= len(nums):
                ansli.append(candi)
                b += 1
                break
            else:
                if nums[b + i][0] == "1":
                    candi += nums[b + i][1]
                    b += i + 1
                    ansli.append(candi)
                    break
                elif nums[b + i][0] == "0":
                    candi += nums[b + i][1]

    print(max(ansli))

Submission status: Accepted

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]))
        ret.append(sum(array[-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: Accepted

Solution code:
import sys

N, K = map(int, input().strip().split(' '))
S = input().strip()
prev = ''
l = 0
lst = []
for s in S:
    if s == prev:
        l += 1
    else:
        lst += [l]
        l = 1
    prev = s
lst += [l]
lst = lst[1:]
# print(lst)

flip = S[0] == '1'
res = sum(lst[0:2*K+flip])
cur = res
# print(cur)
flip ^ - 1
for i in range(1, len(lst)):
    cur -= lst[i-1]
    if not flip:
        cur += sum(lst[i+2*K-1:i+2*K+1])
        res = max(cur, res)
        # print(lst[i+2*K:i+2*K+2])
    # res = max(res, sum(lst[i:i+2*K+flip]))
    # print(cur)
    flip ^= 1

# print(N, K)
# print(S)
print(res)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))


N, K = ints_raw()
S = input()
cts = []
ctree = {}



def main():
    ans = 0
    kukan = 1
    start = 0
    if S[0]=="0":
        cts.append(["1",0,0])
    for i in range(1,len(S)):
        if S[i-1]!=S[i]:
            cts.append([S[i-1],kukan,start])
            start = i
            kukan=0
        kukan+=1
    cts.append([S[-1],kukan,start])
    if S[-1]=="0":
        cts.append(["1",0, N-1])
    if K*2+1 >= len(cts):
        return N
    buf = sum([cts[i][1] for i in range(K*2+1)])
    ans = buf
    for i in range(K*2+1,len(cts)):
        n_buf = buf-cts[i-(K*2+1)][1]+cts[i][1]
        if cts[i][0]=="1":
            ans =max(ans,n_buf)
        buf = n_buf
    return ans

print(main())

Submission status: Accepted

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

cnt_list = []
i = 0
if s[0] == "0":
    key = "0"
else:
    key = "1"
last = 0
while i < N:
    j = i
    tmp = 1
    for j in range(i + 1, N):
        if s[j] == key:
            tmp += 1
            if j == N - 1:
                last = 1
        else:
            break

    cnt_list.append([int(key), tmp])

    if key == "0":
        key = "1"
    else:
        key = "0"
    i = max(j, i + 1)
    if last:
        break

cnt = K
i = 0
tmp = 0
while cnt > 0 and i < len(cnt_list):
    tmp += cnt_list[i][1]
    if cnt_list[i][0] == 0:
        cnt -= 1
    i += 1

if i < len(cnt_list):
    tmp += cnt_list[i][1]
    i += 1

anslist = []
anslist.append(tmp)

start = 0
while i < len(cnt_list) and start < len(cnt_list):
    if cnt_list[start][0] == 1:
        tmp -= cnt_list[start][1]
        if start + 1 < len(cnt_list):
            tmp -= cnt_list[start + 1][1]
        start += 2
    else:
        tmp -= cnt_list[start][1]
        start += 1

    if cnt_list[i][0] == 0:
        tmp += cnt_list[i][1]
        if i + 1 < len(cnt_list):
            tmp += cnt_list[i + 1][1]
        i += 2
    else:
        tmp += cnt_list[i][1]
        i += 1
    anslist.append(tmp)

print(max(anslist))

Submission status: Accepted

Solution code:
"""
python3 c.py < input.txt
"""
import math
import itertools as it
import heapq

N,K=map(int, input().split())
S=input()
T=[S[0]]
U=[1]
for c in S[1:]:
    if c==T[-1]:
        U[-1]=U[-1]+1
    else:
        T.append(c)
        U.append(1) 
M=len(U)
V=[U[0]]
for i in range(1,M):
    V.append(V[-1]+U[i])

X=[]
for l in range(M):
    if T[l]=="0":
        ll=max(0, l-1)
        r=max(l, min(M-1, l+2*(K-1)+1))
        X.append((ll, r))
    else:
        X.append((0,0))
V=[0]+V
#print(T)
#print(U)
#print(V)
#print(X)
#print([([0]+V)[r+1]-([0]+V)[l] for (l,r) in X])
print(max([V[r+1]-V[l] for (l,r) in X]))

Submission status: Accepted

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

import sys
import copy

# input = sys.stdin.readline

# ---------------------------------------------------------

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

cnt = []
kind = []

i, j = 0, 0
while i < N:
    while j < N and S[i] == S[j]:
        j += 1
    cnt.append(j - i)
    kind.append(int(S[i]) - int('0'))
    i = j

ans = 0
sum = 0
zero = 0
L = len(cnt)
right = 0
for left in range(len(cnt)):
    if left > right:
        right = left
    while right < len(cnt) and zero <= K:
        if kind[right] == 0 and zero == K:
            break
        if kind[right] == 0:
            zero += 1
        sum += cnt[right]
        right += 1

    ans = max(ans, sum)
    sum -= cnt[left]
    if kind[left] == 0:
        zero -= 1

print(ans)

Submission status: Accepted

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

import sys
import copy

# input = sys.stdin.readline

# ---------------------------------------------------------

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

cnt = []
kind = []

i, j = 0, 0
while i < N:
    while j < N and S[i] == S[j]:
        j += 1
    cnt.append(j - i)
    kind.append(int(S[i]) - int('0'))
    i = j

ans = 0
sum = 0
zero = 0
L = len(cnt)
right = 0
for left in range(L):
    if left > right:
        right = left
    while right < L and zero <= K:
        if kind[right] == 0 and zero == K:
            break
        if kind[right] == 0:
            zero += 1
        sum += cnt[right]
        right += 1

    ans = max(ans, sum)
    sum -= cnt[left]
    if kind[left] == 0:
        zero -= 1

print(ans)

Submission status: Accepted

Solution code:
N, K  = [int(elm) for elm in input().split()]
S = input()

state = 2
counts = []
k_count = 0 # 0 -> 1, count++

end_lens = []
save_flag = False
end_i = -1
for s_in, s in enumerate(S):
    if s == "0":
        if state == 1: # 1 -> 0 (c_start)
            #k_count += 1
            #if save_flag: # end 1
            #print("1->0", s_in, k_count)
            if k_count >= K: # stop counter k_count-1
                end_i += 1
                
                #print("range", counts[end_i][0], s_in)
                len_ = s_in - counts[end_i][0]
                end_lens.append(len_)
                save_flag = False

            state = 0

        elif state == 2: # first
            new_count = [s_in, 0, -1]
            counts.append(new_count)
            state = 0
            pass
        else: # state = 0 cont.
            pass

    if s == "1":
        if state == 0: # 0 -> 1 (c_end)
            k_count += 1            
            #print("0->1", s_in, k_count)
            state = 1

            new_count = [s_in, 0, -1]
            counts.append(new_count)

        elif state == 2: # first 
            new_count = [s_in, 0, -1]
            counts.append(new_count)
            state = 1
        else: # state = 1 cont.
            pass

#if save_flag:
if True:
    s_in += 1
    end_i += 1
    #print("range", counts[end_i][0], s_in)
    len_ = s_in - counts[end_i][0]
    end_lens.append(len_)
    save_flag = False

if len(end_lens) == 0:
    out = len(S)
else:
    out = max(end_lens)

print(out)

Submission status: Accepted

Solution code:
N, K = tuple(map(int, input().split()))
S = "1"+input()+"1"

prev = S[0]
if prev == "0":
  fst_is_0 = True
else:
  fst_is_0 = False

cnt = 0
cnt_0 = 0

cnt_lst = []
for idx, s in enumerate(S):
  if s == prev:
    cnt += 1
  else:
    cnt_lst.append(cnt)
    cnt = 1
    if s == "0":
      cnt_0 += 1
    prev = s
else:
  cnt_lst.append(cnt)
#print(cnt_lst)


if cnt_0 <= K:
  print(len(S)-2)
else:
  prev = "1"
  cnt_lst = [0]
  for idx,s in enumerate(S):
    if prev != s:
      cnt_lst.append(idx)
    prev=s
  cnt_lst.append(len(S))
  s_ =[]
  for idx in range( int( (len(cnt_lst)+1)/2) -K):
    #print(2*idx+2*K,idx*2,cnt_lst[2*idx+2*K+1] -cnt_lst[idx*2])
    if idx==0 or idx==int( (len(cnt_lst)+1)/2) -K-1:
      s_.append(cnt_lst[2*idx+2*K+1] -cnt_lst[idx*2]-1)
    else:
      s_.append(cnt_lst[2*idx+2*K+1] -cnt_lst[idx*2])
  print(max(s_))

Submission status: Accepted

Solution code:
n, k = [int(item) for item in input().split()]
s = input() + "#"

series = []
prev = "#"
for i, c in enumerate(s):
    if prev != c:
        series.append(i) 
        prev = c

ans = 0
if s[0] == "1":
    for i in range(0, len(series) -1 -2*k, 2):
        ans = max(ans, series[i + 2*k + 1] - series[i])
    ans = max(ans, series[min(k*2+1, len(series)-1)])
else:
    for i in range(1, len(series) -1 -2*k, 2):
        ans = max(ans, series[i + 2*k + 1] - series[i])
    ans = max(ans, series[min(k*2, len(series)-1)])
if s[-2] == "0":
    ans = max(ans, series[-1] - series[max(0, len(series)-1-2*k)])
print(ans)

Submission status: Accepted

Solution code:
from sys import exit
from queue import Queue

q = Queue()

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

S = input()

ans_list = []

delta = 0

Flag = False

buffer = 0

for i in range(len(S)):
    if S[i] == '0' and not Flag:
        Flag = True
        buffer = i
        if K == 0:
            ans_list.append(i - delta)
    if S[i] == '1' and Flag:
        if K > 0:
            K -= 1
            q.put((buffer, i - 1))
        else:
            delta = q.get()[1] + 1
            q.put((buffer, i - 1))
        Flag = False
if K > 0:
    print(len(S))
    exit()

if S[len(S) - 1] == '0':
    delta = q.get()[1] + 1
    ans_list.append(len(S) - delta)

if S[len(S) - 1] == '1':
    ans_list.append(len(S) - delta)

print(max(ans_list))

Submission status: Accepted

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

# 穴の位置memo
memo = []
cnt = 0
for i in range(len(S)):
    if S[i] == "1":
        if cnt > 0:
            memo.append([i-cnt,cnt])
        cnt = 0
    else:
        cnt += 1
if cnt > 0:
    memo.append([i+1-cnt,cnt])
# print(memo)

import sys
if K >= len(memo):
    print(len(S))
    sys.exit()

max = 0
for i in range(len(memo) - K + 1):
    if i == 0:
        max = memo[K][0]
    elif i == (len(memo) - K):
        if max < len(S) - (memo[i-1][0] + memo[i-1][1]):
            max = len(S) - (memo[i-1][0] + memo[i-1][1])
    else:
        if max < memo[i + K][0] - (memo[i-1][0] + memo[i-1][1]):
            max = memo[i + K][0] - (memo[i-1][0] + memo[i-1][1])
print(max)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s = input()
A = [0,0]
zerodig = 0
for i in range(N-1):
    if s[i] != s[i+1]:
        A.append(i+1)
        if (s[i] == "0" and s[i+1] == "1"):
            zerodig += 1
if s[N-1] == "0":
    zerodig += 1

A.append(len(s))
A.append(len(s))

if s[0] == "0":
    check = 0
else:
    check = 1

width = 2 * K + 1
score = 0

if zerodig <= K:
    print(len(s))
else:
    for i in range(len(A)-width):
        if score <= A[i+width] - A[i] and (i+check) % 2 == 0:
            score = A[i+width] - A[i]
    print(score)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys

n, k = [int(x) for x in input().split()]
ss = [int(x) for x in input()]

zero_array = []
one_array = []
curr_num = ss[0]
flag = 0

if curr_num == 0:
    zero_array.append(0)
else:
    one_array.append(0)
    flag = 1

for i in ss:
    if curr_num == i:
        if i == 0:
            zero_array[-1] += 1
        else:
            one_array[-1] += 1
    else:
        curr_num = i
        if i == 0:
            zero_array.append(1)
        else:
            one_array.append(1)

# print("zero_array", zero_array)
# print("one_array", one_array)
# print("flag", flag)

if k >= len(zero_array):
    print(sum(zero_array) + sum(one_array))
    sys.exit()
else:
    t = 0
    tmp = sum(zero_array[t: t+k]) + sum(one_array[t: t+k+flag])
    max_count = tmp
    # print("outer_tmp", tmp)
    # print()
    while t + k + flag <= len(one_array) and t + k < len(zero_array):
        # print("t", t)
        tmp += zero_array[t+k] - zero_array[t]
        if t+k+flag < len(one_array):
            tmp += one_array[t+k+flag]
            if not (t == 0 and flag == 0):
                if t == 0:
                    pass
                    # print("yeh")
                tmp -= one_array[t+flag-1]
        elif not (t == 0 and flag == 0):
            tmp -= one_array[t+flag-1]
        # print("tmp", tmp)
        if tmp > max_count:
            max_count = tmp
            # print(t, max_count)
        t += 1

    print(max_count)
# print(zero_array)
# print(one_array)

Submission status: Accepted

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

cnt = 0
for i in range(n):
    if s[i] == "1" and cnt == 0:
        ans_0.append(i)
        cnt += 1
    elif s[i] == "0":
        cnt = 0
cnt = 0
for i in range(n):
    if s[n-1 - i] == "1" and cnt == 0:
        ans_1.append(n-1-i)
        cnt += 1
    elif s[n-1 - i] == "0":
        cnt = 0
ans_1.sort()
ans_list = []
if len(ans_0) == 0:
    print(n)
elif len(ans_0) == 1:
    if k == 1:
        print(max(n-ans_0[0], ans_1[0]+1))
    else:
        print(n)
elif len(ans_0) < k:
    print(n)
else:
    if 0 not in ans_0:
        ans_0.append(0)
        ans_1.append(0)
        ans_0.sort()
        ans_1.sort()
    if n-1 not in ans_1:
        ans_0.append(n-1)
        ans_1.append(n-1)
    for i in range(len(ans_0) - k):
        ans_list.append(ans_1[i+k] - ans_0[i])
    print(max(ans_list) + 1)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split(" "))
S = np.array([int(i) for i in input()])
pos1 = np.linspace(0,N-1,N)[S == 1]
lst = []
if len(pos1) == 0:
    print(N)
else:    
    st =[pos1[0]]
    if len(pos1) != 1:
        for i in pos1[1:]:
            if st[-1] + 1 == i:
                st.append(i)
            else:
                lst.append(st)
                st = [i]
            if i == pos1[-1]:
                lst.append(st)
    else:
        lst.append(st)
    lst = [[0]] + lst + [[N-1]]
    time = len(lst) - K
    if time <= 0:
        print(N)
    else:
        print(int(max([max(lst[i+K]) - min(lst[i])+1 for i in range(time)])))

Submission status: Accepted

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

def get_sequence(arr):
    if len(arr) == 0:
        return []
    result = []
    n = 1
    prev = arr[0]
    for c in arr[1:]:
        if c == prev:
            n += 1
        else:
            result.append([prev,n])
            prev = c
            n = 1
    result.append([prev,n])
    return result

seq = get_sequence(S)
lengths = [ x[1] for x in seq ]
if seq[0][0] == '0':
    lengths.insert(0,0)
if seq[-1][0] == '0':
    lengths.append(0)

L = (len(lengths)-1)//2
if L <= K:
    print(N)
else:
    ans = sum(lengths[:2*K+1])
    now = ans
    for i in range(L-K):
        now += sum(lengths[2*(K+i)+1:2*(K+i)+3])-sum(lengths[2*i:2*(i+1)])
        ans = max(ans,now)
    print(ans)

Submission status: Accepted

Solution code:
# 2019/04/13
# AtCoder Beginner Contest 124 - D

# Input
n, k = map(int,input().split())
s = input()
bgnl = list()
endr = list()

bgnl.append(0)
endr.append(0)

seqflg = False

# Search for begin 1
for i in range(n):
    if s[i] == "0":
        if seqflg == True and i > 0:
            endr.append(i-1)
            seqflg = False
    elif s[i] == "1" and seqflg == False:
        bgnl.append(i)
        seqflg = True

if s[n-1] == "1":
    endr.append(n-1)

bgnl.append(n-1)
endr.append(n-1)

max = 0
if len(bgnl) >= k:
    for j in range(0, len(bgnl)-k):
        pcnt = endr[j+k] - bgnl[j] + 1
#        if j == 0 or j+k == n:
#            pcnt -= 1
#        print(pcnt, endr[j+k], bgnl[j])
        if max < pcnt:
            max = pcnt
    ans = max

else:
    ans = n
    
#print(bgnl)
#print(endr)

# Output
print(ans)

Submission status: Accepted

Solution code:
import re

def norm(s):
    s1 = list(map(len, re.split('0+', s)))
    s0 = list(map(len, re.split('1+', s)))
    if s0[0] == 0:
        s0.pop(0)
    if s0[-1] == 0:
        s0.pop(-1)
    return [s0,s1]

def solve(n, k, s):
    s0, s1 = norm(s)

    if len(s1) == 1:
        return(s1[0])

    if len(s0) <= k:
        return n
    
    s0_sum = sum(s0[0:k])
    s1_sum = sum(s1[0:k+1])

    v = s0_sum + s1_sum
    mv = v
    
    for last_idx in range(0, len(s0) - k):
        # update
        v = (v - s0[last_idx] + s0[last_idx + k] -
             s1[last_idx] + s1[last_idx + k + 1])
        if mv < v:
            mv = v

    return mv


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

Submission status: Accepted

Solution code:
import numpy as np


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

# search where 1
arr = np.array([0] + s_arr.tolist() + [0])
diff = np.diff(arr)
heads = np.where(diff == 1)[0]
tails = np.where(diff == -1)[0]
assert heads.size == tails.size

if s_arr[0] == 0:
    heads = np.array([0] + heads.tolist())
    tails = np.array([0] + tails.tolist())

if s_arr[-1] == 0:
    heads = np.array(heads.tolist() + [len(s_arr)])
    tails = np.array(tails.tolist() + [len(s_arr)])

ans = 0
for i, head in enumerate(heads):
    idx = min(i + K, len(tails) - 1)
    tail = tails[idx]
    ans = max(ans, tail - head)

print(ans)

Submission status: Accepted

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

b = '1'

l = []
c = 0
for s in S:
	if b == s:
		c = c + 1
	else:
		l.append(c)
		c = 1
		b = '1' if b == '0' else '0'

l.append(c)
if S[-1] == '0':
	l.append(0)

n = len(l)//2
if n <= K:
	print(N)
	exit()

size = len(l)
cand = []
k = 2*K+1
cd = sum(l[0:k])
cand.append(cd)
for i in range(0,size-k,2):
	cd = cd - l[i]-l[i+1] + l[i+k] + l[i+k+1]
	cand.append(cd)
print(max(cand))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
T = []
if S[0] == '0': T.append(0)
cnt = 1
for i in range(1, N):
    if S[i - 1] == S[i]:
        cnt += 1
    else:
        T.append(cnt)
        cnt = 1
if cnt > 0: T.append(cnt)
if S[-1] == '0': T.append(0)
cs = [0] * (len(T) + 1)
n = 0
for i in range(1, len(T) + 1):
    n += T[i - 1]
    cs[i] = n

n = min(K * 2 + 1, len(T))
ans = 0
for i in range(1, len(T) - n + 2, 2):
    t = cs[i + n - 1] - cs[i - 1]
    if ans < t: ans = t
print(ans)

Submission status: Accepted

Solution code:
import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = [0]*(len(L)+1)
for i in range(len(L)):
  L_cum[i]=L_cum[i-1]+L[i]

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)]-L_cum[i*2-1]
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)+1]-L_cum[2*i]
    ans=max(rev)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
split_list = [0]
section_list = [0]
for i in range(1, N):
    if S[i-1] != S[i]:
        section_list.append(i - split_list[-1])
        split_list.append(i)
split_list.append(N)
section_list.append(split_list[-1] - split_list[-2])
del split_list[0]
del section_list[0]
answer = 0
if len(section_list) <= 2 * K:
    answer= N
else:
    total = sum(section_list[:2 * K + 1])
    if S[0] == '1':
        answer = total
    for i in range(len(section_list) - 2 * K - 1):
        total = total - section_list[i] + section_list[i+2*K+1]
        if (S[0] == '0') & (i % 2 == 0):
            if total >= answer:
                answer = total
        if (S[0] == '1') & (i % 2 == 1):
            if total >= answer:
                answer = total
    # 0から始まるパターン
    total = sum(section_list[:2 * K])
    if total > answer:
        answer = total
    #0で終わるパターン
    total = sum(section_list[- 2 * K:])
    if total > answer:
        answer = total
print(answer)

Submission status: Accepted

Solution code:
from itertools import groupby
# from time import time

N, K = map(int, input().split())
S = input()
# N, K = 10**5, 10**5
# S = ['0', '1']*10**5
# start = time()
val_list = []
id_list = []
count = 0
for k, g in groupby(S):
    id_list.append(count)
    val_list.append(k)
    lg = len(list(g))
    count += lg
id_list.append(count)
# print(id_list)
num_sec = len(id_list)
if num_sec == 1:
    print(N)
else:
    m = 0
    end = 0
    for i in range(num_sec):
        if end == num_sec - 1:
            break
        if val_list[i] == '1':
            # print('1')
            end = min(i+2*K+1, num_sec - 1)
            v = id_list[end] - id_list[i]
            # print('  ', v)
            m = max(m, v)
        elif i == 0:
            # print('0')
            end = min(i+2*K, num_sec - 1)
            v = id_list[end] - id_list[i]
            # print('  ', v)
            m = max(m, v)
    print(m)
    # print(time() - start)

Submission status: Accepted

Solution code:
n, k = [int(_) for _ in input().split(' ')]
s = '0' + input() + '0'


a = []
if s[1] == '0':
    a.append((1, 0))

state = ''
for i in range(n + 1):
    if s[i] == '0' and s[i + 1] == '1':
        state = i + 1
    elif s[i] == '1' and s[i + 1] == '0':
        a.append((state, i))

if s[n] == '0':
    a.append((n + 1, n))

l = len(a)
if k <= l - 1:
    print(max([a[i + k][1] - a[i][0] + 1 for i in range(l - k)]))
else:
    print(n)

Submission status: Accepted

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

a = []
b = []

index = 0
length = 0
judge = "0"
for i in range(len(s)):
	if s[i] == judge:
		length += 1
	if s[i] != judge:
		if judge == "0":
			b.append(length)
		if judge == "1":
			a.append(length)
		length = 1
		judge = str((int(judge)+1)%2)
if judge == "0":
	b.append(length)
	a.append(0)
if judge == "1":
	a.append(length)


M = len(a)
if K >= M:
	print(len(s))
	exit()

ans = 0
ans_new = 0
for i in range(K):
	ans += a[i]+b[i]
ans_max = ans
for i in range(M-K):
	if i == 0:
		ans_new = ans-b[0]+b[K]+a[K]
	if i != 0:
		ans_new = ans-a[i-1]-b[i]+b[K+i]+a[K+i]
	ans_max = max(ans_max,ans_new)
	ans = ans_new
print(ans_max)

Submission status: Accepted

Solution code:

n, k = map(int, input().split())
S = str(input())

flag = '0'
ans = []
for i, s in enumerate(S):
    if s == '1':
        if flag == '0':
            tmp = [0]*2
            tmp[0] = i+1
            flag = '1s'
        if flag == '1s' and i == n-1:
            tmp[1] = i+1
            ans.append(tmp)
    else:
        if flag == '1s':
            tmp[1] = i
            ans.append(tmp)
            flag = '0'
if S[0] == '0':
    ans.insert(0, [1, 1])
if S[n-1] == '0':
    ans.append([n, n])
# print(ans)
anser = []
if k >= len(ans):
    print(n)
else:
    for i in range(len(ans)):
        if i+k > len(ans)-1:
            break
        else:
            anser.append(ans[i+k][1]-ans[i][0]+1)
    print(max(anser))