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

people = []
prev = s[0]
neg = False
if prev == "0":
	neg = True

count = 1

for i in range(1, len(s)):
	if prev != s[i]:
		people.append(count)
		count = 0
		prev = s[i]
	count += 1
people.append(count)


if len(people)/2 <= k:
	print(n)
	quit()


max_people, start, prep = 0, 0, 0
if neg == False:
	max_people = sum(people[:(k*2)+1])
	start = 2
	prep = max_people - people[0] - people[1]
else:
	max_people = sum(people[:k*2])
	start = 1
	prep = max_people - people[0]

scan = (k*2)+1
i = 0
for i in range(start, len(people)-(k*2)+1, 2):
	try:
		cur_sum = prep + people[i+scan-1] + people[i+scan-2]
	except IndexError:
		cur_sum = prep + people[-1]
	max_people = max(max_people, cur_sum)
	prep = cur_sum - people[i] - people[i+1]

print(max_people)

Submission status: Accepted

Solution code:
N, K = map( int, input().split())
S = input()
l = 0
now = S[0]
k = 0
if now == "0":
    k = 1
r = 0
for i in range(1, N):
    if now == "1":
        if S[i] == "1":
            r = i
        else:
            k += 1
            if k > K:
                break
            r = i
            now = "0"
    else:
        r = i
        now = S[i]
ans = r - l + 1
while r < N - 1:
    if S[l] == "0":
        for i in range(l,N):
            if S[i] == "1":
                l = i
                break
    else:
        now = "1"
        for i in range(l, N):
            if now == "1":
                now = S[i]
            else:
                if S[i] == "1":
                    l = i
                    break
    now = "0"
    for i in range(r+1, N):
        if now == "0":
            now = S[i]
            r = i
        else:
            if S[i] == "0":
                r = i - 1
                break
            else:
                r = i
    if ans < r-l+1:
        ans = r-l+1
print(ans)

Submission status: Accepted

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

l = [0]
curr = '1'
for c in S:
    if c != curr:
        l.append(1)
        curr = c
    else:
        l[-1] += 1
if curr == '0':
    l.append(0)

n_group = (len(l) - 1) // 2
sum_ = 0
k = min(K, n_group)
sum_ = sum(l[0:2*k+1])
max_ = sum_
for i in range(k, n_group):
    sum_ -= l[2*i-2*K] + l[2*i+1-2*K]
    sum_ += l[2*i+1] + l[2*i+2]
    max_ = max(max_, sum_)
print(max_)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
now = 1
cnt = 0
Nums = []
for i in range(len(s)):
    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)

ans = 0
Add = 2 * k + 1

sum = [0] * (len(Nums) + 1)

for i in range(len(Nums)):
    sum[i + 1] = sum[i] + Nums[i]

for i in range(len(Nums))[::2]:
    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()
cur = "1"
sum_ = [0]
ans = -1
for i, c in enumerate(s):
    if cur != c:
        sum_.append(i)
        if c == "0":
            if len(sum_) >= 2 + k + k:
                ans = max(ans, sum_[-1] - sum_[-2-k-k])
        cur = c
sum_.append(len(s))
if s[-1] == "0":
    sum_.append(len(s))
if len(sum_) > 2 + k + k:
    ans = max(ans, sum_[-1] - sum_[-2-k-k])
else:
    ans = n
print(ans)

Submission status: Accepted

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

l = [0]
curr = '1'
for c in S:
    if c != curr:
        l.append(1)
        curr = c
    else:
        l[-1] += 1
if curr == '0':
    l.append(0)

n_group = len(l) // 2
sum_ = 0
k = min(K, n_group)
sum_ = sum(l[0:2*k+1])
max_ = sum_
for i in range(k, n_group):
    sum_ -= l[2*i-2*K] + l[2*i+1-2*K]
    sum_ += l[2*i+1] + l[2*i+2]
    max_ = max(max_, sum_)
