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 sys import stdin
sN,sK = stdin.readline().rstrip().split()
N,K = int(sN), int(sK)
S = stdin.readline().rstrip()
# print(N,K)
# print(S)
nums = []
now = 1
cnt = 0
for itr in range(0,N):
    if S[itr] == 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)
add = 2*K+1
ans = 0
left = 0
right = 0
tmp = 0
for itr in range(0,len(nums),2):
    nextleft = itr
    nextright = min(itr + add, len(nums))
    while(right < N and right < nextright):
        tmp += nums[right]
        right += 1
    while(left < N and left < nextleft):
        tmp -= nums[left]
        left += 1
    ans = max(tmp, ans)
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")
#print(x)
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:
n,k = map(int,input().split())
s = tuple(input())

now = 1 # 今見ている数
cnt = 0 # nowがいくつ並んでいるか
nums =[]

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1    #見る値の切り替え
        cnt = 1

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

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

add = 2 * k + 1
ans = 0
left = 0
right = 0
tmp = 0

for i in range(len(nums))[::2]:
    next_left = i
    next_right = min(i+add, len(nums))
    # 尺取法
    while next_left > left:
        tmp -= nums[left]
        left += 1
    while next_right > right:
        tmp += nums[right]
        right += 1
    ans = max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np 

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

li = []
right=0
left =0
cnta = 0
if s[right]=="0":
    cnta=1
while(right<len(s)-1):
    if s[right]=="1" and s[right+1]=="0":
        cnta += 1
    if cnta > K:
        li.append(len(s[left:right+1]))
        while(left<len(s)-1):
            if s[left]=="0" and s[left+1]=="1":
                left+=1
                cnta-=1
                li.append(len(s[left:right+1]))
                break
            left += 1
    right += 1
li.append(len(s[left:]))
mx = 0
for i in li:
    mx = max(mx, i)
print(mx)

Submission status: Accepted

Solution code:
#looked ans

n,k = map(int,input().split())
s = input()
#入力
cnt = 0
if s[0] == '0':
    cnt += 1
for i in range(1,n):
    if s[i-1] == '1' and s[i] == '0':
        cnt += 1
##切り替わるところで＋1
if cnt <= k:
    print(n)
    #切り替わるところが動かす回数より少ない場合n(自明)
else:
    one_left,one_right = [0],[]
    #
    for i in range(1,n):
        if s[i-1] == '0' and s[i] == '1':
            one_left.append(i)
        if s[i-1] == '1' and s[i] == '0':
            one_right.append(i)
    #01 の時右に加える10の時左に加える
    #切り替えの時の配列の番号を加える
    one_right.append(n)
    #nはとりあえず右
    if s[0] == '1':
        one_right.pop(0)
    if s[-1] == '1':
        one_left.pop(-1)
    #最初の人が逆立ちしているなら右の切り替えの最初はなし
    #最後の人が逆立ちしているなら左の切り替えの最後はなし
    #print(one_right,'r')
    #print(one_left,'l')

    ans = 0
    #ans 01,10の切り替えの少ないほうでloopを回す
    for i in range(min(len(one_left),len(one_right)-k+1)):
        ans = max(ans,one_right[i+k-1]-one_left[i])
        #ans は　ある点までの個数-フラグの開始点までの個数の最大値
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np 

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

li = []
ls = []
pre = "X"
for i in range(len(s)):
    if pre!=s[i]:
        li.append(i)
        ls.append(s[i])
    pre=s[i]
# print(li)
# print(ls)

for _ in range(K*2+1):
    li.append(N)

maxv = 0
for i in range(len(ls)):
    if ls[i] == "0":
        maxv = max(maxv, li[i+K*2]-li[i])
    else:
        maxv = max(maxv, li[i+K*2+1]-li[i])

print(maxv)

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def findmax():
    cur=0
    l=[]
    prev = '1'
    for c in s:
        if prev ==c:
            cur+=1
        else:
            l.append(cur)
            cur = 1
        prev=c
    l.append(cur)
    if prev=='0':
        l.append(0)
    w = 2*k+1
    if len(l)<=w:
        return n
    sumup = [0]+list(accumulate(l))
    res = 0
    for i in range(0, len(l)-w+1,2):
        res = max(res,sumup[i+w]-sumup[i])
    return res
