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 = list(input())

if len(S) == 1:
    print(1)
elif len(S) == 2:
    print(2)
elif S[0] == '0':
    LA = [0]
    LB = [0]
    for i in range(0,N-1):
        if (S[i] != S[i+1]) & (S[i] == '0'):
            LA.append(i+1)
    for i in range(1,N-1):
        if (S[i] != S[i+1]) & (S[i] == '1'):
            LB.append(i)
    LB.append(N-1)
    ANS = 0
    if K >= len(LB)-1:
        print(N)
    else:
        for i in range(len(LB)-K):
            J = LB[i+K]-LA[i]+1
            if J > ANS:
                ANS = J
        print(ANS)
else:
    LA = [0]
    LB = []
    for i in range(0,N-1):
        if (S[i] != S[i+1]) & (S[i] == '0'):
            LA.append(i+1)
        elif (S[i] != S[i+1]) & (S[i] == '1'):
            LB.append(i)
    LB.append(N-1)
    ANS = 0
    if K >= len(LB)-1:
        print(N)
    else:
        for i in range(len(LB)-K):
            J = LB[i+K]-LA[i]+1
            if J > ANS:
                ANS = J
        print(ANS)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
S = input()
L = []
t = 1
for k in range(1,N):
    if S[k-1] == S[k]:
        t += 1
    else:
        L.append(t)
        t = 1
L.append(t)
l = len(L)
A = [0 for k in range(l+2)]

for k in range(l):
    A[k+1] = A[k] + L[k]
A[l+1] = A[l]
if S[0] == "0":
    ans = A[min(l,2*K)]
    if l%2 == 1:
        for k in range(l-2*K+1):
            if k%2 == 1:
                ans = max(ans,A[k+2*K+1]-A[k])
    else:
        for k in range(l-2*K):
            if k%2 == 1:
                ans = max(ans,A[k+2*K+1]-A[k])
else:
    ans = A[min(l,2*K+1)]
    if l%2 == 1:
        for k in range(l-2*K):
            if k%2 == 0:
                ans = max(ans,A[k+2*K+1]-A[k])
    else:
        for k in range(l-2*K+1):
            if k%2 == 0:
                ans = max(ans,A[k+2*K+1]-A[k])

print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
N, K = (int(x) for x in input().split())
string = input()
ls = list(map(int, string))

if string == "1" or string == "0":
    print(1)
    sys.exit()


def cal_list(pb):
    comp = []
    k = 0
    m = 0
    if pb[1][0] == "0":
        pb[0].insert(0, 0)
        pb[1].insert(0, "1")
    if pb[1][len(pb[1][:])-1] == "0":
        pb[0].append(0)
        pb[1].append("1")
    comp.append(pb[0][0])
    for i in range(1, len(pb[0][:])):
        comp.append(comp[i-1]+pb[0][i])
    ans = 0
    j = 0
    for h in list(reversed(range(K+1))):
        while 2*h+1+2*j <= len(comp):
            if j == 0:
                ans = comp[2*h]
            else:
                ans = max(ans, comp[2*h+2*j]-comp[j*2-1])
            j += 1
    print(ans)


def split_01(lis):
    pb = [[] for i in range(2)]
    i = 0
    while i < len(lis):
        count_0, count_1 = 0, 0
        if lis[i] == 0:
            while lis[i] == 0:
                count_0 += 1
                i += 1
                if i >= len(lis):
                    break
            pb[0].append(count_0)
            pb[1].append("0")
        if i >= len(lis):
            break
        if lis[i] == 1:
            while lis[i] == 1:
                count_1 += 1
                i += 1
                if i >= len(lis):
                    break
            pb[0].append(count_1)
            pb[1].append("1")
        if i >= len(lis):
            break
    return pb


pr = split_01(copy.copy(ls))
cal_list(copy.copy(pr))

