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=input()
bef=S[0]
idx=[0]
for i in range(1,N):
    if S[i]!=bef:
        idx.append(i)
        bef=S[i]
ans=0
for i,x in enumerate(idx):
    if x==0 and S[0]=="0":
        end=i+2*K
        if end>=len(idx):
            end=N
        else:
            end=idx[end]
        ans=max(ans,end-x)
    if S[x]=="1":
        end=i+2*K+1
        if end>=len(idx):
            end=N
        else:
            end=idx[end]
        ans=max(ans,end-x)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
Sinput=input()
S=[]
for i in range(len(Sinput)):
    S.append(int(Sinput[i]))
Smax=0
human=[]
humansum=[0]
counter=1
if S[0]==0:
    human.append(0)
for i in range(1,len(S)):
    if S[i-1]!=S[i]:
        human.append(counter)
        counter=1
    else:
        counter+=1
human.append(counter)
if len(human)%2==0:
    human.append(0)

#奇数番目が０の個数、偶数番目が１の個数
for i in range(len(human)):
    humansum.append(human[i]+humansum[i])

if K>=len(human)//2:
    ans=len(S)
else:
    for i in range(len(human)//2-K+1):
        Smax = max(Smax,humansum[(i+K)*2+1]-humansum[i*2])
    ans=Smax
print(ans)

Submission status: Accepted

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

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

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

t = [0]
for i in range(len(nums)):
    t.append(t[i] + nums[i])

ans = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(i + 2 * k + 1, len(nums))

    ans = max(ans, t[right] - t[left])

print(ans)

Submission status: Accepted

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

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

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

ans = 0
left = 0
right = 0
tmp = 0

for i in range(0, len(nums), 2):
    next_left = i
    next_right = min(i + 2 * k + 1, len(nums))

    while (left < next_left):
        tmp -= nums[left]
        left += 1

    while (right < next_right):
        tmp += nums[right]
        right += 1

    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
'''
Sを連続する値の数のリストに変換
(ただし、左右端は必ず1が0個以上存在するとする)
S='0111010011' -> A=[0,1,3,1,1,2,2]

K=1なら、
sum(A[0:3]), sum(A[2:5]), sum(A[4:7])のmaxが答え
'''

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

# Sを0,1の区切りで分解したときのそれぞれの長さ
A = []
cur = S[0]
c = 0
for s in S[1:] + '*':
    c += 1
    if cur != s:
        cur = s
        A.append(c)
        c = 0

# 先頭、末尾が"0"のときは0を追加
if S[0] == '0':
    A = [0] + A
if S[-1] == '0':
    A = A + [0]

# Aの累積値を計算
AA = [None] * len(A)
AA[0] = A[0]
for i in range(1, len(A)):
    AA[i] = AA[i-1] + A[i]

# Aの偶数番号インデックス(0始まり)から計算される
# 2K+1個の連続する要素の和の最大値が求める値
if len(A) <= 2 * K + 1:
    print(sum(A))
else:
    m = 0
    i = 0
    while i + 2*K <= len(A):
        # p: sum(A[i: i+2*K+1])
        p = AA[i+2*K] - (AA[i-1] if i > 0 else 0)
        m = max(m, p)
        i += 2
    print(m)

Submission status: Accepted

Solution code:
#長さN 試行回数K
N, K = map(int, input().split())
#配列S
S = input()
A = []
if S[0] == '0':
  A.append(0)
  
i = 0
#次に違う数字が出てくるまでをカウント
while i < len(S):
  j = i
  while j < len(S) and S[i] == S[j]:
    j += 1
  A.append(j - i)
  i = j
#print(A)  
ans = 0
tot = 0
r = 0
for l in range(len(A)):
  while r < len(A) and r - l < 2 * K + 1:
    tot += A[r]
    r += 1
  if l % 2 == 0:
    ans = max(ans, tot)
  if r == l:
    r += 1
  else:
    tot -= A[l]
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from collections import deque

N, K = [int(x) for x in input().split()]
blocks = [[tp, list(people)] for tp, people in groupby(input())]

ans = 0
cur = 0
stand = 0
target = deque()

for tp, people in blocks:
    if tp == '0':
        stand += 1
        if stand > K:
            removed = target.popleft()
            cur -= len(removed[1])
            if removed[0] == '1' and len(target) > 0:
                removed = target.popleft()
                cur -= len(removed[1])

    target.append([tp, people])
    cur += len(people)
    ans = max(ans, cur)

print(ans)

Submission status: Accepted

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

l = 0
count = 0

ans = 0
for r in range(N):
    if S[r] == '0':
        if r == 0 or S[r - 1] == '1':
            count += 1
    if count > K:
        while S[l] == '1':
            l += 1
        while S[l] == '0':
            l += 1
        count -= 1
    ans = max(ans, r - l + 1)

print(ans)

Submission status: Accepted

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+10**5)
# 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: Accepted