print(findmax())

Submission status: Accepted

Solution code:
#尺取を累積和にかえてみた
def 眠い():
	N,K=[int(_) for _ in input().split()]
	aS = [0]*N
	iS = 0
	iC = 0
	for s in input():
		if s == '0' :
			if iS % 2:
				aS[iS] = iC
				iS += 1
				iC = 1
			else:
				iC += 1
		else:
			if iS % 2:
				iC += 1
			else:
				aS[iS] = iC
				iS += 1
				iC = 1

	if iC:
		if s == '0' :
			if iS % 2:
				aS[iS]=0
				iS+=1
				aS[iS]=iC
			else:
				if len(aS) < iS +1 :
					aS.append(0)
					aS[iS]=iC
				else:
					aS[iS]=iC
		else:
			if iS % 2:
				if len(aS) < iS +1:
					aS.append(0)	
					aS[iS]=iC
				else:
					aS[iS]=iC
			else:
				aS[iS]=0
				iS +=1
				aS[iS]=iC
	aS=aS[:iS+1]
	iL = len(aS)
	accS = [0]*(iL+3)
	for i in range(iL):
		accS[i+1]=aS[i]+accS[i]
	accS[-2]=accS[-3]

	iLP=iL//2
	if iL % 2:
		iLP += 1
		if iLP <= K:
			print(N)
			exit()
	else:
		if iLP <= K:
			print(N)
			exit()
	print(max(accS[(i+K)*2]-accS[i*2 -1 ] for i in range(iLP-K+1)))

眠い()

Submission status: Accepted

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

ruiwa = [0]

for i in range(1,len(s)):
    if s[i] != s[i-1]:
        ruiwa.append(i)
ruiwa.append(n)

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    cnt=0
    l=[]
    prev = "1"

    for i in s:
        if prev ==i:
            cnt+=1
        else:
            l.append(cnt)
            cnt = 1
        prev=i
    l.append(cnt)
    if prev=="0":
        l.append(0)

    w = 2*k+1

    if len(l)<=w:
        return n

    acc = [0]+list(accumulate(l))
    ans = 0
    for i in range(0, len(l)-w+1,2):
        ans = max(ans,acc[i+w]-acc[i])
    return ans
print(solve())

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    cnt=0
    l=[]
    prev = '1'

    for i in s:
        if prev ==i:
            cnt+=1
        else:
            l.append(cnt)
            cnt = 1
        prev=i
    l.append(cnt)
    if prev=='0':
        l.append(0)

    w = 2*k+1

    if len(l)<=w:
        return n

    acc = [0]+list(accumulate(l))
    ans = 0
    for i in range(0, len(l)-w+1,2):
        ans = max(ans,acc[i+w]-acc[i])
    return ans
print(solve())

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    cnt=0
    l=[]
    prev = '1'

    for c in s:
        if prev ==c:
            cnt+=1
        else:
            l.append(cnt)
            cnt = 1
        prev=c
    l.append(cnt)
    if prev=='0':
        l.append(0)

    w = 2*k+1

    if len(l)<=w:
        return n

    acc = [0]+list(accumulate(l))
    ans = 0
    for i in range(0, len(l)-w+1,2):
        ans = max(ans,acc[i+w]-acc[i])
    return ans
print(solve())

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
S = input()
len0 = [len(i) for i in S.split('1') if (len(i)) != 0]
len1 = [len(i) for i in S.split('0') if (len(i)) != 0]

lens = np.zeros(len(len0)+len(len1), dtype=np.int)
if(int(S[0])==0):
    lens[::2] = len0
    lens[1::2] = len1
else:
    lens[::2] = len1
    lens[1::2] = len0
lens = np.cumsum(lens)
    
if(S[0] == "0"):
    lens = np.insert(lens, 0, 0)
lens = np.append(lens, [lens[-1]]*(K*2))

if(K >= len(len0)):
    print(len(S))
