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:
from itertools import *

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

nums=[]
if S[0]=="0":
  nums.append(0)
i=0
while i<len(S):
  j=i
  while j<len(S) and S[j]==S[i]:
    j+=1
  nums.append(j-i)
  i=j
if S[-1]=="0":
  nums.append(0)

sums=[0]+list(accumulate(nums))

ans=0
for left in range(0,len(sums),2):
  right=left+K*2+1
  if len(sums)<=right:
    right=len(sums)-1
  ans=max(ans,sums[right]-sums[left])

print(ans)

Submission status: Accepted

Solution code:
from itertools import *

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

C=[]
now=1
cnt=0
for i in range(N):
  if S[i]==str(now):
    cnt+=1
  else:
    C.append(cnt)
    now=1-now
    cnt=1
C.append(cnt)
if len(C)%2==0:
  C.append(0)

S=[0]+list(accumulate(C))

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

print(ans)

Submission status: Accepted

Solution code:
import sys
N,K = map(int,input().split())
S = input()
l_edge = []
r_edge = []

if S[0] == '0':
    l_edge.append(0)
for i in range(N):
    # iは0ブロックの左端になっているか
    if i > 0 and (S[i-1] == '1' and S[i] == '0'):
        l_edge.append(i)
    # iは0ブロックの右端になっているか
    if i < N-1 and (S[i] == '0' and S[i+1] == '1'):
        r_edge.append(i)
if S[-1] == '0':
    r_edge.append(N-1)

assert len(l_edge) == len(r_edge)

Block = len(l_edge)
if Block <= K:
    print(N)
    sys.exit()

ans = 0
for leftblock in range(Block):
    # l := 「1の列の左端」のSにおけるインデックス
    if leftblock == 0:
        l = 0
    else:
        l = r_edge[leftblock-1]+1
        assert l>0

    rightblock = max(leftblock+K-1,0)
    if rightblock >= Block-1:
        r = N-1
    else:
        r = l_edge[rightblock+1]-1
    
    '''
    print('----')
    print(leftblock,rightblock)
    print(l,r)
    '''
    ans = max(ans,r-l+1)

print(ans)

Submission status: Accepted

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

    # Cumulative Sum
    cs = [0]
    now = 1
    cnt = 0
    for i in s:
        if i == now:
            cnt += 1
        else:
            cs.append(cs[-1] + cnt)
            now = i
            cnt = 1
    cs.append(cs[-1] + cnt)
    if now == 0:
        cs.append(cs[-1])

    if len(cs) - 2*k - 1 < 1:
        print(n)
    else:
        ans = 0
        for i in range(0, len(cs)-2*k-1, 2):
            cnt = cs[i + 2*k + 1] - cs[i]
            if ans < cnt:
                ans = cnt
        print(ans)

main()

Submission status: Accepted

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

nums = []
if s[0] == '0':
    nums.append(0)
i = 0
while i < n:
    j = i
    while j < n and s[j] == s[i]:
        j += 1
    nums.append(j-i)
    i = j
if s[-1] == '0':
    nums.append(0)

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

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

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

N,K=mint()
S=input()
j=0
tmp='1'
while j<N:
    if tmp=='1' and S[j]=='0':
        if K==0:
            j-=1
            break
        else:
            K-=1
    tmp=S[j]
    j+=1
if j==N:
    print(j)
    exit()
ans=j+1
i=-1
while True:
    if j==N-1:
        print(ans)
        exit()
    i+=1
    while True:
        if i==N-1 or (S[i]=='0' and S[i+1]=='1'):
            break
        i+=1
    j+=1
    while True:
        if j==N-1 or (S[j]=='1' and S[j+1]=='0'):
            break
        j+=1
    ans=max(ans,j-i)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
Nums = []
now = 1 # 今見ている数
cnt = 0 # nowがいくつ並んでいるか
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now   # 0と1を切り替えるときの計算 now ^= 1
        cnt = 1