print(max_)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
S = input()
last = S[0]
ls = []
cnt = 0
flg = 0
for n in range(N):
    if S[n] == last:
       cnt += 1
       flg = 1
    else:
        ls.append(cnt)
        last = S[n]
        cnt += 1
        flg = 0
if flg == 1:
    ls.append(cnt)
cumsum = []
ls = [0] * 2 * K + ls
ls_len = len(ls)
first = 0 if S[0] == "0" else 1
for _n in range(first, len(ls), 2):
    cumsum.append(ls[min(ls_len-1, _n + K * 2 + 1)] - ls[_n])
print(max(cumsum))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = deque([int(x) for x in stdin.readline().rstrip()])

# 0の始点と終点のインデックスリスト
# 始点→終点→始点→終点→...の順
# 従って、必ず偶数個になる（インデックスが偶数の場合は始点で、奇数の場合は終点）
index_list = []
if S[0] == 0:
    index_list.append(0)
    
res = []

for i in range(1, len(S)):
    if S[i] != S[i-1]:
        if S[i] == 0:
            index_list.append(i)
        else:
            index_list.append(i-1)

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

if K < len(index_list) // 2:
    for i in range(len(index_list)//2 - K + 1):
        start = 0
        end = 0
        if i == 0:
            start = 0
        else:
            # 1から始まるところ
            # index_list[2*i-1]は0の終点のインデックス
            start = index_list[2*i-1] + 1
        
        if i == len(index_list)//2 - K:
            end = len(S) - 1
        else:
            # 1で終わるところ
            # index_list[2*(i+K)]は0の始点
            end = index_list[2*(i+K)] - 1

        res.append(end-start+1)


# 全部反転できる
if K >= len(index_list)//2:
    res.append(len(S))

print(max(res))

Submission status: Accepted

Solution code:
a = []

n,k = map(int, input().split())
for x in range(k+1):
  a.append(0)
q = input()

p = 0
c = 0
mx = 0

for i in range(n-1):
  p = p+1
  c = c+1  
  if q[i] == q[i+1]:
    lalala = 1

  elif (int(q[i]) == 1) & (int(q[i+1]) == 0) :
    p = p-a[0]
    if p > mx:
      mx = p
    
  elif (int(q[i]) == 0) & (int(q[i+1]) == 1):
    a.pop(0)
    a.append(c)
    c = 0

if int(q[n-1]) == 1:
  if p+1- a[0]> mx:
    mx = p +1 - a[0]
else:
  if p+1 -a[1] > mx:
    mx = p  -a[1] +1
  
  


print(mx)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
now = 1
cnt = 0
Nums = []
for i in range(len(s)):
    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)

ans = 0
Add = 2 * k + 1

left = 0
right = 0
tmp = 0

for i in range(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)

Submission status: Accepted

Solution code:
data = input().split()
N = int(data[0])
K = int(data[1])
 
TL = list(input())
TLlist = []
TLLlist = []
now = TL[0]
nowlist = now
anslist = []
 