else:
    ans = []
    max_num = 0
    for first, i in enumerate(range(K*2, len(lens), 2)):
        if(first == 0):
            ans = lens[i]
        else:
            ans = lens[i] - lens[i-(K*2)-1]
        if(ans > max_num):
            max_num = ans
    
    print(max_num)

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    cnt=0
    l=[]
    prev = '1'
    
    for c in s:
        if prev ==c:
            cnt+=1
        else:
            l.append(cnt)
            cnt = 1
        prev=c
    l.append(cnt)
    if prev=='0':
        l.append(0)

    w = 2*k+1

    if len(l)<=w:
        return n

    acc = [0]+list(accumulate(l))
    ans = 0
    for i in range(0, len(l)-w+1,2):
        ans = max(ans,acc[i+w]-acc[i])
    return ans
print(solve())

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    l=[]
    prev = '1'
    cnt = 0
    for c in s:
        if prev ==c:
            cnt+=1
        else:
            l.append(cnt)
            cnt = 1
        prev=c
    l.append(cnt)
    if prev=='0':
        l.append(0)

    w = 2*k+1

    if len(l)<=w:
        return n

    acc = [0]+list(accumulate(l))
    ans = 0
    for i in range(0, len(l)-w+1,2):
        ans = max(ans,acc[i+w]-acc[i])
    return ans
print(solve())

Submission status: Accepted

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

import re

def nchars(s, n):
    """文字列 s に、同じ文字が n 個以上連続している部分文字列を見つける
    """
    assert n > 0
    reg = re.compile("(.)\\1{%d,}" % (n - 1))  # カンマを取ると n 個ちょうどになる
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s = s[m.end():]

s_list = list(nchars(S, 1))
s_list_num = [len(s) for s in s_list]
if '1' in s_list[0]:
    s_list_num.insert(0,0)
else:
    s_list_num.insert(0,0)
    s_list_num.insert(0,0)


s_list_sum = []
tmp_sum = 0
for x in s_list_num:
    tmp_sum += x
    s_list_sum.append(tmp_sum)

#print(s_list)
#print(s_list_num)
#print(s_list_sum)

ans = 0
for i in range(1, len(s_list_sum),2):

    l_sum = s_list_sum[i-1]
    r_sum = s_list_sum[min(len(s_list_sum)-1, i+K*2)]
    #print(l_sum, r_sum)
    ans = max(ans, r_sum - l_sum)

print(ans)

Submission status: Accepted

Solution code:

def 眠い():
	N,K=[int(_) for _ in input().split()]
	aS = [0]*N
	iS = 0
	iC = 0
	for s in input():
		if s == '0' :
			if iS % 2:
				aS[iS] = iC
				iS += 1
				iC = 1
			else:
				iC += 1
		else:
			if iS % 2:
				iC += 1
			else:
				aS[iS] = iC
				iS += 1
				iC = 1

	if iC:
		if s == '0' :
			if iS % 2:
				aS[iS]=0
				iS+=1
				aS[iS]=iC
			else:
				if len(aS) < iS +1 :
					aS.append(0)
					aS[iS]=iC
				else:
					aS[iS]=iC
		else:
			if iS % 2:
				if len(aS) < iS +1:
					aS.append(0)	
					aS[iS]=iC
				else:
					aS[iS]=iC
			else:
				aS[iS]=0
				iS +=1
				aS[iS]=iC
	aS=aS[:iS+1]
	iL = len(aS)
	iLP = iL // 2
	if iL % 2:
		iLP += 1
		if iLP <= K:
			print(N)
		else:
			iD = sum(aS[:2*K])
			iMax = iD
			for i in range(1,iLP -K+1):
				if i == 1:
					iD -= aS[0]
				else:
					j = (i-1)*2
					iD -= sum(aS[j-1:j+1])
				if i == iLP -K :
					iD += aS[-1]
				else:
					j = (i+K-1)*2
					iD +=  sum(aS[j:j+2])
				if iMax < iD:
					iMax = iD
			print(iMax)
	else:
		if iLP <= K:
			print(N)
		else:
			iD = sum(aS[:2*K])
			iMax = iD
			for i in range(1,iLP -K+1):
				if i == 1:
					iD -= aS[0]
				else:
					j = (i-1)*2
					iD -= sum(aS[j-1:j+1])
				j = (i+K-1)*2
				iD +=  sum(aS[j:j+2])
				if iMax < iD:
					iMax = iD
			print(iMax)