Solution code:
import sys
import itertools
n, k = map(int, sys.stdin.readline().split())
s = [int(string) for string in input()]

tmp = []
flag = s[0]
cnt = 1

if s[0] == 0:
    tmp.append(0)
for i in range(1, n):
    if flag == s[i]:
        cnt += 1
    else:
        tmp.append(cnt)
        cnt = 1
        flag = 1 - flag
tmp.append(cnt)
if s[-1] == 0:
    tmp.append(0)

ruisekiwa = list(itertools.accumulate(tmp))
ans = 0
ruisekiwa.insert(0, 0)
for left in range(0, len(ruisekiwa), 2):
    right = left + 2*k+1
    if len(ruisekiwa) <= right:
        right = len(ruisekiwa)-1
    ans = max(ans, ruisekiwa[right] - ruisekiwa[left])

print(ans)

Submission status: Accepted

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+1)//2<=K:
    print(__list[-1])
else:
    print(max([__list[2*i+2*K+1]-__list[2*i] for i in range((C+1)//2-K)]))

Submission status: Accepted

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

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n,k = li()
s = ns()

cur = "1"
cum = [0]

for i, si in enumerate(s):
    if cur != si:
        cur = si
        cum.append(i)

cum.append(n)

if cur == "0":
    cum.append(n)


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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

## pesmistic input (8916 ms)
#N = 100000
#K = 10000
#S = '10'*50000

## make 'next_lst'
## S='1100010000' --> next_lst=[2,3,1,4,1]
next_lst = []
pre_state = S[0]
cnt = 1
for i in range(1,len(S)):
  if S[i] == pre_state:
    cnt += 1
  else:
    next_lst.append(cnt)
    pre_state = S[i]
    cnt = 1
else:
  next_lst.append(cnt)
if S[0] == '0':
  next_lst = [0] + next_lst
if S[-1] == '0':
  next_lst = next_lst + [0]


if len(next_lst) <= 2*K+1:
  ans = sum(next_lst)
  print(ans)
  exit()

## 配列の区間和はcumsumで累積和を取ってその差分を取るほうが速い
ans = 0
lst = np.cumsum(np.array([0]+next_lst))
for i in range((len(next_lst)-2*K+1)//2):
  var = lst[2*i+2*K+1] - lst[2*i]
  ans = max(ans, var)

print(ans)

Submission status: Accepted

Solution code:
def intinput(): return map(int,input().split())

n,k=intinput()
s=input()
x=1
cnt=0
lis=[]
for i in range(n):
    if s[i]==str(x):
        cnt+=1
    else:
        lis.append(cnt)
        cnt=1
        x ^= 1
lis.append(cnt)
if len(lis)%2==0:
    lis.append(0)
x=[0]
for i in range(len(lis)):
    x.append(x[i]+lis[i])
l = 2*k+1
ans=0
for i in range(0,len(x),2):
    left=i
    right=min(len(x)-1,l+i)
    tmp = x[right]-x[left]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, K = map(int, input().split())
S = input()[:-1]

L = [0]
L_index = [0]
prev = ""
for c in S:
    if c == prev:
        L[-1] += 1
    else:
        prev = c
        L.append(1)
        L_index.append(c)

L_acc = list(accumulate(L))

ans = 0
len_L = len(L)
for s in range(1, len_L):
    if L_index[s] == "0":
        right_end = min(s+K*2-1, len_L-1)
    else:
        right_end = min(s+K*2, len_L-1)
    ans = max(ans, L_acc[right_end]-L_acc[s-1])
print(ans)

Submission status: Accepted

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

t = []
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))

if len(t) > 0:
    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)
        if t[-1][1] != n:
            tmp = n - t[-k][0]
            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)
        if t[-1][1] != n:
            tmp = n - t[-min(k,len(t))][0]
            res = max(res, tmp)

    print(res + 1)
else:
    print(n)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
x = [0]
for i in range(n - 1):
    if s[i:i + 2] in ['01', '10']:
        x.append(i + 1)
y = []
for i in range(len(x)):
    idx = i + 2 * k
    if s[x[i]] == '0':
        if i > 0:
            continue
    else:
        idx += 1

    if idx < len(x):
        y.append(x[idx] - x[i])
    else:
        y.append(n - x[i])
        break
print(max(y))

Submission status: Accepted

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

# print(n, k, s)

prevcCt = 0 # 前に連続逆立ちの数
nextCnt = 0 # 後ろに連続逆立ちの数

# "00010" ⇒ [-3, 1, -1]のような配列に変換

val = 0
vals = []
for i in range(len(s)):
	if s[i] == "0":
		val -= 1
	else:
		val += 1

	#print(i, val, s[i], s[i+1])
	# print(i,len(s))
	if i == len(s) - 1 or s[i] != s[i+1]:
		vals.append(val)
		val = 0

#print(vals)

#操作しやすいようにマイナス要素が偶数になるように先頭に0を追加
if vals[0] < 0:
	vals.insert(0,0)

vals.append(0)
vals.append(0)

#print(vals)

vals = list(map(abs, vals))
#print(vals)


# K回操作できるということは連続した2k+1個の要素の最大値を求めればよい
max = 0

loopCnt = len(vals) - k
if  loopCnt < 1:
	loopCnt = 1


# 最初の要素をベースとする
sumVal = sum(vals[0:2*k + 1])
max = sumVal

# print(vals)
# print(max)

for i in range(loopCnt):
	#print(i, len(vals), k)
	# 偶数の時だけ判定
	if i%2 == 0 and i>0:
		# 外れた要素の合計値
		outVal = sum(vals[i-2:i])
		# 新たに加わった要素の合計値
		inVal = sum(vals[i + 2*k -1:i + 2*k + 1])
	
		sumVal = sumVal - outVal + inVal

		#print(i, vals[i-2:i], outVal, vals[i + 2*k -1:i + 2*k + 1], inVal, sumVal)
		# print(vals[i:i + 2*k + 1])

		#sumVal = sum(vals[i:i + 2*k + 1])
		# for e in vals[i:i + 2*k + 1]:
		# 	sumVal += abs(e)
		if sumVal > max:
			max = sumVal

print(max)

Submission status: Accepted

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

now = 1
cnt = 0
for i in range(N):
    if S[i] == now:
        cnt += 1
    else:
        nums.append(cnt)
        cnt = 1
        now = 1 - now
if cnt != 0:
    nums.append(cnt)
    
if S[N-1] == 0:
    nums.append(0)

sums = [0] * (len(nums) + 1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]

Add = 2 * K + 1
res = 0
for left in range(0, len(nums), 2):
    right = left + Add
    if right >= len(sums):
        right = len(sums) - 1
    res = max(res, sums[right] - sums[left])

print(res)

Submission status: Accepted

Solution code:
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############


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

nums = []
now = 1 # 今見ている数
cnt = 0
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1

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

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

ruiseki = [0]

for i in range(1, len(nums)+1):
    ruiseki.append(ruiseki[i-1] + nums[i-1])

ans = 0

for i in range(0, len(nums), 2):
    left = i
    right = min(i+2*K+1, len(nums))
    ans = max(ans, ruiseki[right] - ruiseki[left])

print(ans)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]
stands = [int(x) for x in input()]