for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)
TLLlist.append(len(nowlist))
 
 
if TLlist[0][:1] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    anslist.append( sum(TLLlist[1:2*K + 2]) )
    for lop in range(3,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
elif TLlist[0][:1] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    for lop in range(2,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
 
print(max(anslist))

Submission status: Accepted

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

N,K=[int(x) for x in input().strip().split()]

f=1
cnt=0
S=[]
r=0
for s in input().strip():
    s=int(s)
    if s==f:
        cnt+=1
    else:
        r+=cnt
        S.append(r)
        cnt=1
        f=1-f
else:
    r+=cnt
    S.append(r)
if len(S)%2==0:
    S.append(r)

Max=0
i=0
if len(S)==1:
    Max=S[0]
else:
    while True:
        if i >=len(S):
            break
        r=i+2*K
        cnt=S[min(r,len(S)-1)]-S[max(i-1,0)]
        if cnt > Max:
            Max = cnt
        i+=2

print(Max)

Submission status: Accepted

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

Nums = []
# 今見ている数字
now = 1
# 何個続いているか
cnt = 0
ans = 0

for i in range(N):
    if S[i] == now:
        cnt += 1
    else:
        # 続いた数を挿入
        Nums.append(cnt)
        # 0と1を入れ替え
        now = 1 - now
        # 新しくカウント
        cnt = 1

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

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

Add = 2 * K + 1
# 累積和生成
listSum = [0 for _ in range(len(Nums) + 1)]
for i in range(len(Nums)):
    listSum[i + 1] = listSum[i] + Nums[i]

# 1から始まるので、偶数番目(0のみ)見る
for i in range(0,len(Nums),2):
    left = i
    right = min(i + Add, len(Nums))
    tmp = listSum[right] - listSum[left]

    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

hsc = []
if s[0] == '0':
    hsc.append(0)
pre = s[0]
cnt = 0
for c in s:
    if c == pre:
        cnt += 1
    else:
        hsc.append(cnt)
        pre = c
        cnt = 1
hsc.append(cnt)

_max = sum(hsc[0:2*k+1])
tmp = _max
r = 2 * k + 1
for i in range(2, n, 2):
    l_sum = sum(hsc[i-2:i])
    r_sum = sum(hsc[r:r+2])
    r += 2
    tmp -= l_sum
    tmp += r_sum
    _max = max(_max, tmp)

print(_max)

Submission status: Accepted

Solution code:
import numpy as np

n, k = [int(a) for a in input().split()]
s = input()

def main():
    consecutive_ones = [len(x) for x in s.split("0") if x != '']
    consecutive_zeros = [len(x) for x in s.split("1") if x != '']

    if s[0] == "0":
        consecutive_ones.insert(0, 0)
    if s[-1] == "0":
        consecutive_ones.append(0)
    
    if len(consecutive_zeros) == 0:
        return n
    else:
        cumsum_ones = np.convolve(consecutive_ones, np.ones(k+1), mode='valid')
        cumsum_zeros = np.convolve(consecutive_zeros, np.ones(k), mode='valid')

        z = [x + y for x,y in zip(cumsum_ones, cumsum_zeros)]
        return int(max(z))


print(main())

Submission status: Accepted

Solution code:
n, k=map(int, input().split())
s=list(map(int, list(input())))
if s[0]==0:
    renzoku_list=[0]
else:
    renzoku_list=[]
sum=1
before=s[0]
for i in range(1, n):
    if s[i]==before:
        sum=sum+1
        before=s[i]
    else:
        renzoku_list.append(sum)
        sum=1
        before=s[i]
renzoku_list.append(sum)
if s[n-1]==0:
    renzoku_list.append(0)
ruisekiwa=[0]
for i in range(len(renzoku_list)):
    ruisekiwa.append(renzoku_list[i]+ruisekiwa[i])

length=len(renzoku_list)

max=0

if (length-1)//2<=k:
    print(n)
else:
    for i in range(len(ruisekiwa)-(2*k+1)):
        if i%2==0:#i=0,2,4,...
            sum=ruisekiwa[i+2*k+1]-ruisekiwa[i]
            if sum>=max:
                max=sum
    print(max)

Submission status: Accepted

Solution code:
import sys

def i2s():
    return sys.stdin.readline().rstrip()

def ii2ss(n):
    return [sys.stdin.readline() for _ in range(n)]

def sp2nn(sp, sep=' '):
    return [int(s) for s in sp.split(sep)]

def ss2nn(ss):
    return [int(s) for s in list(ss)]

def analyze(S):
    data = []
    i0 = 0
    s0 = S[0]
    sc = 0
    for i, s in enumerate(S):
        if s == s0:
            sc += 1
        else:
            data.append((i0, s0, sc))
            i0 = i
            s0 = s
            sc = 1
    data.append((i0, s0, sc))
    return data

def main(ss):
    N, K = sp2nn(ss[0])
    S = ss[1]
    data = analyze(S)
    cmax = 0
    
    for dl in range(len(data)):
        c = 0
        dw = K * 2
        if data[dl][1] == '1':
            dw += 1
        if dl + dw < len(data):
            c = data[dl+dw][0] - data[dl][0]
        else:
            c = N - data[dl][0]
        if cmax < c:
            cmax = c
    
    print(cmax)
main(ii2ss(2))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

# stand = []
# reverse = []
# state = None
# count = 0
# tmp = None
# for i in S:
# 	if i == "0":
# 		state = "stand"
# 	else:
# 		state = "reverse"
# 	if tmp == "stand" and state == "reverse":
# 		stand.append(count)
# 		count = 1
# 	elif tmp == "reverse" and state == "stand":
# 		reverse.append(count)
# 		count = 1
# 	else: # 状態が前と同じ
# 		count += 1
# 	tmp = state
# if state == "stand":
# 	stand.append(count)
# else:
# 	reverse.append(count)

# if "0" not in S:
# 	print(len(S))
# else:
# 	if K >= len(stand): # 全員逆立ちにできる
# 		print(len(S))
# 	else:
# 		if len(stand) > len(reverse):
# 			reverse.append(0)
# 			reverse.insert(0, 0)
# 		if len(stand) == len(reverse) and S[0] == "0":
# 			reverse.insert(0, 0)
# 		if len(stand) == len(reverse) and S[0] == "1":
# 			reverse.append(0)
# 		# print(stand)
# 		# print(reverse)
# 		max_ = 0
# 		for i in range(max(1, 1+len(reverse)-(K+1))):
# 			# print(reverse[i:i+K+1],stand[i:i+K])
# 			tmp = sum(reverse[i:i+K+1]+stand[i:i+K])
# 			if tmp > max_:
# 				max_ = tmp
# 		print(max_)
indexes = [0]
if S[0] == "0":
    indexes.append(0)
for i in range(N-1):
	if S[i] != S[i+1]:
		indexes.append(i+1)
indexes.append(N)
if S[N-1] == "0":
    indexes.append(N)
ans = []
# print(indexes)
r = len(indexes)//2 -1
if K >= r:
	print(N)
else:
	print(max(indexes[2*(i+K)+1]-indexes[2*i] for i in range(r-K+1)))
	# for i in range(len(indexes)):
	# 	# print(i)
	# 	if i == len(indexes)-1:
	# 		break
	# 	if S[indexes[i]] == "0":
	# 		if i+2*K >= len(indexes):
	# 			continue
	# 		ans.append(indexes[i+2*K]-indexes[i])
	# 	else:
	# 		if i+2*K+1 >= len(indexes):
	# 			continue
	# 		ans.append(indexes[i+2*K+1]-indexes[i])
	# if ans == []:
	# 	print(len(S))
	# else:
	# 	print(max(ans))

Submission status: Accepted

Solution code:
import sys

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


def nexti(n):
    while S[n] == '1':
        n += 1
    while S[n] == '0':
        n += 1
    return n


def nextj(n):
    while S[n] == '0':
        n += 1
        if n == N:
            return N
    while S[n] == '1':
        n += 1
        if n == N:
            return N
    return n


i = 0
j = 0
while S[j] == '1':
    j += 1
    if j == N:
        print(N)
        sys.exit(0)
for _ in range(K):
    j = nextj(j)
    if j == N:
        print(N)
        sys.exit(0)

ans = j - i
while True:
    i = nexti(i)
    j = nextj(j)
    ans = max(ans, j - i)
    if j == N:
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

reatInt = lambda: int(sys.stdin.readline())
reatIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]


n, k = reatIntN()
ss = sys.stdin.readline().strip()

l = []
i = 0
if ss[0] == '0':
    l.append((1, 0))
else:
    l.append((0, 0))
while i < len(ss):
    c = ss[i]
    while (i < len(ss)) and (c == ss[i]):
        i += 1
    l.append((int(c), i))

i = 1
ret = 0
while i < len(l):
    q = 1 if  l[i][0] == 0 else 0
    b = i - 1
    e = min(i + 2 * k - q, len(l) - 1)
    ret = max(ret, l[e][1] - l[b][1])
    i += 1
print(ret)

Submission status: Accepted

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

wl = []
wc = 0
prevs = None
for i, _s in enumerate(s):
  if prevs is None:
    wl.append(i)
    prevs = _s
    if _s == '0':
      wc += 1
  elif prevs != _s:
    wl.append(i)
    prevs = _s
    if _s == '0':
      wc += 1
wl.append(n)

if k >= wc:
  print(n)
elif s[0] == '0':
  if s[-1] == '0':
    maxl = max(wl[2*k] - wl[0], wl[-1] - wl[-2*k-1])
    for l, r in zip(wl[1::2], wl[2*k+2:-1:2]):
      if r - l > maxl:
        maxl = r - l
  else:
    maxl = wl[2*k] - wl[0]
    for l, r in zip(wl[1::2], wl[2*k+2::2]):
      if r - l > maxl:
        maxl = r - l
  print(maxl)
else:
  if s[-1] == '0':
    maxl = wl[-1] - wl[-2*k-1]
    for l, r in zip(wl[::2], wl[2*k+1:-1:2]):
      if r - l > maxl:
        maxl = r - l
  else:
    maxl = 0
    for l, r in zip(wl[::2], wl[2*k+1::2]):
      if r - l > maxl:
        maxl = r - l
  print(maxl)

Submission status: Accepted

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

l, r = 0, 0
for i in range(K):
    while r < N and s[r] == '1': r += 1
    while r < N and s[r] == '0': r += 1
# K回直立→逆立ちの反転操作を行う
while r < N and s[r] == '1': r += 1
# 元々逆立ちしている人の右端まで行く
ans = r - l
# 区間の人数をansに代入
while r < N:
    while l < r and s[l] == '1': l += 1
    while l < r and s[l] == '0': l += 1
    # 左端を右にずらす
    # 出来るだけ人数が多くなるように区間を縮めるので、
    # 0==直立の区間直後まで動かす
    while r < N and s[r] == '0': r += 1
    while r < N and s[r] == '1': r += 1
    # 右端を右にずらす
    # できるだけ人数が多くなるように区間を広げるので、
    # 1==逆立ちの区間の直後まで動かす
    ans = max(ans, r - l)
    # 区間の人数をansに代入
print(ans)

# 尺取り法

Submission status: Accepted

Solution code:

from itertools import groupby
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, K = tuple(li())
S = stdin.readline() + "2"
# use window
l, r = 0, 0
cnt = 0
r_iter = groupby(S)
l_iter = groupby(S)
r_next = next(r_iter)
l_next = next(l_iter)
while r < N:
    # print(l, r, K)
    if K > 0:
        if r_next[0] == '1' and r > 0:
            K -= 1
        r += len(list(r_next[1]))
        r_next = next(r_iter)
        cnt = max(cnt, r - l)
    elif K == 0 and r_next[0] == "1":
        cnt = max(cnt, r - l)
        r += len(list(r_next[1]))
        r_next = next(r_iter)
        cnt = max(cnt, r - l)
    else:
        if l_next[0] == "0":
            K += 1
        l += len(list(l_next[1]))
        l_next = next(l_iter)
# print(l,r,K)
if r_next[0] == '1':
    cnt = max(cnt, r-l)
print(cnt)

Submission status: Accepted

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

a = [0]
if S[0] == '0':
    a.append(0)
for i in range(N-1):
    if S[i] != S[i+1]:
        a.append(i+1)
a.append(N)
if S[N-1] == '0':
    a.append(N)
r = len(a) // 2 - 1
if K >= r:
    print(N)
else:
    print(max(a[2*(i+K)+1]-a[2*i] for i in range(r-K+1)))

Submission status: Accepted

Solution code:
def d_handstand(N, K, S):
    index_switched = [0]
    for i in range(1, N):
        if S[i] != S[i - 1]:
            index_switched.append(i)
    max_index = max(index_switched)

    ans_candidate = []
    for k in range(len(index_switched)):
        if S[index_switched[k]] == '0':
            ans_candidate.append((index_switched[k + 2 * K] if k + 2 * K
                                  < len(index_switched) else N) - index_switched[k])
        elif S[index_switched[k]] == '1':
            ans_candidate.append((index_switched[k + 2 * K + 1] if k + 2 * K
                                  + 1 < len(index_switched) else N) - index_switched[k])
    return max(ans_candidate)

N, K = [int(i) for i in input().split()]
S = input()
print(d_handstand(N, K, S))

Submission status: Accepted

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

t = []
if s[0] == "0":
    t.append(("1", 0))

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

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

S = [t[0][1]]
rm = [0]
m = len(t)
for i in range(m//2):
    tmp = S[-1]
    S.append(tmp+t[2*i+1][1]+t[2*i+2][1])
    rm.append(tmp+t[2*i+1][1])

ans = []
for i in range(m//2+1):
    if i - k < 0:
        ans.append(S[i])
    else:
        ans.append(S[i]-rm[i-k])
print(max(ans))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, K  = map(int, input().split())
ans = 0
num = 0
S = input()
a = S.split('1')
b = S.split('0')
ls = []
for x in a:
    if len(x) != 0:
        ls.append(len(x))
c = [0] + list(accumulate(ls))
ls_ = []
for x in b:
    if len(x) != 0:
        ls_.append(len(x))
d = [0] + list(accumulate(ls_))

if len(c)-1 <= K:
    print(N)
    sys.exit()

if len(c) == len(d):
    if S[0] == '0':
        d = [0] + d
        for x, y, u, t in zip(c, c[K:], d, d[K+1:]):
            ans = max(ans, y-x+t-u)
        print(ans)
    elif S[0] == '1':
        r = d[-1]
        d.append(r)
        for x, y, u, t in zip(c, c[K:], d, d[K+1:]):
            ans = max(ans, y-x+t-u)
        print(ans)
elif len(c) == len(d)+1:
    r = d[-1]
    d.append(r)
    d = [0] + d
    for x, y, u, t in zip(c, c[K:], d, d[K+1:]):
        ans = max(ans, y-x+t-u)
    print(ans)
elif len(c) == len(d)-1:
    for x, y, u, t in zip(c, c[K:], d, d[K+1:]):
        ans = max(ans, y-x+t-u)
    print(ans)

Submission status: Accepted

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

now = 1
cnt = 0
nums = []
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

# Calculate cumulative sums
cum_sum = [0]
for i in range(0, len(nums)):
    cum_sum.append(cum_sum[i] + nums[i])

# Solve
ans = 0
for i in range(0, len(nums), 2):
    l = i
    r = min(i + add, len(nums))
    ans = max(ans, cum_sum[r] - cum_sum[l])

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
l = []
a = 0
if S[0] == '1':
	a += 1
else:
	l.append(a)
	a += 1
for i in range(1, N, 1):
	if S[i] == S[i - 1]:
		a += 1
	else:
		l.append(a)
		a = 1
l.append(a)
if S[N - 1] == '0':
	l.append(0)
if (len(l) + 1) // 2 - K < 1:
	print(N)
else:
	ans = sum(l[0:2 * K + 1])
	n_ans = ans
	for k in range((len(l) - 1) // 2 - K):
		n_ans += l[2 * k + 2 * K + 1] + l[2 * k + 2 * K + 2] - l[2 * k] - l[2 * k + 1]
		ans = max(ans, n_ans)
	print(ans)

Submission status: Accepted

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

fpos_list = []
ps = ''
for i in range(len(S)):
    if ps != S[i]:
        fpos_list.append([i, S[i]])
        ps = S[i]

ans = 0
for i in range(len(fpos_list)):
    bp = fpos_list[i][0]
    bs = fpos_list[i][1]
    l = 0
    if bs == '0':
        ep = N
        if i+2*K < len(fpos_list):
            ep = fpos_list[i+2*K][0]
        l = ep-bp
    else:
        ep = N
        if i+1+2*K < len(fpos_list):
            ep = fpos_list[i+1+2*K][0]
        l = ep-bp
    if l > ans:
        ans = l
    # debug
    #print('i: ', i)
    #print('bp: ', bp)
    #print('bs: ', bs)
    #print('l: ', l)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
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)

add = 2 * K + 1

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

ans = 0
for i in range(len(nums)):
  if i % 2 == 1:
    continue
  
  left = i
  right = min(i + add, len(nums))
  tmp = sums[right] - sums[left]

  ans = max(tmp, ans)

print(ans)

Submission status: Accepted

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

i = 0
d = []
while i <= n:
    if s[i] == '0':
        d.append(i)

    else:
        if d != []:
            l.append(d)
            d = []
    i += 1

#print(l)

m = 0
nl = len(l)

for i in range(max(nl - k + 1, 1)):
    start = l[i - 1][-1] + 1 if i != 0 else 0
    goal = l[min(i + k, nl - 1)][0] - 1 if not i + k > nl - 1 else n - 1
    #print(start, goal)
    m = max(m, goal - start + 1)

print(m)

Submission status: Accepted

Solution code:
from itertools import accumulate

def f():
     n, k = map(int,input().split())
     p = list(input())
     a = [] 
     pre = '1'
     cnt = 0
     for i in range(n):
          if pre != p[i]:
               a.append(cnt)
               cnt = 1
               pre = p[i]
          else:
               cnt += 1
     a.append(cnt)
     if pre == '0':
          a.append(0)

     w = 2*k+1

     if w >= len(a):
          return n
     else:
          acc = [0] + list(accumulate(a))
          ans = 0
          for i in range(0,len(a)-w+1,2):
               ans = max(ans,acc[i+w]-acc[i])
          return ans
          
print(f())

Submission status: Accepted

Solution code:
#参考　https://atcoder.jp/contests/abc124/submissions/4948803
from itertools import accumulate

def f():
     n, k = map(int,input().split())
     p = list(input())
     a = [] 
     pre = '1'
     cnt = 0
     for i in p:
          if pre != i:
               a.append(cnt)
               cnt = 1
               pre = i
          else:
               cnt += 1
     a.append(cnt)
     if pre == '0':
          a.append(0)

     w = 2*k+1

     if w >= len(a):
          return n
     else:
          acc = [0] + list(accumulate(a))
          ans = 0
          for i in range(0,len(a)-w+1,2):
               ans = max(ans,acc[i+w]-acc[i])
          return ans
          
print(f())

Submission status: Accepted

Solution code:
import re
import numpy as np
N, K = [int(item) for item in re.split(r"\s", input())]
S = [int(item) for item in list(input())]

if sum(S) == len(S) or sum(S) == 0:
    print(len(S))
else:
    S = S + [2]

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

    count = np.diff(np.array(index)).tolist()

    if S[0] == 0:
        count = [0] + count
    if S[-2] == 0:
        count = count + [0]

    # print(index)
    #print("count", count)

    cumsum = [0] + np.cumsum(count).tolist()
    c_len = len(cumsum)
    win = min(2 * K + 1, c_len - 1)
    # print(cumsum)
    # print(win)

    print(max([cumsum[i + win] - cumsum[i] for i in range(0, c_len - win, 2)]))

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
S = input()
arr_0,arr_1 = [],[]
val = 1
temp = S[0]
if temp == '0':
    arr_1 += [0]
for s in S[1:]+"_":
    if s == temp:
        val+=1
    else:
        if temp=="1":
            arr_1 += [val]
        else:
            arr_0 += [val]
        val = 1
    temp = s
if S[-1] == "0":
    arr_1 += [0]

max_ = sum(arr_0[:K]+arr_1[:K+1])
for i in range(1, len(arr_0)-K+1):
    if (arr_0[i+K-1]+arr_1[i+K]) > (arr_0[i-1]+arr_1[i-1]):
        tmp = sum(arr_0[i:i+K])+sum(arr_1[i:i+K+1])
        if tmp > max_:
            max_ = tmp
print(max_)

Submission status: Accepted

Solution code:
#参考　https://atcoder.jp/contests/abc124/submissions/4948803
from itertools import accumulate

n, k = map(int,input().split())
p = list(input())
a = []
pre = '1'
cnt = 0
for i in range(n):
     if pre != p[i]:
          a.append(cnt)
          cnt = 1
          pre = p[i]
     else:
          cnt += 1
a.append(cnt)
if pre == '0':
     a.append(0)

w = 2*k+1

if w >= len(a):
     print(n)
else:
     acc = list(accumulate(a))
     ans = 0
     acc = [0] + acc
     for i in range(0,len(a)-w+1,2):
          ans = max(ans,acc[i+w]-acc[i])
     print(ans)

Submission status: Accepted

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

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            if ind == 0:
                line[ind] = counter1
            else:
                line[ind] = line[ind-1]+counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = line[ind-1] + counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        if ind == 0:
                line[ind] = counter1
        else:
                line[ind] = line[ind-1]+counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = line[ind-1] + counter0
        ind+=1
        
if ind%2 ==0:
        line[ind] = line[ind-1]
        ind+=1
        
line[1:ind+1]  = line[:ind]   
line[0] = 0 
line = line[:ind+1]
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    maxchain = 0
    for i in range(0,len(line)-2*k,2):
        chain = line[i+2*k+1]-line[i]
        #print(chain)
        if chain>maxchain:
            maxchain=chain
    print(maxchain)

Submission status: Accepted

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

cnt = 1
cntlist = []
for i in range(1, N):
    if s[i - 1] != s[i]:
        cntlist.append(cnt)
        cnt = 1
    else:
        cnt += 1

cntlist.append(cnt)
if s[0] == "0":
    cntlist = [0] + cntlist

ans = 0
for i in range(2 * K + 1):
    if i >= len(cntlist):
        break
    ans += cntlist[i]
anslist = [ans]
s = 0
g = 2 * K + 1
while g < len(cntlist):
    ans -= cntlist[s]
    ans -= cntlist[s + 1]
    s += 2
    ans += cntlist[g]
    g += 1
    if g >= len(cntlist):
        anslist.append(ans)
        break
    ans += cntlist[g]
    g += 1
    anslist.append(ans)

print(max(anslist))

Submission status: Accepted

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

S = input()
para = [0]
for i, s in enumerate(S):
    if i == 0:
        para.append(1)
    else:
        if S[i] == S[i-1]:
            para[-1] += 1
        else:
            para.append(1+para[-1])

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


i = 0

tmpmax = 0

if S[0] == '1':
    if i + 2*k + 1 >= len(para) - 1:
        print(n)
    else:
        while i + 2*k + 1 <= len(para) - 1:
            j = i + 2*k + 1
            tmpmax = max(tmpmax, para[j] - para[i])

            i += 2
        print(tmpmax)

else:
    if i + 2*k >= len(para) - 1:
        print(n)
    else:
        while i + 2*k <= len(para) - 1:
            j = i + 2*k
            if i == 0:
                tmpmax = max(tmpmax, para[j] - para[i])
            else:
                tmpmax = max(tmpmax, para[j] - para[i-1])

            i += 2
        print(tmpmax)