if cnt != 0:
    Nums.append(cnt)
# 1-0-1-0-1-0-1 って感じの配列が欲しい
# 1-0-1-0-1-0 みたいに0で終わっていたら適当に1つ足す
if len(Nums) % 2 == 0:
    Nums.append(0)

Add = 2 * K + 1
# 累積和を作る
# 0 1 2 3 4 5 6
#  0 1 2 3 4 5
sum = [0] * (len(Nums) + 1)
for i in range(len(Nums)):
    sum[i + 1] = sum[i] + Nums[i]
ans = 0
# 1-0-1... の1から始めるので、偶数番目だけ見る
for i in range(0, len(Nums), 2):
    # 次のleft, rightを計算する [left, right)
    left = i
    right = min(i + Add, len(Nums))
    tmp = sum[right] - sum[left]
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

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

#run length encoding
for char in S:
	if bef == char:
		count += 1
	else:
		lst.append(count)
		count = 1
		bef = char
		
lst.append(count)

if S[-1] == "0":
	lst.append(0)
	
# 並び方は0101...となるか10101...となるか
l = len(lst)
if l <= 2*K + 1:
	print(N)
	exit()
	
tmp = sum(lst[:2*K+1])
ans = tmp
d = 2*K + 1
for i in range(2*K+1, l, 2):
	tmp -= lst[i-d] + lst[i-d+1]
	tmp += lst[i] + lst[i+1]
	ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

# \n
def input():
    return sys.stdin.readline().rstrip()


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

    l = []
    down = 0  # "0"
    up = 0  # "1"
    flag = int(S[0])
    if not flag:
        l.append(0)
    for i in range(N):

        if int(S[i]) == 1:
            up += 1
            if down:
                l.append(down)
                down = 0
        if int(S[i]) == 0:
            down += 1
            if up:
                l.append(up)
                up = 0
    if up:
        l.append(up)
    else:
        l.append(down)

    if len(l)<=2*K+1:
        print(N)
        exit()
    total = sum(l[:2*K+1])
    ans =total
    flag =1
    csum=list(itertools.accumulate(l))
    for i in range(2,len(l) - 2 * K +1,2):
        right =min(i+2*K,len(l)-1)
        ans = max(ans, csum[right] - csum[i-1])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
lst = []
bef = s[0]
if bef == "0":
    lst.append(0)
cnt = 0
for ss in s:
    if bef == ss:
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1
        bef = ss
lst.append(cnt)
if s[-1] == "0":
    lst.append(0)

l = len(lst)
if l <= k * 2 + 1:
    print(n)
    exit()
tmp = sum(lst[:2 * k + 1])
ans = tmp
d = 2 * k + 1
for i in range(2 * k + 1, l, 2):
    tmp -= lst[i - d] + lst[i - d + 1]
    tmp += lst[i] + lst[i + 1]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s = input()
ls = []
i = 0
c = 0
while i < N and s[i] == "1":
    c += 1
    i += 1
if i==N:
    print(N)
    exit()
while i < N:
    l = c
    c = 0
    while i < N and s[i] == "0":
        c += 1
        i += 1
    m = c
    c = 0
    while i < N and s[i] == "1":
        c += 1
        i += 1
    r = c
    ls.append((l,m,r))
K = min(K, len(ls))
from itertools import accumulate
acc = list(accumulate([0]+ls, lambda x,y:x+y[1]+y[2]))
ans = 0
for i in range(len(ls)-K+1):
    ans = max(ans, acc[i+K]-acc[i]+ls[i][0])
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from numpy import *
n,k = map(int,input().split())
k = 2*k+1
s = input()
x = [0]*(s[0]=="0")+[len(list(v))for k,v in groupby(s)]+[0]*(s[-1]=="0")
x1 = array(x[k:])
x2 = array(x[:-k])
x3 = sum(x[:k])
y = [x3]+list(x3+cumsum(x1-x2))
print(max(y[::2]))