眠い()

Submission status: Accepted

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

	one_left, one_right = [], []
	#if s[0] == "1":
	one_left.append(0)
	for i in range(1, n):
		if s[i-1] == "0" and s[i] == "1":
			one_left.append(i)
		if s[i-1] == "1" and s[i] == "0":
			one_right.append(i)
	#if s[-1] == "1":
	one_right.append(n)
	if s[0] == "1":
		one_right.pop(0)
	if s[-1] == "1":
		one_left.pop(-1)
	#print(one_left)
	#print(one_right)
	ans = 0
	for i in range(min(len(one_left), len(one_right)-k+1)):
		ans = max(ans, one_right[i+k-1] - one_left[i])
	print(ans)

Submission status: Accepted

Solution code:
#input
N, K = map(int, input().split())#0~K-1回目と考える。
s = input() #0~N-1人目と考える。


#output

first_pos = int(s[0:1]) #0人目が○なら1, ×なら0

nowpos = first_pos #今チェックしている立ち方
nowposcount = 0 #1にすると0人目を考えるときにバグる
Accum = [0] * (N+1) #累積和 取り出し方は[まとまり個数目] 要素数はまとまりの個数+1
nowRuisekiCount = 1 #何番目のまとまりを見ているか 0~まとまり個数-1
zeroRenzoku = 1

for i in range(len(s)): #0~N-1人目につき、全てをチェックして累積和のリストを作る
    if int(s[i:i+1]) == nowpos: #今チェックしている立ち方と同じ(左の人と同じ)なら
        nowposcount += 1 #左のまとまりの個数を1増やす
        Accum[nowRuisekiCount] = Accum[nowRuisekiCount-1] + nowposcount #まとまりの数字数を入れる
    else:
        nowpos = abs(nowpos - 1)
        nowposcount = 1 #nowposcountは1に戻る
        nowRuisekiCount += 1 #次のまとまりに移ったことになる
        Accum[nowRuisekiCount] = Accum[nowRuisekiCount-1] + nowposcount #まとまりの文字数を入れる(1を入れる)

matomariCount = nowRuisekiCount #まとまりの数

#累積和を出す
if (first_pos == 1) & (matomariCount <= (K*2+1)): #まとまり数がK*2+1以下なら、全部逆立ちさせられる
    print(len(s))
elif (first_pos == 0) & (matomariCount <= (K*2)): #最初が0だと同様にK*2以下なら
    print(len(s))
else:
    #一番最初の合計文字数
    if first_pos == 1:
        maxaccum = Accum[(K*2+1)]
    else: #最初のまとまりが0なら
        maxaccum = Accum[(K*2)]

    #2個目のまとまりからも同様に見ていく
    for i in range(2, matomariCount+1, 1):
        if abs((first_pos - ((i-1)%2))) == 0: #これが0なら左端が0なので右端を落とす
            if i+(K*2)-1 > matomariCount:
                maxaccum = max(maxaccum, Accum[matomariCount]-Accum[i-1])
            else:
                maxaccum = max(maxaccum, Accum[i+(K*2)-1]-Accum[i-1])
        else:
            if i+(K*2) > matomariCount:
                maxaccum = max(maxaccum, Accum[matomariCount]-Accum[i-1])
            else:
                maxaccum = max(maxaccum, Accum[i+(K*2)]-Accum[i-1])
    print(maxaccum)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
memo = []
c = 0
ps = ''
lens = len(s) - 1
b = 0
if s[0] == '1':
    b = 1

for i in range(lens + 1):
    if s[i] != ps:
        memo.append(c)
        c = 1
        ps = s[i]
        if i == lens:
            memo.append(1)
        continue
    if i == lens:
        memo.append(c+1)
    c += 1
    ps = s[i]

if  len(memo) < k * 2 + b + 1:
    print(sum(memo))
