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 groupby
N, K = map(int,input().split())
S = list(input())
Sg = groupby(S)
L = []
if S[0] =="0":
  L.append(0)
for k, g in Sg:
  L.append(len(list(g)))
if S[-1] == "0":
  L.append(0)
#print(L)
acu = [0]
for i in range(len(L)):
  acu.append(acu[-1] + L[i])
#print(acu)
ans = 0
for left in range(0,len(acu),2):
  right = min(left + 2 * K + 1,len(acu) - 1)
  ans = max(ans,acu[right] - acu[left])
print(ans)

Submission status: Accepted

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

tmp, cnt = s[0], 0
for x in s:
    if x != tmp:
        ls.append((tmp, cnt))
        if tmp == 0: stand_ls.append(len(ls)-1)
        cnt = 0
        tmp = x
    cnt += 1
    
if len(ls) == 1 and ls[0][0] == 1: print(ls[0][1]); exit()

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i][1]
    return cs

cum = cumsum(ls)

ans = 0
k = min(k, len(stand_ls))
for i in range(len(stand_ls) - (k-1)):
    l, r = stand_ls[i], stand_ls[i+k-1]
    if l > 0: l -= 1
    if r < len(ls)-1: r += 1
    ans = max(ans, cum[r+1] - cum[l])
print(ans)

Submission status: Accepted

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


n,k = MAP()
s = input()
k*=2

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

r = len(lst)
lst += [n]
ans=[]
for i in range(r):
    if s[lst[i]]=="0":
        ans.append(lst[min(i+k,r)] - lst[i])
    else:
        ans.append(lst[min(i+k+1,r)] - lst[i])

print(max(ans))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
prev = "1"
count = 0
blocks = []
for i,s in enumerate(S):
    if s != prev:
        blocks.append(count)
        prev = s
        count = 1
    else:
        count += 1
blocks.append(count)
if len(blocks) % 2 == 0:
    blocks.append(0)
if len(blocks) // 2 <= K:
    print(sum(blocks))
else:
    ps = sum(blocks[:2*K+1])
    cur_max = ps
    for i in range(2*(K+1),len(blocks),2):
        ps += blocks[i-1] + blocks[i]
        ps -= blocks[i-2-2*K] + blocks[i-1-2*K]
        cur_max = max(cur_max,ps)
    print(cur_max)

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
S = input()
s1 = []
s0 = []
if S[0] == '0':
    s1.append(0)

tmp = S[0]
cnt = 1
for s in S[1:]:
    if tmp != s:
        if tmp == '0':
            s0.append(cnt)
        else:
            s1.append(cnt)
        cnt = 0
    tmp = s
    cnt += 1
if tmp == '0':
    s0.append(cnt)
    s1.append(0)
else:
    s1.append(cnt)

val = 0

j = 0
for i in range(min(K, len(s0))):
    val += s0[i] + s1[i]
    j = i + 1
val += s1[j]
l = 0

pre = val
for i in range(j, len(s0)):
    tmp = pre - s0[l] - s1[l]
    tmp += s0[i] + s1[i + 1]
    val = max(val,tmp)
    l += 1
    pre = tmp
print(val)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
cnt=0
ans=0
j=0
for i in range(n):
    if s[i]=="0":
        if i==0 or s[i-1]=="1":
            cnt+=1
    if cnt>k:
        while s[j]=="1":
            j+=1
        while s[j]=="0":
            j+=1
        cnt-=1
    ans=max(ans,i-j+1)

print(ans)

Submission status: Accepted

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

l = 0
count = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate
N, K = map(int, input().split())
S = groupby(list(input()))
state = []
number = []
for i, j in S:
    state.append(i)
    number.append(len(list(j)))

answer = 0

if len(state) == 1:
    print(number[0])
    exit()

number = list(accumulate([0] + number))
l = len(number) - 1

if state[0] == '0':
    answer = number[min(l, 2 * K)] - number[0]