Submission status: Accepted

Solution code:
import sys
bbn=1000000007
	
#+++++
		
def main2():
	n, k = map(int, input().split())
	sl = input()
	dd=[]
	ddv=[]
	left= sl[0]
	count=0
	pre=left
	for c in sl:
		if c == pre:
			count+=1
		else:
			dd.append(count)
			ddv.append(pre)
			pre=c
			count=1
	dd.append(count)
	ddv.append(pre)
	
	pa(ddv)
	if k == 0:
		return max([v for v,c in zip(dd,ddv) if c == '1'])
	
	ll=[]
	for i,c in zip(dd,ddv):
		if c == '0':
			pass
			
def main():
	n, k = map(int, input().split())
	sl = input()
	al=[]
	if sl[0]=='0':
		al.append(0)
	p=sl[0]
	count=1
	for c in sl[1:]:
		if c == p:
			count+=1
		else:
			al.append(count)
			count=1
			p=c
	else:
		al.append(count)
		if sl[-1]=='0':
			al.append(0)
			
	#pa(al)
	
	if 2*k+1 >= len(al):
		print(n)
		return 
	
	ret = al[0]
	for i in range(k):
		ret += al[2*i+1]
		ret += al[2*i+2]
	#pa(ret)
	rs=ret
	for i in range(k, (len(al)//2)):
		rs += al[2*i+1]
		rs += al[2*i+2]
		rs -= al[2*(i-k)+1]
		rs -= al[2*(i-k)]
		ret = max(rs, ret)
		#pa(rs)
	print(ret)
		
			
			
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

# count sequence man and memo the cnt in group
man_groups = []
same_cnt = 0
last_man = ""
for i in range(N):
    cur_man = S[i]
    if cur_man != last_man:
        if same_cnt > 0:
            if last_man == "0":
                same_cnt *= -1
            man_groups.append(same_cnt)
        same_cnt = 1
    else:
        same_cnt += 1
    last_man = cur_man
if same_cnt > 0:
    if last_man == "0":
        same_cnt *= -1
    man_groups.append(same_cnt)

# count max sequence man from evey pos
sum_list = []
end_pos = 2 * K if man_groups[0] > 0 else 2 * K - 1
max_man_groups_idx = len(man_groups) - 1
end_pos = min(end_pos, max_man_groups_idx)
last_max = sum(map(abs, man_groups[0: end_pos + 1]))
sum_list.append(last_max)

start_pos = 2 if man_groups[0] > 0 else 1
for i in range(start_pos, len(man_groups), 2):
    if end_pos >= max_man_groups_idx:
        break
    for j in range(2):
        idx = i - j - 1
        if idx >= 0:
            last_max -= abs(man_groups[idx])
    for j in range(2):
        end_pos += 1
        if end_pos <= max_man_groups_idx:
            last_max += abs(man_groups[end_pos])
    sum_list.append(last_max)

#print(man_groups)
#print(sum_list)
print(max(sum_list))

Submission status: Accepted

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

# count sequence man and memo the cnt in group
man_groups = []
same_cnt = 0
last_man = ""
for i in range(N):
    cur_man = S[i]
    if cur_man != last_man:
        if same_cnt > 0:
            if last_man == "0":
                same_cnt *= -1
            man_groups.append(same_cnt)
        same_cnt = 1
    else:
        same_cnt += 1
    last_man = cur_man
if same_cnt > 0:
    if last_man == "0":
        same_cnt *= -1
    man_groups.append(same_cnt)

# count max from evey
sum_list = []
end_pos = 2 * K if man_groups[0] > 0 else 2 * K - 1
end_pos = min(end_pos, len(man_groups) - 1)
last_max = sum(map(abs, man_groups[0: end_pos + 1]))
sum_list.append(last_max)
for i in range(1, len(man_groups)):
    if end_pos >= len(man_groups) - 1:
        break
    last_max -= abs(man_groups[i - 1])
    if man_groups[i] > 0:
        next_end_pos = min(end_pos + 2, len(man_groups) - 1)
        man_groups_to_add = man_groups[end_pos + 1: next_end_pos + 1]
        last_max += sum(map(abs, man_groups_to_add))
        end_pos = next_end_pos
    sum_list.append(last_max)

#print(sum_list)
#print(sum_list)
print(max(sum_list))

Submission status: Accepted

Solution code:
from itertools import groupby

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

grouped = groupby(s)

res = []

if s[0] == '0':
	res.append(0)

for l,v in grouped:
	res.append( (len(list(v))) )

if s[len(s)-1] == '0':
	res.append(0)

now = 0
ans = 0
for i in range(min(len(res),2*k+1)):
	now += res[i]

ans = max(ans,now)

for i in range(2*k+1,len(res),2):
	now -= res[i-2*k-1]
	now -= res[i-2*k]

	now += res[i]
	now += res[i+1]

	ans = max(ans,now)

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

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

grouped = groupby(s)

res = []

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

for l,v in grouped:
	res.append( (l,len(list(v))) )

if s[len(s)-1] == '0':
	res.append((1,0))

now = 0
ans = 0
for i in range(min(len(res),2*k+1)):
	now += res[i][1]

ans = max(ans,now)

for i in range(2*k+1,len(res),2):
	now -= res[i-2*k-1][1]
	now -= res[i-2*k][1]

	now += res[i][1]
	now += res[i+1][1]

	ans = max(ans,now)

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

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


grouped = groupby (s)
res = []

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

for l,v in grouped:
	res.append( (l,len(list(v))) )

if s[len(s)-1] == '0':
	res.append((1,0))

#for d in res:
	#print(d)

if len(res) <= 2*k + 1:
	ans = 0;
	for d in res:
		ans += d[1];

	print(ans)
	exit()

now = 0
ans = 0
for i in range(2*k+1):
	now += res[i][1]

ans = max(ans,now)

for i in range(2*k+1,len(res),2):
	now -= res[i-2*k-1][1]
	now -= res[i-2*k][1]

	now += res[i][1]
	now += res[i+1][1]

	ans = max(ans,now)

print(ans)

Submission status: Accepted

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

S = S + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

# 立った人の連続の数
if (S[0] == '0'):
    stand = 1
else:
    stand = 0

L = 0
R = 0

# 尺取り法
while (R < N):
    # 右端を進めることが可能（立った人の連続の数がK以下）なら、右端を進める
    if (stand <= K):
        # 立った人の連続の数が増えるなら1足す
        if (S[R] == '1' and S[R + 1] == '0'):
            stand += 1
        # 答えの更新
        ans = max(ans, R - L + 1)
        R += 1
    # 進められない場合、左端と右端が同じなら両者を進める
    # 左端が右端を追い越さないための処理
    elif (L == R):
        L += 1
        R += 1
    # それ以外は左端のみを進める
    else:
        # 立った人の連続の数が減るなら1減らす
        if (S[L] == '0' and S[L + 1] == '1'):
            stand -= 1
        L += 1
        # 左端のみを進めた場合は答えを更新し得ない

print(ans)

Submission status: Accepted

Solution code:
def main():
	N, K = [int(x) for x in input().split(" ")]
	S = list(input())
	cnt = [0] # idx = 0, 2, 4 ... -> handstand
	a = 0
	for i in range(len(S)):
		if S[i] == "0":
			if a % 2 == 0:
				a += 1
				cnt.append(1)
			else:
				cnt[-1] += 1
		elif S[i] == "1":
			if a % 2 == 0:
				cnt[-1] += 1
			else:
				a += 1
				cnt.append(1)
	if S[-1] == "0":
		cnt.append(0)

	if K >= (len(cnt) - 1) / 2:
		print(N)
		return 0

	T = [sum(cnt[:(2 * K + 1)])]
	for i in range(0, len(cnt) - 2 * K - 2, 2):
		T.append(T[-1] - cnt[i] - cnt[i + 1] + cnt[i + 2 * K + 1] + cnt[i + 2 * K + 2])
	print(max(T))

main()

Submission status: Accepted

Solution code:
# 解説AC
# https://drken1215.hatenablog.com/entry/2019/04/14/222900
n, k = map(int, input().split())
S = list(input())

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

# 1の個数、0の個数、1の個数、、、
cnt = []

# 先頭が0なら1が0個とみなす
if S[0] == "0":
    cnt.append(0)

# 個数勘定
i = 0
while i < n:
    j = i
    while j < n and S[i] == S[j]:
        j += 1
    cnt.append(j-i)
    i = j

# 最後尾が0なら1が0個とみなす
if S[-1] == "0":
    cnt.append(0)

# cnt の累積和
cumCnt = [0]
for c in cnt:
    cumCnt.append(cumCnt[-1] + c)

# print(cnt)
# print(cumCnt)

lenCnt = len(cnt)
lenCumCnt = len(cumCnt)
ans = 0

for left in range(0, lenCumCnt, 2):
    right = min(left + 2*k+1, lenCumCnt-1)
    ans = max(ans, cumCnt[right] - cumCnt[left])
print(ans)

Submission status: Accepted

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

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

# 1の個数、0の個数、1の個数、、、
cnt = []

# 先頭が0なら1が0個とみなす
if S[0] == "0":
    cnt.append(0)

# 個数勘定
i = 0
while i < n:
    j = i
    while j < n and S[i] == S[j]:
        j += 1
    cnt.append(j-i)
    i = j

# 最後尾が0なら1が0個とみなす
if S[-1] == "0":
    cnt.append(0)

# cnt の累積和
cumCnt = [0]
for c in cnt:
    cumCnt.append(cumCnt[-1] + c)

# print(cnt)
# print(cumCnt)

lenCnt = len(cnt)
lenCumCnt = len(cumCnt)
ans = 0

for left in range(0, lenCumCnt, 2):
    right = min(left + 2*k+1, lenCumCnt-1)
    ans = max(ans, cumCnt[right] - cumCnt[left])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

i=0
if s[0]=='1':
    lst=[]
else:
    lst=[0]

while i<n:
    j=i
    cnt=0
    while j<n and s[i]==s[j]:
        cnt+=1
        j+=1
    
    lst.append(cnt)
    i=j

if 2*k+1>=len(lst):
    print(n)
    exit(0)

csum=list(accumulate(lst))
cur=csum[2*k]
ans=cur
for i in range(2,len(lst),2):
    right=min(i+2*k,len(lst)-1)

    ans=max(ans,csum[right]-csum[i-1])

print(ans)

Submission status: Accepted

Solution code:
import sys
 
N, K = map(int, sys.stdin.readline().strip().split())
S = sys.stdin.readline().strip()
 
l = x = ans = 0
for r in range(N):
    if S[r] == '0' :
        if r == 0 or S[r-1] == '1':
            x += 1
    if x > K:
        while S[l] == '1':
            l += 1
        while S[l] == '0':
            l += 1
        x -= 1
    ans = max(ans, r-l+1)
print(ans)

Submission status: Accepted

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

a = []

i = 0
while i < n:
    j = 1
    while i + j < n and s[i] == s[i + j]:
        j += 1
    a.append((s[i], j))
    i += j
if a[0][0] == '0':
    a = [('1', 0)] + a
if a[-1][0] == '1':
    a.append(('0', 0))

while len(a) < k * 2:
    a.append(('1', 0))
    a.append(('0', 0))
m = len(a)


s = [0] * (m + k * 5 + 1)
for i in range(m + k * 2):
    if i < m:
        s[i + 1] = s[i] + a[i][1]
    else:
        s[i + 1] = s[i]
ans = 0
for i in range(1, m, 2):
    ans = max(ans, s[i + k * 2] - s[i - 1])
print(ans)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


N,K = MI()
S = LI2()

A = []
a = 1
for i in range(1,N):
    if S[i-1] == S[i]:
        a += 1
    else:
        A.append(a)
        a = 1
A.append(a)

l = len(A)
if l <= 2*K-1:
    print(N)
    exit()

if S[0] == 1:
    A = [1]+A
if S[-1] == 1:
    A = A+[1]

A = [0]+A
l = len(A)

from itertools import accumulate

A = list(accumulate(A))
ans = 0
for i in range(l//2-K+1):
    if i == 0:
        ans = max(ans,A[2*(K+i)]-A[2*i])
    elif i == l//2-K:
        ans = max(ans,A[2*(K+i)-1]-A[2*i-1])
    else:
        ans = max(ans,A[2*(K+i)]-A[2*i-1])

print(ans)

Submission status: Accepted

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

if s[0] == "0":
  zero=True
  iti=False
else:
  iti=True
  zero=False

count=0
for i in range(0,len(s)):
  if zero and s[i]=="0":
    count+=1
  elif zero and s[i]=="1":
    d.append(count)
    iti=True
    zero=False
    count=1
  elif iti and s[i]=="0":
    d.append(count)
    zero=True
    iti=False
    count=1
  elif iti and s[i]=="1":
    count+=1
d.append(count)
d.append(0)
import itertools
acum = list(itertools.accumulate([0]+d))
#print(d)
#print(acum)
hantei=0
ans=0
if s[0]=="0":
  ks1=min(k*2,len(d))
  ks2=min(k*2+1,len(d))
else:
  ks1=min(k*2+1,len(d))
  ks2=min(k*2,len(d))
  
for i in range(0,len(d)-ks1+1,2):
  ans=max(acum[i+(ks1)]-acum[i],ans)
for i in range(1,len(d)-ks2+1,2):
  ans=max(acum[i+(ks2)]-acum[i],ans)
print(ans)

Submission status: Accepted

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

from itertools import groupby

gr = groupby(s)

cum=[]
tmp=0
for k,v in gr:
    if k=='0':
        cum.append(tmp+len(list(v)))
        tmp=0
    elif k=='1':
        tmp+=len(list(v))


cum = list(reversed(cum))

ans = 0
cnt = 0
tmp=0
gr = groupby(s)
for k,v in gr:
    if k=='0':
        cnt+=1
        if cnt>p:
            tmp -=cum.pop()

    tmp +=len(list(v))
    ans = max(ans,tmp)


print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
S = LI2()

A = []
a = 1
for i in range(1,N):
    if S[i-1] == S[i]:
        a += 1
    else:
        A.append(a)
        a = 1
A.append(a)

l = len(A)
if l <= 2*K-1:
    print(N)
    exit()

if S[0] == 1:
    A = [1]+A
if S[-1] == 1:
    A = A+[1]

A = [0]+A
l = len(A)

from itertools import accumulate

A = list(accumulate(A))
ans = 0
for i in range(l//2-K+1):
    if i == 0:
        ans = max(ans,A[2*(K+i)]-A[2*i])
    elif i == l//2-K:
        ans = max(ans,A[2*(K+i)-1]-A[2*i-1])
    else:
        ans = max(ans,A[2*(K+i)]-A[2*i-1])

print(ans)

Submission status: Accepted

Solution code:
def run_length_compress(S):
    res = [[S[0], 1]]
    for c in S[1:]:
        if c == res[-1][0]:
            res[-1][1] += 1
        else:
            res.append([c, 1])
    return res


N, K = map(int, input().split())
S = input()
cs = run_length_compress(S)
M = len(cs)

ans = 0
tot = 0
right = 0
zeros = 0
for left in range(M):
    while right < M and zeros + (cs[right][0] == "0") <= K:
        if cs[right][0] == "0":
            zeros += 1
        tot += cs[right][1]
        right += 1

    ans = max(ans, tot)

    if left == right:
        right += 1
    else:
        if cs[left][0] == "0":
            zeros -= 1
        tot -= cs[left][1]
print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, S):
    S = [int(s) for s in S]
    point_l = 0
    point_r = 0
    # decision r
    num_0 = 0 if S[0] == 1 else 1
    flg = S[0]
    for i in range(N):
        if S[i] != flg:
            if flg == 1:
                num_0 += 1
                if num_0 > K:
                    point_r = i - 1
                    break
            flg = S[i]
        if i == N - 1:
            point_r = i
            break
    # measuring method
    ans = point_r - point_l + 1
    while point_r < N - 1:
        # move point_l
        for i in range(0, N):
            if S[point_l + i] != S[point_l + i + 1]:
                if S[point_l + i + 1] == 1:
                    point_l += i + 1
                    break
        # move point_r
        for i in range(1, N):
            if point_r + i == N - 1:
                point_r = N - 1
                break
            if S[point_r + i] != S[point_r + i + 1]:
                if S[point_r + i + 1] == 0:
                    point_r += i
                    break
        ans = max(ans, point_r - point_l + 1)

    print(ans)


if __name__ == '__main__':
    N, K = map(int, input().split())
    S = input()
    solve(N, K, S)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

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

l = []
ans = 0
q = "1"
n = 0

for i in range(len(S)):
    if q != S[i]:
        l.append(n)
        n = 1
    else:
        n += 1
    q = S[i]
l.append(n)
if S[-1] == "0":
    l.append(0)

maxlen = K * 2 + 1

if maxlen >= len(l):
    print(N)
else:
    su = 0
    for i in range(maxlen):
        su += l[i]
    ans = su
    for i in range(0,len(l) - maxlen,2):
        su -= l[i] + l[i + 1]
        su += l[maxlen + i] + l[maxlen + i + 1]
        ans = max(ans,su)
    print(ans)

Submission status: Accepted

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

C = [0]
tmp = 0
car = 0
for i in range(N):
  if S[i] != car:
    C.append(tmp)
    tmp = 1
    car = S[i]
  else:
    tmp += 1
C.append(tmp)
if car == 0:
  C.append(0)

#print(C)
if len(C) <= 2*K+1:
  print(N)
else:
  tmp = sum(C[0:2*K+1])
  ans = sum(C[0:2*K+1])
  for i in range(0,len(C)-(2*K+1),2):
    tmp -= C[i]
    tmp -= C[i+1]
    tmp += C[i + 2*K+1]
    tmp += C[i + 2*K+1 + 1]
    ans = max(ans, tmp)
    #print(tmp)
  print(ans)

Submission status: Accepted

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

s1 = 0
s0 = 0

if N < K:
    print(N)
    exit(0)
# Create 01 array
for c in S:
    if c == '1':
        s1 += 1
        if not s0 == 0:
            ts.append((0, s0))
        s0 = 0
    else:
        s0 += 1
        if not s1 == 0:
            ts.append((1,s1))
        s1 = 0

if s1 != 0:
    ts.append((1,s1))
if s0 != 0:
    ts.append((0,s0))

# print("TS:", ts)

# top/bottom
top0 = False
bottom0 = False

if ts[0][0] == 0:
    top0 = True

if ts[-1][0] == 0:
    bottom0 = True

# print(top0, bottom0)
## pre calc
if len(ts) >= 2:
    ans = 1
else:
    ans = ts[0][1]
# print(ans)

sp = 0
ep = len(ts)

if top0:
    ans = sum(x[1] for x in ts[:K*2])
    # print("t0:", ans)
    sp = 1

if bottom0:
    ans = max(ans, sum(x[1] for x in ts[-K*2:]))
    # print("b0:", ans)
    ep = len(ts)-1

# Calc
# print(sp, ep)
if ep - sp > 1:
    W = 2 * K + 1
    temp = sum([x[1] for x in ts[sp:sp+W]])
    # print("temp:", temp)
    ans = max(temp, ans)

    for ix in range(sp+2, ep-W+1, 2):
        temp = temp - ts[ix-1][1] - ts[ix-2][1] + ts[ix+W-1][1] + ts[ix+W-2][1]
        # print(ix, temp)
        ans = max(temp, ans)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
a = [0]
for i in range(n):
    if (s[i] == "0") == (len(a) % 2 == 1):
        a.append(1)
    else:
        a[-1] += 1
t = [0]
for i in a:
    t.append(i + t[-1])
ans = 0
for i in range(len(t)):
    if i % 2 == 0:
        # print(min(i + 2 * k + 1, len(t) - 1))
        ans = max(ans, t[min(i + 2 * k + 1, len(t) - 1)] - t[i])
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
seqs = [] #(start, end, 0or1): [start, end)
now_num = S[0]
start = 0
for i in range(1, N):
    if S[i] != now_num:
        seqs.append((start, i, int(now_num)))
        now_num = S[i]
        start = i
        if i == N-1:
            seqs.append((start, N, int(now_num)))
            break
    if i == N-1:
        seqs.append((start, N, int(now_num)))
        break

first = S[0]
zero_ranges = None
if first == "0":
    zero_ranges = [i for i in range(0, len(seqs), 2)]
else:
    zero_ranges = [i for i in range(1, len(seqs), 2)]
n_zero = len(zero_ranges)
if n_zero <= K:
    print(N)
    exit()

cum = [0]*(len(seqs)+1)
cum[0] = 0
for i in range(1, len(seqs)+1):
    s, e, n = seqs[i-1]
    cum[i] = cum[i-1] + e-s
length = len(seqs)
ans = 0
for i in range(int(first), len(seqs), 2):
    j = i + 2*K - 2
    if j+1 > length:
        continue
    tmp = 0
    if j+2 <= length and i-1 >= 0:
        tmp = cum[j+2] - cum[i-1]
    elif j+2 <= length and i-1 < 0:
        tmp = cum[j+2]
    elif j+2 > length and i-1 >= 0:
        tmp = cum[j+1] - cum[i-1]
    else:
        tmp = cum[j+1]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())+['-1']

num = [0]
for i in range(1,n+1):
    if s[i-1] != s[i]:
        num.append(i)
# print(num)

ans,lennum = num[1],len(num)
for i in range((s[0]=='1')-1,lennum-2,2):
    l,r = max(i,0),min(i+2*k+1,lennum-1)
    ans = max(ans,num[r]-num[l])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
A=[]
now=1
cnt=0
for i in range(n):
    if int(s[i])==now:
        cnt+=1
    else:
        now^=1
        A.append(cnt)
        cnt=1
A.append(cnt)
if len(A)%2==0:
    A.append(0)



bk=2*k+1
ans=sum(A[0:bk])
res=ans
left=0
right=bk
while right+2<=len(A):
    res-=A[left]
    res-=A[left+1]
    left+=2    
    res+=A[right]
    res+=A[right+1]
    right+=2
    ans=max(res,ans)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
count0=[]
count1=[]
if s[0]=="0":
    count1.append(0)

i=0
temp=0
while i<=n-1:
    j=0
    while i+j+1<=n-1 and s[i+j]==s[i+j+1]:
        j+=1
    if s[i]=="0":
        count0.append(j+1)
    else:
        count1.append(j+1)
    i+=(j+1)


if s[-1]=="0":
    count1.append(0)


sun=sum(count0[:k])+sum(count1[:k+1])
temp=sun
for i in range(len(count0)-k):
    sun=sun+count0[k+i]+count1[k+1+i]-count0[i]-count1[i]
    temp=max(temp,sun)
print(temp)