else:
    sumi = 0
    sumi = sum(memo[: k * 2 + b + 1])
    temp = [sumi]
    memo.append(0)
    # print(memo)
    # print(len(memo))
    for i in range(b, len(memo) - 2 * k  - 1, 2):
        last = 0
        if i + 2 * k + 2 <= len(memo) - 1:
            last = memo[i + 2 * k + 2]
        sumi = sumi - memo[i] - memo[i + 1] + memo[i + 2 * k  + 1] +last
        temp.append(sumi)
    # print(temp)
    print(max(temp))

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


def runLength(in_str):
    kukan = 1
    start = 0
    ret = []
    for i in range(1,len(in_str)):
        if in_str[i-1]!=in_str[i]:
            ret.append([in_str[i-1],kukan,start])
            start = i
            kukan=0
        kukan+=1
    ret.append([in_str[-1],kukan,start])
    return ret

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

def main():
    global cts
    ans = 0
    kukan = 1
    start = 0
    if S[0]=="0":
        cts.append(["1",0,0])
    cts += runLength(S)
    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 = input()
start =[]
end = [0]
if S[0] == "0":
    start.append(0)
for i in range(n):
    if S[i:i+2] == "10":
        start.append(i+1)
    elif S[i:i+2] == "01":
        end.append(i+1)

if len(start) <= k:
    print(len(S))
else:
    start.append(len(S))
    ans = []
    for i in range(len(start) - k):
        ans.append(start[i + k] - end[i])
    print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    l=[]
    prev = '1'
    cnt = 0
    for c in s:
        if prev ==c:
            cnt += 1
        else:
            l.append(cnt)
            cnt = 1
        prev = c
    l.append(cnt)
    if prev == '0':
        l.append(0)

    w = 2 * k + 1

    if len(l) <= w:
        return n

    acc = [0] + list(accumulate(l))
    ans = 0
    for i in range(0, len(l) - w + 1, 2):
        ans = max(ans, acc[i + w] - acc[i])
    return ans


print(solve())

Submission status: Accepted

Solution code:

def main():
    all_num, inst_num = map(int, input().split())
    data = list(input())

    data_la = []
    ans_0, ans_1 = 0, 0
    for i in range(all_num):
        if data[i] == '1':
            ans_1 += 1
            if ans_0 > 0:
                data_la.append(ans_0)
                ans_0 = 0
        else:
            ans_0 += 1
            if ans_1 > 0:
                data_la.append(ans_1)
                ans_1 = 0
    if ans_1 > 0:
        data_la.append(ans_1)
    elif ans_0 > 0:
        data_la.append(ans_0)

    ans = 0
    ans_data = 0
    count_0 = 0

    if data[0] == '0':
        data_la.insert(0, 0)

    # print(data_la)

    if len(data_la) <= 2:
        ans_data = sum(data_la)
    else:
        pre_data1_ind, pre_data2_ind = 0, 1
        pre_data1, pre_data2 = data_la[pre_data1_ind], data_la[pre_data2_ind]

        for i in range(len(data_la)):
            if i % 2 == 1:
                count_0 += 1

            if count_0 == inst_num + 1:
                ans = ans - pre_data1 - pre_data2
                pre_data1_ind += 2
                pre_data2_ind += 2
                if pre_data1_ind >= len(data_la):
                    pre_data1 = 0
                else:
                    pre_data1 = data_la[pre_data1_ind]
                if pre_data2_ind >= len(data_la):
                    pre_data2 = 0
                else:
                    pre_data2 = data_la[pre_data2_ind]
                count_0 -= 1

            ans += data_la[i]
            if ans_data < ans:
                ans_data = ans

    print(ans_data)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

runlength_one = []
runlength_zero = []
counter = 0
prev = '1'
for s in S:
    if s == prev:
        counter += 1
    else:
        if s == '1':
            runlength_zero.append(counter)
        else:
            runlength_one.append(counter)
        counter = 1
        prev = s
if S[-1] == '1':
    runlength_one.append(counter)
else:
    runlength_one.append(0)
    runlength_zero.append(counter)