start = state.index('1') + 1
for i in range(start, l + 1, 2):
    answer = max(answer, number[min(2 * K + i, l)] - number[i - 1])

print(answer)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
b=[1]
if s[0]=="0":b=[0,1]
for i in range(1,n):
  if s[i-1]!=s[i]:b+=[1]
  else:b[-1]+=1
if s[-1]=="0":b+=[0]
if len(b)//2<=k:print(n);exit()
#print(b)

x=a=sum(b[:k*2+1])
#print(b[:k*2+1])
for i in range(k,len(b)//2):
  a+=b[i*2+1]+b[(i+1)*2]
  a-=b[(i-k)*2]+b[(i-k)*2+1]
  x=max(a,x)
  #print(b[(i-k)*2+2:(i+1)*2+1])
print(x)

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
ans = 0
l = 0
r = 0
tmp = 0

for i in range(0,len(nums),2):
    nl = i
    nr = min(i+add,len(nums))
    
    while nl > l:
        tmp -= nums[l]
        l += 1
    while nr > r:
        tmp += nums[r]
        r += 1
    ans = max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
# D - Handstand

# 逆立ちしている人が連続する区間のインデックスを保存する
# 指示1回あたり2つの区間を繋ぐことができる
# 連続したK+1個の区間を順に選んで繋ぎ、最も逆立ち区間が長くなる場合を探す。端から繋ぐ場合は例外処理

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

if len(set(S)) == 1:
    print(N)
    exit()

handstand_range_idx = []
range_start_idx = 0
for idx in range(1,N):
    if (S[idx-1] == "1" and S[idx] == "0"):
        range_end_idx = idx - 1
        handstand_range_idx.append([range_start_idx, range_end_idx])
    elif idx == N-1 and S[idx] == "1":
        range_end_idx = idx
        handstand_range_idx.append([range_start_idx, range_end_idx])
    elif S[idx-1] == "0" and S[idx] == "1":
        range_start_idx = idx

ans = 0
try:
    ans = max(handstand_range_idx[K-1][1]+1, (N-1) - handstand_range_idx[-K][0] + 1)
except IndexError: # 逆立ち区間の数が操作回数よりも少ない場合
    print(N)
    exit()

for first_link_range_idx in range(len(handstand_range_idx)):
    try:
        ans = max(ans, handstand_range_idx[first_link_range_idx + K][1] - handstand_range_idx[first_link_range_idx][0] + 1)
    except IndexError:
        pass

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
X,Y=[],[]
M=0
for i in range(len(S)):
  if(S[i]=='1' and M==0):
    X.append(i)
    M+=1
  elif(S[i]=='1'):
    M+=1
  else:
    if(M):
      Y.append(i-1)
    M=0
if(M):
  Y.append(len(S)-1)
ans=0
if(len(X)>=K):
  for i in range(len(X)-K):
    ans=max(ans,Y[i+K]-X[i]+1)
else:
  ans=len(S)
if(len(X)):
  ans=max(ans,Y[min(K-1,len(X)-1)]+1)
  ans=max(ans,len(S)-X[max(len(X)-K,0)])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
S = list(input()) + ['2']

blocks = []
cur = 1
seq = 0
for s in S:
    if int(s) == cur:
        seq += 1
    else:
        blocks.append(seq)
        cur = 1 - cur
        seq = 1
answer = 0
blocks = np.array(blocks)
for i in range(0, len(blocks), 2):
    answer = max(answer, blocks[i:i+2*K+1].sum())
print(answer)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
a=[]
f=1
s.append(2)
for i in range(n):
    if s[i]==s[i+1]:
        f+=1
    else:
        a.append(f)
        f=1
g=len(a)
r=[0]*(g+1)
for i in range(g):
    r[i+1]=r[i]+a[i]
if s[0]=='1':
    ans=sum(a[0:2*k+1])
    if s[-2]=='0':
        ans=max(ans,sum(a[max(0,g-2*k):g]))
    for i in range(g):
        if 2*i+2*k+1<g+1:
            ans=max(ans,r[2*i+2*k+1]-r[2*i])
        else:
            break
    print(ans)
else:
    ans=sum(a[0:2*k])
    if s[-2]=='0':
        ans=max(ans,sum(a[max(0,g-2*k):g]))
    for i in range(g):
        if 2*i+2*k+2<g+1:
            ans=max(ans,r[2*i+2*k+2]-r[2*i+1])
        else:
            break
    print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def slove():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    s = str(input().rstrip('\n'))
    ls = []
    cnt = 1
    for i in range(1, n):
        if s[i] != s[i-1]:
            ls.append(cnt)
            cnt = 0
        cnt += 1
    ls.append(cnt)

    wc = 0
    b = True if s[0] == "1" else False
    fb = True if s[0] == "1" else False
    cnt = 0
    pos = 0
    m_cnt = 0
    for i in range(len(ls)):
        if not b:
            wc += 1
        if wc > k:
            cnt -= ls[pos]
            pos += 1
            if fb:
                cnt -= ls[pos]
                pos += 1
            else:
                fb = not b
            wc -= 1
        b = not b
        cnt += ls[i]
        m_cnt = max(m_cnt, cnt)
    print(m_cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K=map(int,input().split())
S=input()
l=[0]
t="1"
for i in S:
    if t==i:
        l[-1]+=1
    else:
        l.append(1)
        if t=="1":
            t="0"
        else:
            t="1"
if t=="0":
    l.append(0)
a=sum(l[:2*K+1])
A=a
for i in range(2*K+2,len(l),2):
    a+=l[i]+l[i-1]
    a-=l[i-2*K-2]+l[i-2*K-1]
    A=max(A,a)
print(A)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
S = str(input())
S = S + "2"
d1 = []
d0 = []
k = S[0]
if k=="0":
    d1.append(0)
cou = int(1)
for i in range(N):
    if S[i]!=S[i+1]:
        if S[i]=="0":
            d0.append(cou)
        if S[i]=="1":
            d1.append(cou)
        cou = int(1)
    else:
        cou +=1

#print(d1)
#print(d0)

ansC = []
t = 2*K+1
newN = len(d1)
if len(d1)==1 or d0==[] or K>=N//2+1:
    ansC.append(N)

if newN!=len(d0):
    d0.append(0)
    d0.append(0)
sumd1 = [0]*(newN+t+5)
sumd0 = [0]*(newN+t+5)
for i in range(newN):
    sumd1[i+1] = d1[i]
    sumd0[i+1] = d0[i]
for i in range(newN+1):
    sumd1[i+1] += sumd1[i]
    sumd0[i+1] += sumd0[i]

#for i in range(max(newN-K+1,K)):
if ansC==[] and (newN - K + 1)>=1:
    for i in range(newN - K + 1):
        ans = (sumd1[i + K + 1] - sumd1[i]) + (sumd0[i + K] - sumd0[i])
        ansC.append(ans)
else:
    ansC.append(N)
print(max(ansC))

Submission status: Accepted

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

a_list = []
b_list = []

if s[0] == "0":
    a_list.append(0)
p = 0
for i in s:
    if i == "1" and p < 0:
        b_list.append(-p)
        p = 1
    elif  i == "1" and p >= 0:
        p += 1
    elif  i == "0" and p > 0:
        a_list.append(p)
        p = -1
    elif  i == "0" and p <= 0:
        p -= 1
if p < 0:
    b_list.append(-p)
    a_list.append(0)
else:
    a_list.append(p)


if len(b_list) <= k:
    ans = n
else:
    m = len(b_list) - k
    sequence = sum(a_list[:k+1]) + sum(b_list[:k])
    ans = sequence
    for i in range(m):
        sequence += a_list[i+k+1] - a_list[i]
        sequence += b_list[i+k] - b_list[i]
        ans = max(sequence, ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
S = input()
lst = []
if (S[0] == '0'): lst.append(0)
cnt = 1
for i in range(N-1):
    if (S[i] == S[i+1]):
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1 
lst.append(cnt)
if (S[-1] == '0'): lst.append(0)
tmp = [0] + lst[:]
ans = 0 if (len(lst) != 1) else lst[0] 
for i in range(len(lst)):
    tmp[i+1] += tmp[i]
if (((len(lst)+1)//2-K) < 1):
    ans = tmp[-1]
else:
    for i in range(0, (len(lst)+1)//2-K):
        l = 2*i
        r = l + 1 + 2*K
        s = tmp[r] - tmp[l]
        if (ans < s):
            ans = s
print(ans)

Submission status: Accepted

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

now = 1
cnt = 0
for s in S:
    if str(now) == s:
        cnt += 1
    else:
        Data.append(cnt)
        cnt = 1
        now = 1 - now
if cnt > 0:
    Data.append(cnt)
if now == 0:
    Data.append(0)

DataSum = [0]
for i in range(len(Data)):
    DataSum.append(Data[i]+DataSum[i])

#print(Data)
#print(DataSum)

len1 = min(2*K+1,len(Data))
ans = 0
for i in range(0,len(Data)-len1+1,2):
    left = i
    right =i+len1
    sum1 = 0
    #for j in range(left,right):
    #    sum1 += Data[j]
    sum1 = DataSum[right]-DataSum[left]
    ans = max(ans,sum1)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

cur = 1 # 最初は1が0人立っている
blocks = np.zeros(10**5+1, dtype = np.int64)
seq = 0
p = 0
for s in S:
    if s == cur:
        blocks[p] += 1
    else:
        p += 1
        blocks[p] += 1        
        cur = 1 - cur
W = min(2*K, 10**5)
answer = sum = blocks[:W+1].sum()
for i in range(W+1, 10**5, 2):
    if i+1 > 10 ** 5:
        break
    sum = sum + blocks[i] + blocks[i+1] - blocks[i-W-1] - blocks[i-W]
    if sum > answer:
        answer = sum
print(answer)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s=s+"w"
lists0=[]
lists1=[] 
count=0
for i in range(n):
    if s[i]!=s[i+1] and s[i]=="0":
        lists0.append(i-count)
        count=i
        
    elif s[i]!=s[i+1] and s[i]=="1":
        lists1.append(i-count)
        count=i

if s[0]=="1":
    lists1[0]+=1
elif s[0]=="0":
    lists0[0]+=1     
#下準備の完成
if s[0]=="1" and s[-2]=="1":
    #do nothing special
    if k>=len(lists0):
        print(n)
    elif k<len(lists0):
        big=0
        ans=sum(lists1[:k+1])+sum(lists0[:k])
        for i in range(len(lists0)-k):
            ans1=ans+lists1[k+1+i]+lists0[k+i]-lists1[i]-lists0[i]
            big=max(big,max(ans,ans1))
            ans=ans1
        print(big)
       
        
elif s[0]=="1" and s[-2]=="0":
    # 最後にlists1の方に0を挿入する
    lists1.append(0)

    if k>=len(lists0):
        print(n)
    elif k<len(lists0):
        big=0
        ans=sum(lists1[:k+1])+sum(lists0[:k])
        for i in range(len(lists0)-k):
            ans1=ans+lists1[k+1+i]+lists0[k+i]-lists1[i]-lists0[i]
            big=max(max(ans,ans1),big)
            ans=ans1
        print(big)
    
elif s[0]=="0" and s[-2]=="1":
    #さいしょのlist1の方に0を挿入する
    lists1.insert(0,0)

    if k>=len(lists0):
        print(n)
    elif k<len(lists0):
        big=0
        ans=sum(lists1[:k+1])+sum(lists0[:k])
        for i in range(len(lists0)-k):
            ans1=ans+lists1[k+1+i]+lists0[k+i]-lists1[i]-lists0[i]
            big=max(big,max(ans,ans1))
            ans=ans1
        print(big)    
elif s[0]=="0" and s[-2]=="0":
    #最初と最後にlist1の方に0を挿入する
    lists1.insert(0,0)
    lists1.append(0)

    if k>=len(lists0):
        print(n)
    elif k<len(lists0):            
        big=0
        ans=sum(lists1[:k+1])+sum(lists0[:k])
        for i in range(len(lists0)-k):
            ans1=ans+lists1[k+1+i]+lists0[k+i]-lists1[i]-lists0[i]
            big=max(big,max(ans,ans1))
            ans=ans1
        print(big)

Submission status: Accepted

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

tmp = S[0]
l = [0]
for i in range(N):
    if S[i] != tmp:
        l.append(i)
        tmp = S[i]
r = len(l)
l.extend([N] * (K*2 + 1))    

x = [0] * (r)
for i in range(r):
    if S[l[i]] == 0:
        x[i] = l[i+K*2] - l[i]
    else:
        x[i] = l[i+K*2+1] - l[i]
        
print(max(x))

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
S = np.array([int(x) for x in input()] + [2])

blocks = [] # 同じ数の塊
seq = 1
for i in range(N):
    if S[i+1] == S[i]:
        seq += 1
    else:
        blocks.append(seq)
        seq = 1
blocks = np.array(blocks)

answer = blocks[:2*K].sum()

start = 0 if S[0] == 1 else 1
for i in range(start, len(blocks), 2):
    answer = max(answer, blocks[i:i+(2*K+1)].sum())

print(answer)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(map(int, input()))
lst = []
cnt = 0
now = 1

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

#1 0 1 0 1の形にしたい
if len(lst) % 2 == 0:
	lst.append(0)

ret = 0
add = 2 * K + 1
left = 0
right = 0
total = 0

for i in range(0, len(lst), 2):
	nextleft = i
	nextright = min(i + add, len(lst))
	while nextleft > left:
		total -= lst[left]
		left += 1
	while nextright > right:
		total += lst[right]
		right += 1
	ret = max(ret, total)
	
print(ret)

Submission status: Accepted

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


def main():
    from itertools import accumulate

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

    nums = list()
    now = 1
    count = 0

    # See:
    # https://www.youtube.com/watch?v=FRzpDCx17vw
    # 1と0が連続していくつ続いているかを数える
    # 一つの配列で管理
    for si in s:
        if si == str(now):
            count += 1
        else:
            nums.append(count)
            now = 1 - now  # 0と1を切り替える
            count = 1

    # 端部の処理
    if count != 0:
        nums.append(count)

    # 1-0-1-0-1の形になっている必要がある
    if len(nums) % 2 == 0:
        nums.append(0)

    add = 2 * k + 1

    # 累積和
    summed = list(accumulate([0] + nums))

    tmp = 0
    ans = 0

    # 偶数番目に着目
    for i in range(0, len(nums), 2):
        left = i
        right = min(i + add, len(nums))
        tmp = summed[right] - summed[left]

        ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    nums = list()
    now = 1
    count = 0

    # See:
    # https://www.youtube.com/watch?v=FRzpDCx17vw
    # 1と0が連続していくつ続いているかを数える
    # 一つの配列で管理
    for si in s:
        if si == str(now):
            count += 1
        else:
            nums.append(count)
            now = 1 - now  # 0と1を切り替える
            count = 1

    # 端部の処理
    if count != 0:
        nums.append(count)

    # 1-0-1-0-1の形になっている必要がある
    if len(nums) % 2 == 0:
        nums.append(0)

    add = 2 * k + 1

    # 1. left，rightをfor文の前に
    left = 0
    right = 0  # [left, right)
    tmp = 0
    ans = 0

    # 偶数番目に着目
    for i in range(0, len(nums), 2):
        # 2. 次のleft, rightを決める
        next_left = i
        next_right = min(i + add, len(nums))

        # 3.
        # 左端を移動
        while next_left > left:
            tmp -= nums[left]
            left += 1

        # 右端を移動
        while next_right > right:
            tmp += nums[right]
            right += 1

        ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    nums = list()
    now = 1
    count = 0

    for si in s:
        if si == str(now):
            count += 1
        else:
            nums.append(count)
            now = 1 - now
            count = 1

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

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

    add = 2 * k + 1

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

    for i in range(0, 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(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate
N, K = map(int, input().split())
S = input()
g_cnt = [len(list(v)) for k, v in groupby(S)]
ans = 1

if S[0]=="0":
    g_cnt = [0] + g_cnt
if S[-1]=="0":
    g_cnt = g_cnt + [0]
    
accum = [0] + list(accumulate(g_cnt))
ans = 0
for i in range(0, len(accum), 2):
    r = i+2*K+1
    if r>=len(accum):
        r = len(accum)-1
    ans = max(ans , accum[r]-accum[i])
print(ans)

Submission status: Accepted

Solution code:
# 2019/10/10

n,k=map(int,input().split())
s=list(input())+[None]

cnt=1
ss=[]
if s[0]=='0':ss.append(0)

i=1
while i<=n:
    if s[i]==s[i-1]:
        cnt+=1
    else:
        ss.append(cnt)
        cnt=1
        
    i+=1

if s[-2]=='0':ss.append(0)
nn=len(ss)
k=min(nn//2,k)
res=sum(ss[:k*2+1])
cnt=res
l=0
for r in range(k*2+2,nn,2):
    cnt-=(ss[l]+ss[l+1])
    cnt+=(ss[r]+ss[r-1])
    res=max(res,cnt)
    l+=2

print(res)

Submission status: Accepted

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

L = S.replace('01', '0,1')
L = L.replace('10', '1,0')
L = L.split(',')
L = [len(l) for l in L]

if S[0] == '0':
    L = [0] + L

R = []
for i in range(max(1, len(L) // 2 + 1 - K)):
    if i == 0:
        R.append(sum(L[2*i:2*(i+K)+1]))
    else:
        R.append(R[-1] - sum(L[2*(i-1):2*(i-1)+2]) + sum(L[2*(i+K)-1:2*(i+K)+1]))

print(max(R))

Submission status: Accepted

Solution code:
# 累積和
from sys import exit

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

p = '1'
count = 0
cs = []
for c in S:
    if c != p:
        cs.append(count)
        p = c
        count = 1
    else:
        count += 1
cs.append(count)
if p != '1':
    cs.append(0)

if len(cs) < 2 * K:
    print(N)
    exit()

for i in range(1, len(cs)):
    cs[i] += cs[i - 1]

result = cs[2 * K]
for i in range(2, len(cs) - 2 * K, 2):
    if cs[2 * K + i] - cs[i - 1] > result:
        result = cs[2 * K + i] - cs[i - 1]
print(result)

Submission status: Accepted

Solution code:
# 累積和
from sys import exit

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

p = '1'
count = 0
cs = []
for c in S:
  if c != p:
    cs.append(count)
    p = c
    count = 1
  else:
    count += 1
cs.append(count)
if p == '0':
  cs.append(0)

if len(cs) < 2 * K:
  print(N)
  exit()

for i in range(1, len(cs)):
  cs[i] += cs[i - 1]

result = cs[2 * K]
for i in range(2, len(cs) - 2 * K, 2):
  t = cs[2 * K + i] - cs[i - 1]
  if t > result:
    result = t
print(result)

Submission status: Accepted

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

a = []

now = S[0]
cnt = 1
for x in S[1:]:
    if x == now:
        cnt += 1
    else:
        a.append(cnt)
        now = x
        cnt = 1
a.append(cnt)

#偶数番目に0の数、奇数番目に1の数
if S[0] == "0":
    a = [0] + a
if S[-1] == "0":
    a = a + [0]

#print(a)

m = len(a)

if 2 * K + 1 >= m:
    maxsum = N
else:
    l = 0
    r = 2 * K + 1
    nowsum = sum(a[l : r])
    maxsum = nowsum
    while True:
        l += 2
        r += 2
        if r > m:
            break
        nowsum += a[r - 2] + a[r - 1] - (a[l - 2] + a[l - 1])
        maxsum = max(maxsum , nowsum)

print(maxsum)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

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

hoge = N*3 + 3

imos = [0]*(hoge)
imosInd = 2
cnt = 1
ind = 1
while ind < N:
    if S[ind] == S[ind-1]:
        cnt += 1
    else:
        imos[imosInd] = cnt
        cnt = 1
        imosInd += 1

    ind += 1
imos[imosInd] = cnt

for i in range(2, hoge):
    imos[i] += imos[i-1]


if S[0] == '1':
    ind = 2
else:
    ind = 1

ans = 0

while ind + K*2 < hoge:
    ans = max(ans, imos[ind + K*2] - imos[ind-1])
    ind += 2

print(ans)

Submission status: Accepted

Solution code:
# 左から，逆立ちしている人(1)が連続して並んでいる人数，直立している人(0)が連続して並んでいる人数を順にaに格納していく。
# 一番左の人が直立している(0)ときは，aの先頭に0を追加し，a[0]=0とする。
# 一番右の人が直立している(0)ときにも，aの末尾に0を追加する。
# この操作により，aの最初と最後は，逆立ちしている人(1)の人数となる。
# m=len(a))はN人の人が何ブロックに分かれるかを表す。ただし，最初又は最後に付加され得る，0人の逆立ちしている人から成るブロックを含む。このときmは奇数なので，m=2*l+1と表せる(l>=0)。
# i回の操作により，1のブロックから始まる連続した2*i+1ブロックの全員を1とできる。
# K>=l=(m-1)//2,すなわち2*K+1>=mであれば，N人全員を1にできる。
# K<(m-1)//2であれば，「aの偶数番目の要素a[j]から始まる連続した2*K+1個の要素(a[j+2*K]まで(この要素を含む。))の総和の人数」の最大値を1にできる。(j+2*K<=m-1=2*l,よってj<=2*(l-K))

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

now=S[0]
cnt=1
for c in S[1:]:
    if c==now:
        cnt+=1
    else:
        a.append(cnt)
        now=c
        cnt=1
a.append(cnt)

if S[0]=='0':
    a=[0]+a
if S[-1]=='0':
    a=a+[0]

# print(a)

m=len(a) # m=2*l+1

# print(m)

if 2*K+1>=m:
    ans=N
else:
    l=0;r=2*K+1
    nowsum=sum(a[l:r])
    # print(l,r,nowsum)
    maxsum=nowsum
    while True:
        l+=2;r+=2
        if r>m:
            break
        nowsum=nowsum-a[l-2]-a[l-1]+a[r-2]+a[r-1]  
        maxsum=max(maxsum,nowsum)
        # print(l,r,nowsum)
    ans=maxsum
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = list(map(int,input()))
num = 1
T = []
if S[0] == 0:
    T.append(0)
for i in range(1,N):
    if S[i-1] != S[i]:
        T.append(num)
        num = 0
    num += 1
T.append(num)
if S[N-1] == 0:
    T.append(0)
#index 0,2,4...に1の連続数、1,3,5...に0の連続数
if K >= len(T)//2:
    print(N)
else:
    x = sum(T[0:2*K+1])
    ans = x
    for i in range(1,(len(T)//2)-K+1):
        x = x-(T[2*i-2]+T[2*i-1])+(T[2*i+2*K-1]+T[2*i+2*K])
        ans = max(ans,x)
    print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input() + "#"
A = []
cnt = 1
for i in range(N) :
    if S[i] == S[i+1] :
        cnt += 1
    else :
        A.append(cnt)
        cnt = 1

if S[0] == "1" :
    ans = sum(A[:2*K+1])
    calc = ans
    for i in range(2*K+1, len(A)) :
        calc += A[i]
        if i % 2 == 1 :
            calc -= (A[i-1-2*K] + A[i-2*K])
        ans = max(ans, calc)
else :
    ans = sum(A[:2*K])
    calc = ans
    for i in range(2*K,len(A)) :
        calc += A[i]
        if i == 2*K :
            calc -= A[0]
        elif i % 2 == 0  :
            calc -= (A[i-1-2*K] + A[i-2*K])
        ans = max(ans, calc)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

    A = []
    tmp = S[0]
    cnt = 0
    for i in range(len(S)):
        if S[i] == tmp:
            cnt += 1
        else:
            A.append(cnt)
            tmp = S[i]
            cnt = 1
    else:
        A.append(cnt)

    B = list(itertools.accumulate([0] + A))
    ans = 0
    if S[0] == '1':
        for i in range(1,len(B)+1,2):
            right = i + 2 * K
            if right >= len(B):
                right = len(B) - 1
            tmp = B[right]-B[i-1]
            ans = max(ans, B[right]-B[i-1])
    if S[0] == '0':
        C = [0] + B
        for i in range(1,len(C)+1,2):
            right = i + 2 * K
            if right >= len(C):
                right = len(C) - 1
            tmp = C[right]-C[i-1]
            ans = max(ans, C[right]-C[i-1])

    print(ans)

    
main()

Submission status: Accepted

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

L0 = []
L1 = []
temp = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == "0":
        if temp == "0":
            cnt += 1
        else:
            L1.append(cnt)
            temp = "0"
            cnt = 1
    else:
        if temp == "1":
            cnt += 1
        else:
            L0.append(cnt)
            temp = "1"
            cnt = 1
if S[-1] == "0":
    L0.append(cnt)
else:
    L1.append(cnt)

ans = 0
if S[0] == "0":
    if K >= len(L0):
        ans += N
    else:
        for i in range(K):
            ans += L0[i]+L1[i]
        i = K
        temp = ans
        while i < len(L0):
            if i-K == 0:
                temp -= L0[i-K]
            else:
                temp -= L0[i-K]+L1[i-K-1]
            if i == len(L1):
                temp += L0[i]
            else:
                temp += L0[i]+L1[i]
            if ans < temp:
                ans = temp
            i += 1
else:
    if K >= len(L0):
        ans += N
    else:
        for i in range(K):
            ans += L0[i]+L1[i]
        ans += L1[K]
        i = K
        temp = ans
        while i < len(L0):
            temp -= L0[i-K]+L1[i-K]
            if S[-1] == "0" and i == len(L1)-1:
                temp += L0[i]
            else:
                temp += L0[i]+L1[i+1]
            if ans < temp:
                ans = temp
            i += 1
            
print(ans)

Submission status: Accepted

Solution code:
# しゃくとり法
N, K = map(int, input().split())
S = list(map(int, input()))

j = 1
r = 0
t = []
for i in range(N):
    if S[i] == j:
        r += 1
    else:
        t.append(r)
        r = 1
        j ^= 1
t.append(r)
if j == 0:
    t.append(0)

if K >= (len(t) - 1) // 2:
    print(sum(t))
else:
    result = sum(t[:2 * K + 1])
    j = result
    i = 2
    while i + 2 * K < len(t):
        j += t[i + 2 * K - 1] + t[i + 2 * K] - (t[i - 2] + t[i - 1])
        result = max(result, j)
        i += 2
    print(result)