wl = wr = 0
a = 1 - stands[0]
maxhand = 1

while wr < n-1:
    # extend to right
    if stands[wr + 1] == 1:
        wr += 1
    else: # right extends to 0
        if stands[wr] == 0:
            wr += 1
        else: # current rightmost is 1
            if (a+1 <= k): # use a flip anyway
                a += 1
                wr += 1
            else: # retract from the left
                # update counter
                if (wr - wl + 1) > maxhand:
                    maxhand = wr - wl + 1
                while stands[wl] == 1:
                    wl += 1
                while stands[wl] == 0:
                    wl += 1
                a -= 1

if (wr - wl + 1) > maxhand:
    maxhand = wr - wl + 1

print(maxhand)

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
s = input()
sList = [] #連続する1の数、0の数、1の数...と格納するリスト
switch = int(s[0])
num = 1
if int(s[0]) == 0:
  sList.append(0)
if n > 1:
  for i in range(1, n):
    if int(s[i]) == switch:
      num += 1
    else:
      sList.append(num)
      num = 1
      switch = int(s[i])
sList.append(num)
if len(sList) // 2 < k: #全部ひっくり返せる
  print(n)
  sys.exit()
elif len(sList) % 2 == 0: #最後が0の数で終わっている場合、1の数で終わらせる
  sList.append(0)
  