max = 0
sum_one = 0
sum_zero = 0
for i in range(len(runlength_one)):
    if i + K >= len(runlength_one):
        break

    if i == 0:
        sum_one = sum(runlength_one[0:K + 1])
        sum_zero = sum(runlength_zero[0:K])
    else:
        sum_one = sum_one - runlength_one[i - 1] + runlength_one[i + K]
        sum_zero = sum_zero - runlength_zero[i - 1] + runlength_zero[i + K - 1]
        
    length = sum_one + sum_zero
    max = length if max < length else max

if max == 0:
    max = sum(runlength_one) + sum(runlength_zero)

print(str(max))

Submission status: Accepted

Solution code:
from itertools import accumulate

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


def solve():
    l = []
    prev = '1'
    cnt = 0
    for c in s:
        if prev == c:
            cnt += 1
        else:
            l.append(cnt)
            cnt = 1
        prev = c
    l.append(cnt)
    if prev == '0':
        l.append(0)

    w = 2 * k + 1

    if len(l) <= w:
        return n

    acc = [0] + list(accumulate(l))
    ans = 0
    for i in range(0, len(l) - w + 1, 2):
        ans = max(ans, acc[i + w] - acc[i])
    return ans


print(solve())

Submission status: Accepted

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

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

number_list = []
num = 1

for i in range(N):
    if i == N - 1:
        number_list.append(num)
    else:
        if S[i] == S[i + 1]:
            num += 1
        else:
            number_list.append(num)
            num = 1

#端が0の時は,その端に1が0個あると置けば場合分けを防げる
if S[0] == '0':
    number_list = [0] + number_list
if S[-1] == '0':
    number_list.append(0)

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

max_num = 0
for i in range(0, len(ruiseki), 2):
    if i == 0:
        max_num = ruiseki[min(i + K * 2, len(ruiseki) - 1)]
    else:
        buff = ruiseki[min(i + K * 2, len(ruiseki) - 1)] - ruiseki[i - 1]
        if buff > max_num:
            max_num = buff

print (max_num)

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,K = (int(_) for _ in input().split())
    S = list(int(_) for _ in input())
    now = 1
    cnt = 0
    Nums = []
    ans = 0
    left = 0
    right = 0
    tmp = 0
    for i in range(N):
        if(S[i]==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)
    Add = 2 * K +1
    sum = []
    sum.append(0)
    for i in range(0,len(Nums)):
        sum.append(sum[i] + Nums[i])
        
    for i in range(0,len(Nums),2):
        left = i
        right = min(i+Add,len(Nums))
        tmp = sum[right] - sum[left]
        # while(Nextleft>left):
        #     tmp -= Nums[left]
        #     left +=1
        # while(Nextright>right):
        #     tmp += Nums[right]
        #     right +=1        
        ans = max(tmp,ans)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

sl = []
c = 1
if (s[0] == "1"):
    sl.append(0)
for i in range(n):
    if (i != 0):
        if (s[i] == s[i-1]):
            c += 1
        else:
            sl.append(c)
            c = 1
sl.append(c)

ruisekiwa = [0]
sums = []
ans = 0
w = 2*k+1

if (w > len(sl)):
    print(n)
    exit()
for i in range(len(sl)):
    ruisekiwa.append(ruisekiwa[i] + sl[i])
# print(sl)
# print(ruisekiwa)
for i in range(len(sl)):
    if(k % 2 == 1 and i % 2 == 0 or k % 2 == 0 and i % 2 == 1):
        left = i-k
        if (left < 0):
            left = 0
        right = i + k+1
        if (right >= len(ruisekiwa)):
            right = len(ruisekiwa)-1
        # print(ruisekiwa[right], "-", ruisekiwa[left],
        #      "=", ruisekiwa[right]-ruisekiwa[left])
        ans = max(ans, ruisekiwa[right]-ruisekiwa[left])
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input()
  
group = []
if s[0] == '0' :
  group = [0]
sign = s[0]
curr = 0
for i in range(N):
  curr += 1
  if s[i] != sign: 
    group += [curr-1]
    curr = 1
    sign = s[i]
else:group += [curr]
if s[-1] == '0':
  group += [0]

m = len(group)//2
if K >= m:
  print(N)
