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(map(int, input()))
T = []    
if S[0] == 1:
    T.append(1)
else:
    T.append(0)
    T.append(-1)
for i in range(1, n):
    if S[i] == S[i-1] and S[i] == 1:
        T[-1] += 1
    elif S[i] == S[i-1]:
        T[-1] -= 1
    elif S[i] == 1:
        T.append(1)
    else:
        T.append(-1)
if T[-1] < 0:
    T.append(0)
m = len(T)

ans = []
ans.append(T[0])
for i in range(0, k):
    if 2*i+2 < m:
        ans[0] = ans[0] - T[2*i+1] + T[2*i+2]
    else:
        break

i = 0
j = k+1
ma = ans[0]
while True:
    if 2*j >= m:
        break
    re = ans[-1] - T[2*i] + T[2*i+1] - T[2*j-1] + T[2*j]
    ma = max(ma, re)
    i += 1
    j += 1
    ans.append(re)
    
    
print(ma)

Submission status: Accepted

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

L = [1]

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

n = len(L)
if S[0] == "1":
	if n // 2 <= K:
		print(N)
	else:
		if S[-1] == "1":
			x = L[0]
			for i in range(K):
				x += L[2 * i + 1] + L[2 * i + 2]
			val = x
			for i in range(int(n // 2) - K):
				val += L[2 * (i + K) + 1] + L[2 * (i + K) + 2] - L[2 * i] - L[2 * i + 1]
				if val > x:
					x = val
			print(x)
		else:
			x = L[0]
			for i in range(K):
				x += L[2 * i + 1] + L[2 * i + 2]
			val = x
			for i in range(int(n // 2) - K - 1):
				val += L[2 * (i + K) + 1] + L[2 * (i + K) + 2] - L[2 * i] - L[2 * i + 1]
				if val > x:
					x = val
			val += L[-1] - L[-2 * K - 1] - L[-2 * K - 2]
			if val > x:
				x = val
			print(x)			

else:
	if (n + 1) // 2 <= K:
		print(N)
	elif (n - 1) // 2 == K and S[0] == "0" and S[-1] == "0":
		print(max(N - L[0], N - L[-1]))
	else:
		if S[-1] == "1":
			LL = [L[-1 - i] for i in range(n)]
			x = LL[0]
			for i in range(K):
				x += LL[2 * i + 1] + LL[2 * i + 2]
			val = x
			for i in range(int(n // 2) - K - 1):
				val += LL[2 * (i + K) + 1] + LL[2 * (i + K) + 2] - LL[2 * i] - LL[2 * i + 1]
				if val > x:
					x = val
			val += L[0] - LL[-2 * K + 1] - LL[-2 * K]
			if val > x:
				x = val
			print(x)
		else:
			LL = L[1:]
			x = LL[0]
			for i in range(K):
				x += LL[2 * i + 1] + LL[2 * i + 2]
			val = x
			for i in range(int((n - 1) // 2) - K - 1):
				val += LL[2 * (i + K) + 1] + LL[2 * (i + K) + 2] - LL[2 * i] - LL[2 * i + 1]
				if val > x:
					x = val
			val += L[-1] - LL[-2 * K + 1] - LL[-2 * K]
			if val > x:
				x = val

			LL = [L[-2 - i] for i in range(n - 1)]
			y = LL[0]
			for i in range(K):
				y += LL[2 * i + 1] + LL[2 * i + 2]
			val = y
			for i in range(int((n - 1) // 2) - K - 1):
				val += LL[2 * (i + K) + 1] + LL[2 * (i + K) + 2] - LL[2 * i] - LL[2 * i + 1]
				if val > y:
					y = val
			val += L[0] - LL[-2 * K + 1] - LL[-2 * K]
			if val > y:
				y = val
			print(max(x, y))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
people = list(input())
lst = []
count = 0
flag = people[0]
if flag == '1':
	lst.append(0)
for i in range(len(people)):
	if i == len(people) - 1:
		lst.append(count + 1)
	elif people[i] == flag and people[i+1] != flag:
		lst.append(count + 1)
		count = 0
		flag = people[i + 1]
	else:
		count += 1

maximum = 0
l = len(lst)
temp = sum(lst[0:2*K])
maximum = max(maximum, temp)
for i in range(2, l, 2):
	end = i+2*K
	temp = temp - lst[i-2] + sum(lst[end-2:end])
	if i != 2:
		temp -= lst[i-3]
	maximum = max(maximum, temp)

print(maximum)

Submission status: Accepted

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

a.append(cnt)
a.append(0)
a.append(0)

ans = s = sum(a[:2*K + 1])
for i in range(2*K + 2, len(a), 2):
    s += a[i] + a[i - 1] - a[i - 2*K - 1] - a[i - 2*K - 2]
    ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
n,k = [int(i) for i in input().split()]
s=input()

a = []
c = 0
now = 1
for ss in s:
    if str(now) == ss:
        c += 1
    else:
        now = 1 - now
        a.append(c)
        c=1
a.append(c)
if now == 0:
    a.append(0)

#print(s)
#print(a)

L = len(a)
ans = sum(a[0:2*k+1])
newans=ans
right = 2*k+2
while(right < L):
#    print(right,"r",ans, a[right],  a[right-1], a[right-2*k-1],  a[right-2*k-2])
    newans += a[right] + a[right-1]- a[right-2*k-1] - a[right-2*k-2]
    right += 2
#    print(newans)
    ans = max(ans,newans)
#print("ans")
print(ans)

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]]
print(max(g[i]-g[max(0,i-2*k-1)]for i in range(s[0]=='1',len(g),2)))

Submission status: Accepted

Solution code:
from sys import stdin
##  input functions for me
def ria(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

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

a = [0] * N
prev = 1
v = 0
for i in range(N):
    if S[i] != prev: v += 1
    a[i] = v
    prev = S[i]

ma = 0
l = 0
r = 0
for lv in range(a[0], a[N - 1] + 1):
    while a[l] < lv : l += 1
    rv = 0
    if S[l] == '0':
        rv = lv + 2 * K - 1
    else :
        rv = lv + 2 * K
    while r < N and a[r] <= rv: r += 1
    ma = max(ma, r - l)

print(ma)

Submission status: Accepted

Solution code:
def solve():
  N, K = map(int, input().split())
  _S = input()
  S = []
  b = _S[0]
  s = 0
  if b == '0': S.append(0)
  for _s in _S:
    if b == _s:
      s = s + 1
    else:
      b = _s
      S.append(s)
      s = 1
  S.append(s)
  if b == '0': S.append(0)

  num = min(len(S), 2 * K + 1)
  # n = sum(S[0:num if _S[0] == '1' else (num - 1)])
  n = sum(S[0:num])
  m = n
  # for i in range(0 if _S[0] == '1' else -1, len(S) - num, 2):
  for i in range(0, len(S) - num, 2):
    n = n - sum(S[i:i+2])
    n = n + sum(S[i + num:i + num + 2])
    m = max(m, n)

  return m

print(solve())

Submission status: Accepted

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

v = []
cnt = 1
for i in range(n - 1):
	if s[i] == s[i + 1]:
		cnt = cnt + 1
	else:
		v.append(cnt)
		cnt = 1
v.append(cnt)
m = len(v)

sum = [0] * (m + 1)
for i in range(1, m + 1):
	sum[i] = sum[i - 1] + v[i - 1]

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

print(ans)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
 
data = []
cnt = 0
curr = '1'
for i in range(len(s)):
    if s[i] != curr:
        data.append(cnt)
        curr = s[i]
        cnt = 1
    else:
        cnt += 1
data.append(cnt)
data.append(0)
data.append(0)
 
current_sum = sum(data[0:0 + 2*k+1])
ret = current_sum
for start in range(2, len(data)-k-2, 2):
    if start + 2*k >= len(data):
        break
    diff = -data[start-2]-data[start-1]+data[start + 2*k]+data[start + 2*k-1]
    current_sum += diff
 
#     print(start, val)
    if current_sum > ret:
        ret = current_sum
print(ret)

Submission status: Accepted

Solution code:
import numpy as np

N,K = list(map(int,input().rstrip().split()))
S = list(input())
if S[0] == '0':
    zero_start = True
else:
    zero_start = False

N_normalized = [0,0,0] if zero_start else [0,0]
tmp = '0' if zero_start else '1'
cnt = 0
for i in range(len(S)):
    if tmp == S[i]:
        cnt += 1
        if i == len(S)-1:
            N_normalized.append(cnt)
    else:
        N_normalized.append(cnt)
        cnt = 1
        tmp = S[i]
        if i == len(S)-1:
            N_normalized.append(1)
N_normalized.append(0)
N_normalized.append(0)
N_normalized.append(0)

tmp = sum(N_normalized[0:K*2+1])
ans = tmp

if len(N_normalized)>K*2+1:
    for i in range(2, len(N_normalized)-(K*2+1), 2):
        tmp = tmp-N_normalized[i-1]-N_normalized[i-2]+N_normalized[i+K*2-1]+N_normalized[i+K*2]
        if ans < tmp:
            ans = tmp
else:
    ans = sum(N_normalized)

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input()
L = 2 * K + 1
X = [0]*(2-int(s[0])) + [i+1 for i in range(N-1) if s[i]!=s[i+1]] + [N] * L
print(max([X[i+L]-X[i] for i in range(0, len(X)-L, 2)]))

Submission status: Accepted

Solution code:
import sys

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

ones_list = S.split('0')
zeros_list = S.split('1')

ones = []
if S[0] == '0':
    ones.append(0)
for k in range(len(ones_list)):
    if ones_list[k] != '':
        ones.append(len(ones_list[k]))
if S[-1] == '0':
    ones.append(0)

zeros = []
for k in range(len(zeros_list)):
    if zeros_list[k] != '':
        zeros.append(len(zeros_list[k]))

if K >= len(zeros):
    print(len(S))
    sys.exit()

result = []
maximum = 0
for k in range(K):
    maximum += ones[k]
    maximum += zeros[k]
maximum += ones[K]
result.append(maximum)


for j in range(len(ones) - K - 1):
    maximum += zeros[K+j] + ones[K+1+j] - ones[j] - zeros[j]
    result.append(maximum)
print(max(result))

Submission status: Accepted

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

handstand = [0]
stand = []
isHandstand = True
if s[0] == '0':
  stand.append(0)
  isHandstand = False

for c in s:
  if isHandstand:
    if c == '0':
      stand.append(1)
      isHandstand = False
    else:
      handstand[-1] += 1
  else:
    if c == '0':
      stand[-1] += 1
    else:
      handstand.append(1)
      isHandstand = True

if not isHandstand:
  handstand.append(0)

answer = N

if K < len(stand):
  answer = sum(handstand[:K+1]) + sum(stand[:K])
  prev = answer
  for start in range(1, len(stand) - K + 1):
    prev = prev - handstand[start - 1] - stand[start - 1] + handstand[start + K] + stand[start + K - 1]
    answer = max(answer, prev)    

print(answer)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
s = input()
ha = []
owa = []
ju = 0
for i in range(len(s)) :
    if s[i] == "1" :
        if ju == 0 :
            ha.append(i)
            ju = 1
    else :
        if ju == 1 :
            owa.append(i - 1)
            ju = 0
if not ha :
    print(len(s))
else :
    if ha[0] != 0 :
        ha.insert(0,0)
        owa.insert(0,0)
    owa.append(len(s)-1)
    if len(ha) != len(owa) :
        ha.append(len(s) - 1)
    #print(ha,owa)
    dai = 0
    for i in range(len(owa) - k) :
        dai = max(dai,owa[i+k] - ha[i] + 1)
    if len(ha) > k :
        print(dai)
    else :
        print(len(s))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
X = []
ch = S[0]
cnt = 1
for i in range(1, len(S)):
    if S[i] != ch:
        X.append([ch, cnt])
        cnt = 1
        ch = S[i]
    elif S[i] == ch:
        cnt += 1
X.append([ch, cnt])

st = None
if X[0][0] == '0':
    st = 0
else:
    st = 1
en = st +  2 * (K - 1)
re = K
for v in X:
    if v[0] == '0':
        re -= 1
        
if '0' not in S:
    print(N)
elif re > 0:
    print(N)
else:
    max_1 = 0
    for i in range(st, en + 1):
        max_1 += X[i][1]
    if st - 1 >= 0:
        max_1 += X[st - 1][1]
    if en + 1 < len(X):
        max_1 += X[en + 1][1]
    tmp = max_1
    while True:
        if en + 2 >= len(X):
            break
        if st == 0:
            tmp -= X[0][1]
        else:
            tmp -= X[st][1] + X[st - 1][1]
        if en + 2 == len(X) - 1:
            tmp += X[en + 2][1]
        else:
            tmp += X[en + 3][1] + X[en + 2][1]
        st = st + 2
        en = en + 2
        if tmp > max_1:
            max_1 = tmp
    print(max_1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

n_zeros = len(zeros)

k = min(k, n_zeros)

cum_ones = []
for i, num in enumerate(ones):
    if i == 0:
        cum_ones.append(num)
        continue
    cum_ones.append(num + cum_ones[-1])
cum_zeros = []
for i, num in enumerate(zeros):
    if i == 0:
        cum_zeros.append(num)
        continue
    cum_zeros.append(num + cum_zeros[-1])

max_score = 0
for i in range(n_zeros - k + 1):
    score = 0
    score += (cum_ones[i+k] - cum_ones[i-1]) if i > 0 else cum_ones[i+k]
    if k > 0:
        score += (cum_zeros[i+k-1] - cum_zeros[i-1]) if i > 0 else cum_zeros[i+k-1]
    if max_score < score:
        max_score = score

print(max_score)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
ans=[]
index=[]#0start, 0end
if S[0]=='0':
    index.append(0)

for i in range(1,len(S)):
    if S[i-1]!=S[i] and S[i]=='1':
        index.append(i-1)
    elif S[i-1]!=S[i] and S[i]=='0':
        index.append(i)

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

if K<len(index)//2:
    for i in range(len(index)//2-K+1):
        if i == 0:
            start=0
        else:
            start=index[2*i-1]+1
        if i==len(index)//2-K:
            end=len(S)-1
        else:
            end=index[2*(i+K)]-1
        ans.append(end-start+1)

if K>=len(index)//2:
    print(len(S))
else:
    print(max(ans))

Submission status: Accepted

Solution code:
import sys

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


tmp1 = s[0]
count = 1
data = []
zeros = 0

for i in range(1,len(s)):
    tmp2 = s[i]
    if tmp1 != tmp2:
        data.append((tmp1, count))
        if tmp1 == '0':
            zeros += 1
        tmp1 = tmp2
        count = 1
    else:
        count += 1

data.append((tmp1,count))
if tmp1 == '0':
    zeros += 1

ans = 0

if k >= zeros:
    print(len(s))
    sys.exit()    

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

if data[-1][0] == '0':
    data.append((1,0))

anstmp = 0
for i in range(2*k + 1):
    anstmp += data[i][1]

ans = max(ans, anstmp)

for i in range(zeros - k):
    anstmp -= data[2*i][1]
    anstmp -= data[2*i + 1][1]
    anstmp += data[2*k + 2*i + 1][1]
    anstmp += data[2*k + 2*i + 2][1]

    ans = max(ans, anstmp)


print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
n,k = na()
s = ns()
ones = []
a = 0
now = '0'
 
for i in s:
    if i == now:
        a += 1
    else:
        ones.append(a)
        a = 1
        now = i
 
ones.append(a)

if (len(ones)+1)//2 <= k:
    print(sum(ones))
    exit()

ssu = 0
d = []
for u in ones:
    ssu += u
    d.append(ssu)
d.append(d[-1])
ans = 0
for j in range((len(ones)+1)//2+1-k):
    q = max(0,j*2-1)
    w = 0 if q == 0 else d[q-1]
    ans = max(ans, d[(j+k)*2-1]-w)
 
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

arr0 = np.array(list(map(len, s.split('1'))))
arr0 = arr0[arr0!=0]

arr1 = np.array(list(map(len, s.split('0'))))
arr1 = arr1[arr1!=0]


ans = 0

if s[0] == '0':
    for i in range(len(arr0)):
        
        if i == 0:
            length = arr0[i:i+k].sum() + arr1[i:i+k].sum()
        else:
            length = arr0[i:i+k].sum() + arr1[i-1:i+k].sum()
        ans = max(ans, length)
        
        if i+k > len(arr0):
            break
        
        
else:        
    for i in range(len(arr0)):
        
        
        length = arr0[i:i+k].sum() + arr1[i:i+k+1].sum()
        ans = max(ans, length)
        
        if i+k > len(arr0):
            break
        
        

if len(s) == s.count('1'):
    print(len(s))
else:
    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s='01'+s+'10'
S=[]
E=[]
ans=[]
for i in range(n+3):
  if s[i:i+2]=='01':
    S.append(i+1)
  if s[i:i+2]=='10':
    E.append(i)
if S==[] and E==[]:
  print(n)
else:
  for j in range(len(E)-k):
    ans.append(abs(S[j]-E[j+k]))
  if ans!=[]:
    ans[0]-=1
    ans[len(ans)-1]-=1
    print(max(ans)+1)
  else:
    print(n)

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:
from itertools import accumulate
n, k = map(int,input().split())
s = input()
a = []
i = 0
cnt = 0
now = s[0]
while i < n:
    if s[i] == now:
        cnt += 1
    else:
        a.append(cnt)
        now = s[i]
        cnt = 1
    if i == n-1:
        a.append(cnt)
    i += 1

if len(a) == 1 and s[0] == '1':
    print(n)
    exit()

if s[0] == '0':
    a = [0] + a
if s[-1] == '0':
    a.append(0)
    
r = list(accumulate(a))
lr = len(r)
ans = -float('inf')
kk = 2*k+1
for i in range(k*2, lr+1 , 2):
    if i == k*2:
        ans = max(ans, r[i])
    else:
        ans = max(ans, r[i] - r[i-kk])
        
if ans == -float('inf'):
    print(n)
    exit()
print(ans)

Submission status: Accepted

Solution code:
# D
n, k = map(int, input().split())
s = str(input())
r = 0
l = 0
max_len = 0
count = k
ans = 0
if all([int(i) == 1 for i in list(s)]):
    ans = len(s)
else:
    while r < n:
        if r == n-1:
            break
        while count > 0:
            if r == n-1:
                break
            if int(s[r]) == 1:
                r += 1
                continue
            else:
                count -= 1
                while int(s[r]) == 0:
                    if r == n-1:
                        break
                    r += 1
                while int(s[r]) == 1:
                    if r == n-1:
                        break
                    if r == n-2 and int(s[n-1]) == 0:
                        break
                    if int(s[r+1]) == 0:
                        break
                    r += 1
                continue
        ans = max(ans, r - l + 1)
        while int(s[l]) == 1:
            if l == n-1:
                break
            l += 1
        while int(s[l]) == 0:
            if l == n-1:
                break
            l += 1
        count += 1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input().strip()
sb, eb = False, False
if s[0] == '0':
    s = '1'+s
    sb = True
if s[-1] == '0':
    s = s+'1'
    eb = True
i = 0
dp = []
while i < len(s):
    l = i
    while i < len(s) and s[i] == '1':
        i += 1
    if l < i:
        dp.append([l, i-1])
    while i < len(s) and s[i] == '0':
        i += 1


if len(dp) <= K:
    print(N)
else:
    ans = 0
    for i in range(0, len(dp)-K):
        t = dp[i+K][1]-dp[i][0]+1
        if t > ans:
            ans = t
            if (sb and i == 0) or (eb and i == (len(dp)-K-1)):
                ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
import itertools
 
_, k = map(int, input().split())
S = input()
blocks = [(key, len(list(v))) for key, v in itertools.groupby(S)]
res = 0
i = 0
if blocks[i][0] == '0':
  res = max(res, sum([b[1] for b in blocks[i:i+2*k]]))
  i += 1

crr = sum([b[1] for b in blocks[i:i+2*k+1]])
res = max(res, crr)
while i+2*k + 2 < len(blocks):
  i += 2
  crr = crr + blocks[i+2*k-1][1] + blocks[i+2*k][1]
  crr = crr - blocks[i-1][1] - blocks[i-2][1]
  res = max(res, crr)

crr = sum([b[1] for b in blocks[-2*k:]])
res = max(res, crr)
print(res)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
a = 0
ta = 0
c = 1  # formernumber
if S[0] == '0':
    f = '0'
    F = 0
else:
    f = '1'
    F = 1
L = []
for i in range(1, N):
    if S[i] == f:
        c += 1
    else:
        L.append(c)
        f = S[i]
        c = 1
L.append(c)

if F == 0:
    L.insert(0, 0)
lenL = len(L)
if lenL % 2 == 0:
    L.append(0)
    lenL += 1
#print(L,lenL)
if lenL <= 2 * K + 1:
    print(N)
    exit()
ta = 0
for i in range(2 * K + 1):
    ta += L[i]
    a = ta
for i in range(0, lenL - 2 * K-1, 2):
    ta += -L[i] - L[i + 1] + L[i + 2 * K + 1] + L[i + 2 * K + 2]
    a = max(a, ta)
print(a)
# if F == 0 and len(L) <= 2 * K or F == 1 and len(L) <= 2 * K + 1:
#     print(N)
# elif F == 0:
#     if len(L) % 2 == 1:
#         L.append(0)
#     for i in range(2 * K):
#         a += L[i]
#     ta = a
#     for i in range(len(L)-2*K):
#         a += -L[i]-L[i+1]+L[i+2*K]+L[i+2*K+1]
#         ta = max(a,ta)
# L=[5,6,7,4,24,32]

Submission status: Accepted

Solution code:
#124-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,k=IL()
S=S()
Sn=[]
cs=S[0]
cn=1
for i in range(1,n):
    if S[i]==cs:
        cn+=1
    else:
        Sn.append(cn)
        cs=S[i]
        cn=1
Sn.append(cn)

if S[0]=='0':
    Sn=[0]+Sn
if S[-1]=='0':
    Sn=Sn+[0]
for i in range(1,len(Sn)):
    Sn[i]+=Sn[i-1]

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
if S == "0":
    print(1)
    exit()
if S.count("0") == N:
    print(N)
    exit()
L = [0]
prev = S[0]
num = 1
for s in S[1:]:
    if s == prev:
        num += 1
    else:
        L.append(num)
        num = 1
        prev = s
L.append(num)
# print(L)
for i in range(1, len(L)):
    L[i] += L[i - 1]
# print(L)
left = 0
if S[0] == "1":
    right = min(2 * K + 1, len(L) - 1)
else:
    right = min(2 * K, len(L) - 1)
num = 0
while right < len(L):
    # print("L[" + str(right) + "] - L[" + str(left) + "] = " + str(L[right] - L[left]))
    num = max(num, L[right] - L[left])
    if left == 0 and S[0] == "0":
        left += 1
    else:
        left += 2
    right += 2
if S[-1] == "0":
    right -= 1
    # print("L[" + str(right) + "] - L[" + str(left) + "] = " + str(L[right] - L[left]))
    num = max(num, L[right] - L[left])
print(num)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
ans=[]
index=[]#0start, 0end
if S[0]=='0':
    index.append(0)

for i in range(1,len(S)):
    if S[i-1]!=S[i] and S[i]=='1':
        index.append(i-1)
    elif S[i-1]!=S[i] and S[i]=='0':
        index.append(i)

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

if K<len(index) and S[0]=='1':
    for i in range(len(index)//2-K+1):
        if i == 0:
            start=0
        else:
            start=index[2*i-1]+1
        if i==len(index)//2-K:
            end=len(S)-1
        else:
            end=index[2*(i+K)]-1
        ans.append(end-start+1)

elif K<len(index) and S[0]=='0':
    for i in range(len(index)//2-K+1):
        if i==0:
            start=0
        else:
            start=index[2*i-1]+1
        if i==len(index)//2-K:
            end=len(S)-1
        else:
            end=index[2*(i+K)]-1
        ans.append(end-start+1)


if K>=len(index)//2:
    print(len(S))
else:
    print(max(ans))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
st=[]
en=[]
if s[0]=="1":
    st.append(0)
for i in range(1,n):
    if s[i-1]=="0" and s[i]=="1":
        st.append(i)
    if s[i-1]=="1" and s[i]=="0":
        en.append(i)
if s[n-1]=="1":
    en.append(n)
ans=0
if len(en)+1<=k:
    print(n)
    exit()
if len(en)<=k and s[0]=="1":
    print(n)
    exit()
if len(en)<=k and s[n-1]=="1":
    print(n)
    exit()
if len(en)-1<=k and s[n-1]=="1" and s[0]=="1":
    print(n)
    exit()
    
if len(en)<=k:
    k=len(en)
for i in range(len(en)-k):
    ans=max(ans,en[i+k]-st[i])
if s[0]=="0":
    ans=max(ans,en[k-1])
if s[n-1]=="0":
    ans=max(ans,n-st[len(st)-k])
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
n=N
S=input()
if S[-1]=="0":
    S+="1"
else:
    S+="0"
List=[]
ini=S[0]
now=0
zeronum=0
for i in range(N+1):
    if S[i]==ini:
        now+=1
        continue
    else:
        if ini=="1":
            List.append(now)
        else:
            List.append(now*(-1))
            zeronum+=1
        ini=S[i]
        now=1
if List[0]<0:
    List.insert(0,0)

sum=0
SUM=0

if zeronum<=K:
    print(n)
    quit()
N=len(List)
for i in range(2*K+1):
    if i%2==1:
        sum+=List[i]*(-1)
    else:
        sum+=List[i]
SUM=max(sum,SUM)

for i in range(6):
    List.append(0)
ind=0
for i in range(K+1,N//2+3):

    sum+=-List[ind]+List[ind+1]-List[2*i-1]+List[2*i]
    ind+=2
    SUM=max(sum,SUM)
print(SUM)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if a < b:
        a, b = b, a
    ans = a
    a -= 1
    ans += max(a, b)
    print(ans)
    return

#B
def B():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    ans = 0
    for i in range(n):
        dp[i] = max(dp[i - 1], h[i])
        if dp[i - 1] <= h[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    s = S()
    ans = 0
    for num, i in enumerate(s):
        if num % 2:
            if i == "0":
                ans += 1
        else:
            if i == "1":
                ans += 1
    ansb = 0
    for num, i in enumerate(s):
        if not num % 2:
            if i == "0":
                ansb += 1
        else:
            if i == "1":
                ansb += 1
    print(min(ans, ansb))
    return

#D
def D():
    n, K = LI()
    s = S()
    ans = []
    i = 0
    while i < n:
        l = 1
        for x in range(i+1, n):
            if s[x] == s[i]:
                l = x + 1 - i
                continue
            l = x - i
            break
        ans.append(l)
        i += l
    f = 0
    if s[-1] == "0":
        ans.append(0)
        f = 1
    
    dp = [0 for i in range(len(ans))]
    #print(ans)    
    if s[0] == "0":
        i = 2*K
        dp[0] = sum(ans[:i])
        a = 1
    if s[0] == "1":
        i = 2*K+1
        dp[0] = sum(ans[:i])
        a = 0
    x = 1
    while x + 2 * K < len(ans):
        if not a:
            dp[x] = dp[x - 1] - ans[x-1]
        else:
            dp[x] = dp[x - 1] + ans[x + 2 * K] + ans[x+2*K-1] - ans[x-1]
        x += 1
        a = (a + 1) % 2
        
    print(max(dp))
        

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
import bisect

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

    TYOKU = '0'
    SAKA = '1'

    if S.count(TYOKU) <= K:
        print(N)
        exit()

    asyu = []
    prev = S[0]
    prev_c = 0
    for s in S:
        if prev == s:
            prev_c += 1
        else:
            asyu.append((prev, prev_c))
            prev = s
            prev_c = 1
    asyu.append((prev, prev_c))
    # print(asyu)

    de = []
    for i in range(len(asyu)):
        pair = asyu[i]
        if pair[0] == '0':
            if i > 0:
                prev_pair = asyu[i-1]
                de.append(pair[1] + prev_pair[1])
            else:
                de.append(pair[1])
    # print(de)

    ans = 0
    val = 0
    k = 0
    del_i = 0
    for i in range(len(asyu)):
        pair = asyu[i]
        if pair[0] == '0':
            if k < K:
                val += pair[1]
                k += 1
            else: # max
                val += pair[1]
                val -= de[del_i]
                del_i += 1
        else:
            val += pair[1]
        ans = max(ans, val)

    print(ans)


if __name__ == '__main__':
    main()