s = sum(sList[0:2*k+1])
sMax = s

for i in range(1, (len(sList)-2*k) // 2 + 1): #リストの2k+1個の部分和のうち、最大のものが答え
  s += - sList[2*i-2] - sList[2*i-1] + sList[2*i+2*k] + sList[2*i+2*k-1]
  if sMax < s:
    sMax = s
    
print(sMax)

Submission status: Accepted

Solution code:
n,k=[int(i) for i in input().split()]
s=input()
 
ope=s[0]
cnt=1
l=[];
if s[0]=='0':
	l.append(0)
for i in range(1,len(s)):
	if s[i]==ope:
		cnt+=1
	else:
		l.append(cnt)
		ope=s[i]
		cnt=1
l.append(cnt)
 
if s[len(s)-1]=='0':
	l.append(0)
	
start=0
end=2*k
 
max_sum=sum(l[start:end+1])
cur_sum=max_sum
start+=2
end+=2
while end<len(l):
    cur_sum=cur_sum-l[start-2]-l[start-1]+l[end-1]+l[end]
    max_sum=max([max_sum,cur_sum])
    start+=2
    end+=2
print(max_sum)

Submission status: Accepted

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

q = []
tmp = 0

if len(s) == 1:
    if k >= 1 or s[0] == '1':
        print(1)
    else:
        print(0)
else:
    if s[0] == '0':
        q.append(0)
    for i in range(len(s)):
        if i == 0:
            tmp += 1
        elif i != len(s)-1:
            if s[i] == s[i-1]:
                tmp += 1
            else:
                q.append(tmp)
                tmp = 1
        else:
            if s[i] == s[i-1]:
                tmp += 1
                q.append(tmp)
            else:
                q.append(tmp)
                q.append(1)
    if s[len(s)-1] == '0':
        q.append(0)

    tmp = 0
    max_k = min(math.ceil(len(q)/2), k)
    """
    if len(q) == 1:
        if s[0] == '0' and k == 0:
            ans.append(0)
        else:
            ans.append(q[0])

    #先頭、末尾が0の時
    elif s[0] == '0' and len(q) % 2 == 1:
        for i in range(1, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))
        ans.append(sum(q[:+2*max_k]))
        ans.append(sum(q[-2*max_k+1:]))
    #先頭0末尾1
    elif s[0] == '0' :
        for i in range(1, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))
        ans.append(sum(q[:2*max_k]))
    #先頭1末尾0
    elif len(q) % 2 == 0:
        for i in range(1, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))
        ans.append(sum(q[-2*max_k+1:]))
    else:
        if max_k == math.ceil(len(q)/2):
            max_k -= 1
        for i in range(0, len(q) - 2 * max_k, 2):
            ans.append(sum(q[i:i+2*max_k+1]))

    """
    #先頭1末尾1
    left = 0
    right = 0
    tmp = 0
    ans = 0
    for i in range(0, len(q), 2):
        next_left = i
        next_right = min(i + 2 * k+1, len(q))

        while (next_left > left):
            tmp -= q[left]
            left += 1

        while (next_right > right):
            tmp += q[right]
            right += 1

        ans = max(ans, tmp)
    print(ans)

Submission status: Accepted

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

    ans = sum(lis[0][0:K]) + sum(lis[1][0:K+1])
    foo = ans
    for i in range(len(lis[0])-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: Accepted

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

ans = 0
l = 0
r = 0
count = 1 if s[0]=='0' else 0

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

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(input())
cnt = 1
k = {}
if S[0] == "0":
    k[cnt] = [0]
    cnt += 1


flg = False
for i in range(N):
    if S[i] == '1':
        if flg == False :
            k[cnt] = []
        k[cnt].append(i)
        flg = True
    else:
        if flg == True:
            flg = False
            cnt += 1

if S[-1] == '0':
    k[cnt] = [N-1]

if '0' not in S:
    print(len(S))
    exit()
if N == 1:
    print(1)
    exit()
if cnt - K + 1 < 0:
    print(len(S))
    exit()

ans = 0
for i in range(1,cnt - K+1):
    ans = max(ans , k[i+K][-1]-k[i][0] + 1)
print(ans)

Submission status: Accepted

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

ans = 0
r = 0
l = 0
count = 1 if s[0]=='0' else 0

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

print(ans)

Submission status: Accepted

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)
    if b_int.n > 1:
        res = max(res,max(
            b_int(i, i+2*K+1) for i in range(1, b_int.n) if i%2 == 1
        ))
    print(res)

Submission status: Accepted

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

tank = []
counter = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        tank.append(counter)
        counter = 0
    counter += 1
    if i == N-1:
        tank.append(counter)

if S[0] == '0' and (len(tank)+1)//2 <= K:
    print(N)
    exit()
if len(tank)//2 <= K and S[0] == '1':
    print(N)
    exit()

ans = 0
res = 0
if S[0] == '0':
    for i in range(2*K):
        res += tank[i]
    ans = res
    for i in range(2*K, len(tank)):
        if i == 2*K:
            res -= tank[0]
        elif i%2 == 0:
            res = res - tank[i-2*K] - tank[i-2*K-1]
        res += tank[i]
        ans = max(ans, res)
else:
    for i in range(2*K+1):
        res += tank[i]
    ans = res
    for i in range(2*K+1, len(tank)):
        if i % 2 == 1:
            res = res - tank [i-2*K-1] - tank[i-2*K]
        res += tank[i]
        ans = max(ans, res)

print(ans)

Submission status: Accepted

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(a[-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)

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, K = LI()
    S = SI().strip()

    searching = 1
    count = [0]
    head = 0
    for i in range(N):
        if int(S[i]) == searching:
            count[head] += 1
        else:
            searching = (searching+1)%2
            head += 1
            count.append(1)
    if len(count)//2 <= K:
        print(N)
        sys.exit()

    count.append(0)

    current_sum = sum(count[0:2*K+1])
    max_length = current_sum
    try:
        for k in range(1, N):
            if 2*k+2*K > len(count): break
            current_sum = current_sum - count[2*k-2] - count[2*k-1] + count[2*k+2*K-1] + count[2*k+2*K]
            max_length = max(current_sum, max_length)
    except:
        pass
    print(max_length)

main()

Submission status: Accepted

Solution code:
def sub():
    N, K = [int(e) for e in input().split(" ")]
    ss = [int(e) for e in input()]
    # if len(set(ss)) == 1:
    #     print(len(ss))
    #     return

    dd = [ss[i+1] - ss[i] for i in range(N-1)]
    idd = [0] + [i+1 for i, d in enumerate(dd) if d != 0]
    # print(idd)
    maxScore = 0
    for i in range(len(idd)):
        if ss[idd[i]] == 0:
            ni = i + 2*K
            if ni < len(idd):
                score = idd[ni] - idd[i]
            else:
                score = N - idd[i]
            if score > maxScore:
                maxScore = score
        else:
            ni = i + 2*K + 1
            if ni < len(idd):
                score = idd[ni] - idd[i]
            else:
                score = N - idd[i]
            if score > maxScore:
                maxScore = score
        
    print(maxScore)

sub()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
#しゃくとり法
left = 0
count,ans = 0,0

for right in range(n):
    if s[right] =="0":
        if right==0 or s[right-1]=="1":
            count += 1
    if count > k:
        while s[left] == "1":
            left += 1
        while s[left] == "0":
            left += 1
        count -= 1
    ans = max(ans,right-left+1)
print(ans)

Submission status: Accepted

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

a = []
x = 0 #1の個数
y = 0 #0の個数
if s[0] == 0:
  a.append(0)
for i in range(n):
  if s[i] == 1:
    x += 1
  else:
    y += 1
  if x > 0 and y > 0:
    if s[i] == 0:
      a.append(x)
      x = 0
    else:
      a.append(y)
      y = 0
if x > y:
  a.append(x)
else:
  a.append(y)
  a.append(0)


m = len(a)
left=[0]*(m+1)
right=[0]*(m+1)

for i in range(m):
  left[i+1] = left[i] + a[i]
for i in range(m):
  right[m-i-1] = right[m-i] + a[m-i-1]

ans = 0
if m%2 == 0:
  r = int(m/2) + 1
else:
  r = int((m+1)/2) 
#print(r,a,right,left)
for i in range(r):
  if 2*i+2*k+1 <= m:
    x = left[2*i+2*k+1]-left[2*i]
  else:
    x = left[-1] - left[2*i]
  if ans < x:
    ans = x
print(ans)

Submission status: Accepted

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


# 1と0の切り替わり点を全探索
change_point = [0]
for i in range(N-1):
    if S[i+1] != S[i]:
        change_point.append(i+1)


ans_candidates = []
l = len(change_point)
for i in range(l):
    if i+2*K < l and S[change_point[i]] == '0':
        ans_candidates.append(change_point[i+2*K]-change_point[i])
    elif i+2*K+1 < l and S[change_point[i]] == '1':
        ans_candidates.append(change_point[i+2*K+1]-change_point[i])
    else:
        ans_candidates.append(N-change_point[i])

print( max(ans_candidates) )

Submission status: Accepted

Solution code:
def main():
    n, k = [int(i) for i in input().split()]
    s = [int(i) for i in list(input())]
    table = []
    now = 1
    cnt = 0
    for i in range(n):
        if s[i] == now:
            cnt += 1
        else:
            table.append(cnt)
            cnt = 1
            now ^= 1 # 0　と 1 の切り替え
    if cnt != 0:
        table.append(cnt)
    if len(table)%2 == 0:
        # 奇数で終わらせれば、1 で終わったことになる
        table.append(0)
    ans = 0
    l = 0
    d = min(len(table), 2*k+1)
    r = l + d
    tmp = sum(table[l:r])
    while r <= len(table):
        ans = max(ans, tmp)
        if l < len(table):
            tmp -= table[l]
        l += 1
        if l < len(table):
            tmp -= table[l]
        l += 1
        r += 1
        if r <= len(table):
            tmp += table[r-1]
        r += 1
        if r <= len(table):
            tmp += table[r-1]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

L = []
t = S[0]
counter = 1
for i in range(1, N):
    if t == S[i]:
        counter += 1
    else:
        L.append((counter, t))
        t = S[i]
        counter = 1
        
L.append((counter, t))

P = [0] * (len(L) + 1)
for i in range(len(L)):
    P[i + 1] = P[i] + L[i][0]
    
ma = 0
t = K * 2 + 1
for i in range(len(P) - 1):
    if L[i][1] == '0':
        index = min(i + t - 1, len(P) - 1)
        ma = max(ma, P[index] - P[i])
    else:
        index = min(i + t, len(P) - 1)
        ma = max(ma, P[index] - P[i])
    
print(ma)

Submission status: Accepted

Solution code:
[n, k] = [int(i) for i in input().split()]
s = input()

l = []
cnt = 1
if s[0] == '0':
    l.append(0)
for i in range(len(s) - 1):
    if (s[i] == s[i + 1]):
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
l.append(cnt)
if s[-1] == '0':
    l.append(0)
m = (len(l)) // 2
sum1 = []
temp = sum(l[0:min(2 * m + 1, 2 * k + 1)])
sum1.append(temp)
if (m > k):
    for i in range(1, m - k + 1):
        temp += l[2 * (k + i) - 1] + l[2 * (k + i)] - l[2 * i - 1] - l[2 * i - 2] 
        sum1.append(temp)
print(max(sum1))