else:
  score = [sum(group[:2*K+1])]
  for i in range(m-K):
    score += [score[-1] - group[2*i]  - group[2*i+1] + group[2*i+2*K+1]+group[2*i+2*K+2]]
  
  print(max(score))

Submission status: Accepted

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

List = []
ans = 0
now,count = 1,0
for i in range(len(S)):
    if S[i] == str(now):
        count += 1
    else:
        List.append(count)
        now = 1-now
        count = 1
if count != 0:
    List.append(count)

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

Ruisekiwa = [0]*(len(List)+1)
for i in range(len(List)):
    Ruisekiwa[i+1] = Ruisekiwa[i]+List[i]

add = 2*K+1
for i in range(0,len(List),2):
    left = i
    right = min(i+add,len(List))
    tmp = Ruisekiwa[right] - Ruisekiwa[left]

    ans = max(tmp,ans)


print(ans)

Submission status: Accepted

Solution code:
from queue import Queue as q

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

S = input()

C = q()

one = True
subK = 0
c = 0
ans = 0
Mans = 0
for s in S:
    if s=="1":
        if one:
            c += 1
        else:
            one = True
            C.put(c)
            c = 1
    else:
        if one:
            one = False
            subK += 1
            C.put(c)
            c = 1
        else:
            c += 1
    ans += 1
    if subK>K:
        subK -= 1
        ans -= (C.get()+C.get())
    #print(ans)
    if ans > Mans:
        Mans = ans
    
print(Mans)

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,K = (int(_) for _ in input().split())
    S = list(int(_) for _ in input())
    now = 1
    cnt = 0
    Nums = []
    ans = 0
    left = 0
    right = 0
    tmp = 0
    for i in range(N):
        if(S[i]==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)
    Add = 2 * K +1
    for i in range(0,len(Nums),2):
        Nextleft = i
        Nextright = min(i+Add,len(Nums))
        
        while(Nextleft>left):
            tmp -= Nums[left]
            left +=1
        while(Nextright>right):
            tmp += Nums[right]
            right +=1        
        ans = max(tmp,ans)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
c = [int(s[i]) for i in range(n)]
ids = [0]
for i in range(1,n):
  if c[i] != c[i-1]:
    ids.append(i)
ids.append(n)
l = len(ids)
result = []
for i in range(l-1):
  if c[ids[i]] == 0:
    if i + 2*k < l:
      result.append(ids[i+2*k] - ids[i])
    else:
      result.append(n - ids[i])
  else:
    if i + 2*k + 1 < l:
      result.append(ids[i+2*k+1] - ids[i])
    else:
      result.append(n - ids[i])
print(max(result))

Submission status: Accepted

Solution code:
in1 = list(map(int, input().split()))
s = input()
n = in1[0]
k = in1[1]

l = 0
r = 0
c = 0
while r < n-1:
  if (s[r]=='1' and s[r+1]=='0' and c>=k): break
  if s[r]=='0' and s[r+1]=='1':
    c += 1
  r += 1
r += 1

m = r
while r < n and l < n:
  #move r
  while True:
    r+=1
    if r == n:
      break
    elif s[r-1]=='1' and s[r]=='0':
      break
  #move l
  while s[l]!='0' or s[l+1]!='1':
    l += 1
  l += 1
  m = max(m, r-l)
print(m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, math, copy
input = sys.stdin.readline

N, K = map(int, input().split())
S = list(input().replace('\n',''))
S = list(map(int, S))

group = [0]

for i in range(1,N):
    if S[i-1] != S[i]:
        group.append(i)

ans = 0
for i in range(len(group)):
    start = group[i]
    if(S[start] == 1):
        end_group_id = i + 2 * K + 1
    else:
        end_group_id = i + 2 * K
    if end_group_id < len(group):
        end = group[end_group_id]
    else:
        end = len(S)
    ans = max(ans, end - start)

print(ans)

Submission status: Accepted

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

i = 0
for j in range(N):
    if S[j] == "0" and (j==0 or S[j-1] == "1"):
        K -= 1
    if (K<0):
        if(S[i]=="0" and S[i+1] == "1"):
            K += 1
        i+=1

print(N-i)