Submission status: Accepted

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

    # 2K+1 ... 0
    # 2K ... 1
    results = [0]
    prev = 1
    for i in range(N):
        s = int(S[i])
        if prev == s:
            results[-1] += 1
        else:
            results.append(1)
        prev = s
    if prev == 0: # last is zero
        results.append(0)
    if K >= (len(results) // 2):
        return len(S)

    lh = 0
    ans = results[0]
    maximum = -1
    for rh in range(2, len(results), 2):
        diff = results[rh] + results[rh-1]
        if (rh - lh) > 2*K:
            lh += 2
            diff -= (results[lh-1] + results[lh-2])
        ans = ans + diff
        maximum = max(maximum, ans)
    return maximum

print(m())

Submission status: Accepted

Solution code:
import re


n, k = map(int, input().split())
s = input()
s_re = re.split(r'(0+)', s)
srl = len(s_re)
m = [0] * srl
if srl // 2 <= k:
    ans = n
else:
    for i, w in enumerate(s_re):
        m[i] = len(w)
    tmp = sum(m[:k * 2 + 1])
    ans = tmp
    for i in range(0, srl, 2):
        ie = i + k * 2 + 1
        if ie < srl:
            tmp = tmp - m[i] - m[i+1] + m[ie] + m[ie+1]
            ans = max(ans, tmp)
        else:
            break
print(ans)

Submission status: Accepted

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

ll=len(l)
p=2*K+1
if ll<p:
    print(N)
else:
    print(max(l[p+i]-l[i] for i in range(0,ll-p+1,2)))

Submission status: Accepted

Solution code:
'''input
5 1
00010
'''


N, K=map(int,input().split())
Sstr=input()
# print(Sstr)
S=[]

for i in range(N):
	S.append(int(Sstr[i]))

# print(S)
# flip=0
# for i in range(N-1):
# 	flip+=abs(S[i+1]-S[i])
# print(flip)


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
ans=0

left=0
right=0
tmp=0

for i in range(0, len(Nums), 2):
	# tmp=0
	Nextleft=i
	Nextright=min(i+Add, len(Nums))
	# for j in range(left, right):
	# 	tmp+=Nums[j]
	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:
import sys

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

nowOn = S[0]
count = 0
serialList = []

for i in S:

    if(nowOn == i):
        count += 1

    else:
        serialList.append(count)
        count = 1
        nowOn = i

serialList.append(count)

T = 2 * K + 1
A = 0

#serialList -> ["1", "0", "1", "0", ...]
if S[0] == "0":
    serialList.insert(0, 0)
    
#exception
if int(len(serialList) / 2) < K:
    print(len(S))
    sys.exit()

maxA = 0
for i in range(T):
    A += serialList[i]
    maxA = A
    
for i in range(T, len(serialList), 2):
    A -= serialList[i - T]
    A -= serialList[i - T + 1]
    A += serialList[i]

    if(i+1 < len(serialList)):
        A += serialList[i + 1]

    if maxA < A:
        maxA = A
        
print(maxA)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Handstand
https://atcoder.jp/contests/abc124/tasks/abc124_d
WA
"""
import sys


from itertools import groupby
from collections import deque

def solve(N, K, S):
    seq = [[k, len(list(g))]  for k, g in groupby(S)]
    if len(seq) <= 2*K:
        return len(S)
    if seq[0][0] == '0':
        seq = [['1', 0]] + seq
    if len(seq) % 2 == 0:
        seq.append(['1', 0])

    seq = deque(seq)
    rem = deque()
    ans = 0
    for i in range(2*K+1):
        _, v = seq.popleft()
        ans += v
        rem.append(v)

    max_ans = ans
    while seq:
        _, v = seq.popleft()
        ans += v
        rem.append(v)
        ans -= rem.popleft()
        _, v = seq.popleft()
        ans += v
        rem.append(v)
        ans -= rem.popleft()
        max_ans = max(max_ans, ans)
    return max_ans


def main(args):
    N, K = map(int, input().split())
    S = input()
    ans = solve(N, K, S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
l = [0,0] if (s[0] == '0') else [0]
l += [i for i in range(1,n) if s[i-1] != s[i]]
l += [n] if (s[-1] == '1') else [n,n]

ll = len(l)
pl = 2 * k + 1
if (ll < pl):
    print(n)
else:
   print(max(l[pl+i]-l[i] for i in range(0, ll-pl+1, 2)))

Submission status: Accepted

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

Submission status: Accepted

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

c = 1
l = []
l += [0,0] if (s[0] == '0') else [0]

for i in range(1, n):
    if s[i-1] != s[i]:
        l += [c+l[-1]]; c = 1;
    else:
        c +=1

l += [c+l[-1]]
if s[-1] == '0':
   l += [l[-1]]

ll = len(l)
pl = 2 * k + 1

if ll <= pl:
    print(n)
else: 
    m = 0
    for i in range(0, ll-pl+1, 2):
        t = l[pl+i]-l[i]; m = t if (t > m) else m
    print(m)

Submission status: Accepted

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

l += [0,0] if (s[0] == '0') else [0]

for i in range(1, n):
    if s[i-1] != s[i]:
        l += [c+l[-1]]
        c = 1
    else: 
        c +=1
l += [c+l[-1]]

if s[-1] == '0':
    l += [l[-1]]

ll = len(l)
pl = 2 * k + 1

if ll <= pl:
    print(n)
else:
   m = 0
   for i in range(0, ll-pl+1, 2):
       t = l[pl+i]-l[i]
       m = t if (t > m) else m
   print(m)

Submission status: Accepted

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

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

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

if s[n-1] == '0':
    l.append(0)

ll = len(l)
pl = 2 * k + 1

if ll <= pl:
    t = 0
    for i in range(ll):
        t += l[i]
    print(t)
else:
    t = 0
    for i in range(0,pl):
      t += l[i]
    m = t
    for i in range(0, ll-pl, 2):
        t += l[pl+i] + l[pl+i+1]
        t -= l[   i] + l[   i+1]
        m = t if (t > m) else m
    print(m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#しーあるさんより

n,k=map(int,input().split())
s='1'+input()
i=j=0
while j<n:
  #print(k,i,j)
  k-=  '10'==s[j:j+2]
  i+=k<0
  k+=k<0 and '01'==s[i:i+2]
  j+=1
  #print("End",k,i,j)
print(n-i)

Submission status: Accepted

Solution code:
def solve():
    N, K = [int(_) for _ in raw_input().split()]
    S = raw_input()
    elms = [S[0]]
    cnts = []
    cnt = 1
    for i in range(1,N):
        if S[i] == elms[-1]:
            cnt += 1
        else:
            cnts.append(cnt)
            elms.append(S[i])
            cnt = 1
    cnts.append(cnt)
    num_elm = len(elms)
    max_cont1 = 0
    tmp = 0
    for i in range(num_elm):
        if i == 0:
            if elms[i] == '0':
                tmp = sum(cnts[i:(i+2*K)])
                max_cont1 = max(max_cont1, tmp)
            if elms[i] == '1':
                tmp = sum(cnts[i:(i+2*K+1)])
                max_cont1 = max(max_cont1, tmp)
        elif i == 1:
            if elms[i] == '1':
                tmp -= cnts[i-1]
                if i + 2*K - 1 < num_elm:
                    tmp += cnts[i + 2*K - 1]
                if i + 2*K < num_elm:
                    tmp += cnts[i + 2*K]
                max_cont1 = max(max_cont1, tmp)
        else:
            if elms[i] == '1':
                tmp -= cnts[i - 2]
                tmp -= cnts[i - 1]
                if i + 2*K - 1 < num_elm:
                    tmp += cnts[i + 2*K - 1]
                if i + 2*K < num_elm:
                    tmp += cnts[i + 2*K]
                max_cont1 = max(max_cont1, tmp)
    print str(max_cont1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,K = list(map(int,input().split()))
S = input().replace("10","1 0").replace("01","0 1").split()
#はじめと終わりの値を記録
S0 = int(S[0][0])
Send = int(S[-1][-1])

S = list(map(len,S))
if S0 == 0:
    S.insert(0,0)
if Send == 0:
    S.append(0)
#0010 -> S=[0,2,1,1,0],S0=0,Send=0

ret = 0

if (len(S)-1)//2<= K:
    #0の塊がK以下なら
    print(sum(S))
    import sys
    sys.exit()
else:
    window_size = 1 + K * 2
    ret = sum(S[0:window_size])
    cur_range_val = ret
    start_index = 2
    while start_index + window_size <= len(S):
        cur_range_val = cur_range_val - S[start_index-2] - S[start_index-1] + S[start_index+window_size-2] + S[start_index+window_size-1]
        start_index+=2
        if cur_range_val > ret:
            ret = cur_range_val
print(ret)

Submission status: Accepted

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

h = (0, S[0])
t = (0, S[0])
k = 1 if S[0] == '0' else 0
max_handstands = 1
current_handstands = 1
while True:
    if h[0] == N-1 and t[0] == N-1:
        break
    # kを維持したままtを進める
    elif t[0] < N-1 and not (t[1] == '1' and S[t[0]+1] == '0'):
        t = (t[0]+1, S[t[0]+1])
        current_handstands += 1
    # kを増やしてtを進める
    elif t[0] < N-1 and k < K and S[t[0]+1] != t[1]:
        k += 1
        t = (t[0]+1, S[t[0]+1])
        current_handstands += 1
    # kを維持したままhを進める
    elif not (h[1] == '0' and S[h[0]+1] == '1') and h[0] < t[0]:
        max_handstands = max(max_handstands, current_handstands)
        h = (h[0]+1, S[h[0]+1])
        current_handstands -= 1
    # kを減らしてtを進める
    elif S[h[0]+1] != h[1] and h[0] < t[0]:
        max_handstands = max(max_handstands, current_handstands)
        k -= 1
        h = (h[0]+1, S[h[0]+1])
        current_handstands -= 1
    else:
        raise

print(max_handstands)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
slist = [1 if s == "1" else -1 for s in input()]
last_ch = slist[0]

s_enc_list = []
seq = 0
for s in slist:
  if s == last_ch:
    seq += s
  else:
    s_enc_list.append(seq)
    seq = s
    last_ch = s
s_enc_list.append(seq)
if s_enc_list[0] < 0:
  s_enc_list.insert(0,0)
if s_enc_list[-1] < 0:
  s_enc_list.append(0)
  
k_seq = min(2*K+1,len(s_enc_list))
max_sum = 0
for i in range(k_seq):
  max_sum += abs(s_enc_list[i])
  
sum = max_sum
for i in range(2,len(s_enc_list)-k_seq+1,2):
  sum -= abs(s_enc_list[i-2]) + abs(s_enc_list[i-1])
  sum += abs(s_enc_list[i+k_seq-2]) + abs(s_enc_list[i+k_seq-1])
  if sum > max_sum:
    max_sum = sum
    
print(max_sum)

Submission status: Accepted

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

arr = [0]
for i in range(N):
    if i == 0:
        if S[i] == "1":
            arr[-1] += 1
        else:
            arr.append(1)
    else:
        if S[i-1] == S[i]:
            arr[-1] += 1
        else:
            arr.append(1)
    if i == N-1:
        if S[i] == "1":
            continue
        else:
            arr.append(0)
sumarr = [0]
for i in arr:
    sumarr.append(sumarr[-1] + i)
ans = 0
if 2*K + 1 >= len(arr):
    ans = sumarr[-1]
else:
    for i in range((len(arr)-(2*K+1))//2 + 1):
        left = 1 + 2*i
        right = 2*K + 1 + 2*i
        ans = max(ans, sumarr[right]-sumarr[left-1])

print(ans)

Submission status: Accepted

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

il = [0]

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

res = -1
for i in range(len(il)):
    if s[il[i]]=="0":
        ri = i+2*k
    else:
        ri = i+2*k+1

    if ri>=len(il):
        r = n
    else:
        r = il[ri]
    res = max(res, r-il[i])

print(res)

Submission status: Accepted

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

def check(l,r,k,s,acc):
    cnt = acc[r] - acc[l]
    if l>0 and s[l]=="0":
        cnt += 1
    return cnt<=k

def f(n,k,s):
    acc = [0]*(n+1)
    for i in range(n):
        if i==0:
            if s[i]=="0":
                acc[i+1] = 1
        else:
            if s[i]=="0" and s[i-1]=="1":
                acc[i+1] = acc[i]+1
            else:
                acc[i+1] = acc[i]

    left = 0
    right = 0
    res = -1
    while left<n:
        while right<n and check(left,right+1,k,s,acc):
            right += 1

        res = max(res, right-left)

        if left==right:
            right += 1

        left += 1

    return res

if __name__ == '__main__':
    n,k = map(int, input().split())
    s = input()
    print(f(n,k,s))

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,K = na()
S = ns()
Add = 2*K+1
Nums = []
cnt=0
now=1
for i in range(N):
    if(S[i]==str(now)):
        cnt+=1
    else:
        Nums.append(cnt)
        now = 1-now
        cnt = 1
if(cnt):
    Nums.append(cnt)
if(len(Nums)%2==0):
    Nums.append(0)
#累積和
Sums = [0]*(len(Nums)+1)
for i in range(len(Nums)):
    #print(Nums[i])
    Sums[i+1] = Sums[i] + Nums[i]
#print(Sums)
#print(Nums)
ans = 0
for i in range(0,len(Nums),2):
    left = i
    right = min(i+Add, len(Nums))
    #print(i)
    #print(Sums[i+Add])
    tmp = Sums[right] - Sums[left]
    ans  = max(ans,tmp)
print(ans)

Submission status: Accepted

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

li = []

v = 1
c = 0
for it in S:
  if (v != it ):
    li.append(c)
    c=1
  else:
    c+=1
  v = it
li.append(c)
s = 0
lis = [0]*(len(li)+1)
for i in range(len(li)):
  lis[i+1]=lis[i]+li[i]
s = 0
for i in range(N):
  if (i*2>=N):
    continue
  a = min(i*2,len(li))
  b = min(i*2+2*K+1,len(li))

  ds2 = lis[b]-lis[a]
  s = max(s,ds2)
print (s)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
A = []
if S[0] == '0': A.append(0)
left = 0
while left < N:
  right = left
  while right < N and S[left] == S[right]:
    right += 1
  A.append(right - left)
  left = right
ans = 0
tot = 0
right = 0
for left in range(len(A)):
  while right < len(A) and right - left < 2 * K + 1:
    tot += A[right]
    right += 1
  if left % 2 == 0:
    ans = max(ans, tot)
  if left == right:
    right += 1
  else:
    tot -= A[left]
print(ans)

Submission status: Accepted

Solution code:
def possible(m):
    l = 0
    r = 1
    zeroes = int(s[0] == '0')
    ans = N
    while r != N + 1:
        if r - l > m:
            l += 1
            if s[l] != s[l - 1] and s[l] == '1':
                zeroes -= 1
        if r - l == m:
            ans = min(ans, zeroes)
        if r == N:
            break
        if s[r] != s[r - 1] and s[r] == '0':
            zeroes += 1
        r += 1
    return min(zeroes, ans) <= K
            
N, K = map(int, input().split())
s = input()
l = 1
r = N + 1
while r - l > 1:
    m = (l + r) // 2
    if possible(m):
        l = m
    else:
        r = m
print(l)

Submission status: Accepted

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

nums=[]
now=1
seq_count=0
for char in S:
        if char == str(now):
            seq_count+=1
        else:
            now=1-now
            nums.append(seq_count)
            seq_count=1
nums.append(seq_count)
if len(nums)%2==0:
    nums.append(0)
sums=[0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1]=sums[i]+nums[i]

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

Submission status: Accepted

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

nums=[]
now=1
seq_count=0
for char in S:
    if char in S:
        if char == str(now):
            seq_count+=1
        else:
            now=1-now
            nums.append(seq_count)
            seq_count=1
nums.append(seq_count)
if len(nums)%2==0:
    nums.append(0)
sums=[0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1]=sums[i]+nums[i]

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
 
l = [0]
curr = '1'
 
#0と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)
 
#初期値として左端から1の塊を算出
for i in range(k):
    sum_ += l[2 * i] + l[2 * i + 1]
sum_ += l[2 * k]
max_ = sum_
 
#左端から0の塊を１つずつ取り替えて、最大値を算出
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:

# coding: utf-8

# In[5]:

import sys
#input = sys.stdin.readline
N, K = map(int, input().split())
S = input()


# In[6]:

#print(N, K)
#print(len(S), S)


# In[21]:

tmp = S[0]
sums = [0]*(N+2)
counter = 1
gc = N
nb = 0
for i in range(1, N):
    if S[i] != tmp:
        sums[nb+1] = i
        nb += 1
        counter = 0
        tmp = S[i]
    else:
        gc -= 1
    counter += 1
    if i == N-1:
        sums[nb+1] = i+1

#print(N, gc)
sums = sums[:gc+2]
#print(S)
#print(sums)
#print(gc)
#print(gc-K*2)
pl = [0]*(gc+2)
if gc < K*2:
    print(N)
else:
    if S[0] == "0":
        if S[-1] == "0":
            for i in range(-1, gc-K*2+1, 2):
                #print(i, i+1+K*2, gc)
                j = 0 if i < 0 else i
                l = gc if i+1+K*2>gc else i+1+K*2
                #print(j, l)
                pl[i] = sums[l]-sums[j]
        else:
            for i in range(-1, gc-K*2, 2):
                j = 0 if i < 0 else i
                pl[i] = sums[i+1+K*2]-sums[j]
    else:
        if S[-1] == "0":
            for i in range(0, gc-K*2+1, 2):
                #print(i, i+1+K*2, gc)
                j=i
                l = gc if i+1+K*2>gc else i+1+K*2
                #print(j, l)
                pl[i] = sums[l]-sums[j]
        else:
            for i in range(0, gc-K*2, 2):
                j = i
                pl[i] = sums[i+1+K*2]-sums[j]
    #print(pl)
    print(max(pl))


# In[ ]:

Submission status: Accepted

Solution code:
from collections import deque
N, K = map(int, input().split())
S = input()
que = deque()
p = 0
q = 0
num = 0
i = 0
while i < N:
    if S[i] == '0':
        tmp = 0
        while i < N and S[i] == '0':
            tmp += 1
            i += 1
        que.append(p + tmp)
        q += que[-1]
        if len(que) > K:
            q -= que.popleft()
        num = max(num, q)
    else:
        tmp = 0
        while i < N and S[i] == '1':
            tmp += 1
            i += 1
        p = tmp
        num = max(num, q + tmp)
print(num)

Submission status: Accepted

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


# first, end: '1'
def make_chain(l):
    chn = []
    prev = '1'
    chn.append(0)
    for elem in l:
        if elem != prev:
            chn.append(1)
        else:
            chn[-1] += 1
        prev = elem
    if not l[-1] == '1':
        chn.append(0)
    return chn

chn = make_chain(s)

chn_sums = []
sum_len = 2 * k + 1
chn_sum = sum(chn[:sum_len])
chn_sums.append(chn_sum)
for i in range(0, len(chn) - sum_len, 2):
    # drop prev 1st and 2nd, append next 1st ad 2nd
    chn_sum = chn_sum - chn[i] - chn[i+1] + chn[i+sum_len] + chn[i+sum_len+1]
    chn_sums.append(chn_sum)


print(max(chn_sums))

Submission status: Accepted

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

l = [0]
curr = '1'

#0と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)

#初期値として左端から1の塊を算出
for i in range(k):
    sum_ += l[2 * i] + l[2 * i + 1]
sum_ += l[2 * k]
max_ = sum_

#左端から0の塊を１つずつ取り替えて、最大値を算出
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:
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s = list(map(int, input()))

# Run Length Encoding
rle = list()
target = 1
count = 0
for i in range(n):
    if s[i] == target:
        count += 1
    else:
        target = 1 - target
        rle.append(count)
        count = 1
rle.append(count)
if target == 0:
    rle.append(0)

offset = 2 * k + 1
res = 0

# cumsum
rle_cumsum = [0]
for i in range(len(rle)):
    rle_cumsum.append(rle_cumsum[i] + rle[i])


for i in range(0, len(rle), 2):
    left = i
    right = min(i + offset, len(rle))
    cand = rle_cumsum[right] - rle_cumsum[left]

    res = max(res, cand)

print(res)

Submission status: Accepted

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

# Run Length Encoding
rle = list()
target = 1
count = 0
for i in range(n):
    if s[i] == target:
        count += 1
    else:
        target = 1 - target
        rle.append(count)
        count = 1
rle.append(count)
if target == 0:
    rle.append(0)

offset = 2 * k + 1
res = 0

# two pointers
left = 0
right = 0
cand = 0
for i in range(0, len(rle), 2):
    next_left = i
    next_right = min(i + offset, len(rle))

    while(next_left > left):
        cand -= rle[left]
        left += 1

    while(next_right > right):
        cand += rle[right]
        right += 1

    res = max(res, cand)

print(res)

Submission status: Accepted

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

# print(N, K)
S = input()
index_array = [0]
now_letter = "1"
for i, s in enumerate(S):
    if s != now_letter:
        now_letter = s
        index_array.append(i)
else:
    if now_letter == "1":
        index_array.append(N)
    else:
        index_array.append(N)
        index_array.append(N)        

# print(index_array)
ans = 0
array_len = len(index_array)
if (K + 1) * 2 > array_len:
    print(N)
    exit()
candidate = array_len // 2 - K
for i in range(candidate):
    # print(index_array[(i + K) * 2 + 1] - index_array[i * 2])
    ans = max(index_array[(i + K) * 2 + 1] - index_array[i * 2], ans)
print(int(ans))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
l1 = []
l2 = [0]
prev = "1"
for i in s:
    if i =="1":
        if prev == "0":
            l2.append(1)
        else:
            l2[-1]+=1
    else:
        if prev =="1":
            l1.append(1)
        else:
            l1[-1]+=1
    prev = i
l2.append(0)

res = sum(l2[:k+1])+sum(l1[:k])
ans = res
for i in range(1,len(l1)-k+1):
    res -= l2[i-1]+l1[i-1]
    res += l2[i+k]+l1[i+k-1]
    ans = max(ans,res)
print(ans)

Submission status: Accepted

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

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

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

span = 2*span+1

ans = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(i+span, len(nums))
    tmp = rsw[right]-rsw[left]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
from datetime import datetime

if __name__ == '__main__':
    N, K = map(lambda x:int(x), sys.stdin.readline().split())
    S = list(map(lambda x: int(x), list(sys.stdin.readline().rstrip())))
    start, end = 0, 0
    bStart, bEnd = 0, 0
    # 01010110
    #  * *
    # 広げる時:
    #   前回のz=1
    #   前回のs_end=1
    #   今回広がったもの=0
    #   今回のz=2
    # 狭める時:
    #   前回のz=1
    #   前回のs_start=1
    #   今回狭まったもの=0
    #   今回のz=1
    extend = True
    
    z = 0
    # print(S)
    while True:
        # assert start <= end
        # print(start, end, 'z:', z)
        
        # S[start:end]にある孤立した0がK個以下か
        # prev = 1
        # z = 0
        # for i in range(start, end):
        #     if prev == 1 and S[i] == 0:
        #         z += 1
        #     prev = S[i]
        if extend:
            end_back = 1 if end == 0 else S[end-1]
            if end_back == 1 and S[end] == 0:
                z += 1
        else:
            start_back = 1 if start == 0 else S[start-1]
            if start_back == 0 and S[start] == 1:
                z -= 1
        # input()
        # 全員を起立させられるので，広げる
        # print(z)
        if z <= K:
            if bEnd - bStart < end - start:
                bStart, bEnd = start, end
            end += 1
            if end == len(S):
                break
            extend = True
        # 反転しても逆立ちが残るので，狭める
        else:
            start += 1
            if start == len(S)-1:
                break
            extend = False
    bEnd += 1
    S[bStart:bEnd] = [1 for _ in range(bStart, bEnd)]
    # print(S, bStart, bEnd)

    o, maxO = 0, 0
    prev = 1
    for s in S:
        # print(prev, s)
        if prev == 1 and s == 0:
            if o > maxO:
                maxO = o
            o = 0
        elif s == 1:
            o += 1
        prev = s
    else:
        if o > maxO:
            maxO = o

    print(maxO)

Submission status: Accepted

Solution code:
N, K = input().split()
N = int(N)
K = int(K)
S = input()
A = []
for i in range(len(S)-1):
    if (S[i]=="0" and S[i+1]=="1") or (S[i]=="1" and S[i+1]=="0"):
        A.append(i+1)
A.insert(0, 0)
A.append(N)
M = []
if S == "0"*N:
    M.append(len(S))
elif S[0] == "0":
    if K > len(A)//2:
        K = len(A)//2
    M.append(A[K*2]-A[0])
    a = 1
    b = a + K*2 + 1
elif S[0] == "1":
    if K > (len(A)-1)//2:
        K = (len(A)-1)//2
    a = 0
    b = a + K*2 + 1
if S == "0"*N:
    pass
elif S[-1] == "1":
    while b <= len(A):
        M.append(A[b]-A[a])
        a += 2
        b = a + K*2 + 1
elif S[-1] == "0":
    while b <= len(A)-1:
        M.append(A[b]-A[a])
        a += 2
        b = a + K*2 + 1
    M.append(A[-1]-A[-1-K*2])
print(max(M))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
First=S[0]
Now=First
cnt=0
A=[0]
for s in S:
    if Now=='1' and s=='0':
        A+=[cnt]
        Now='0'
    elif Now=='0' and s=='1':
        A+=[cnt]
        Now='1'
    cnt+=1
A+=[N]
dp=2*K+1
ans=[]

if First=="0":
    p=1
    ans.append(A[min(dp-1,len(A)-1)])
else:
    p=0
    ans.append(A[min(dp,len(A)-1)])

while p+dp<len(A):
	ans.append(A[p+dp]-A[p])
	p+=2
ans.append(N-A[p])
#print(A)
print(max(ans))