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:
#!/usr/bin/env python3
# input
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
s = input()
range_len = 2 * k + 1
ans = 0
block_len = []
block_len.append(0)
now = "1"
for i in s:
    if now == i:
        block_len[-1] += 1
    else:
        block_len.append(1)
        now = i
if now == "0":
    block_len.append(0)
l_block = len(block_len)
# print(block_len)
if l_block <= range_len:
    print(n)
else:
    # 尺取
    tmp = sum(block_len[:range_len])
    ans = tmp
    for idx in range(l_block - range_len):
        tmp += block_len[idx + range_len] - block_len[idx]
        # print(tmp, idx)
        if idx % 2 == 1:
            # print(ans, tmp)
            ans = max(ans, tmp)

    print(ans)

Submission status: Accepted

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

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

ans = 0
if S[0] == '0':
    s = [0] + s
if S[-1] == '0':
    s = s + [0]

if 2*K + 1 > len(s):
    print(sum(s))
    exit()

s_cumsum = [s[0]] * len(s)
for i in range(1, len(s)):
    s_cumsum[i] = s_cumsum[i-1] + s[i]
    
for i in range(0, len(s), 2):
    if i + 2*K >= len(s):
        break
    if i < 1:
        ans = s_cumsum[i+2*K]
    ans = max(ans, s_cumsum[i+2*K]-s_cumsum[i-1])
    #ans = max(ans, sum(s[i:i+2*K+1]))

print(ans)

Submission status: Accepted

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

num = []
temp = 0
count = 0
flag = True
while temp < len(s):
    if flag == True:
        if s[temp] == "1":
            count += 1
            temp += 1
        else:
            num.append(count)
            count = 1
            temp += 1
            flag = False
    else:
        if s[temp] == "0":
            count += 1
            temp += 1
        else:
            num.append(count)
            count = 1
            temp += 1
            flag = True
num.append(count)
num2 = [sum(num[:min(2 * k + 1, len(num))])]
temp = min(2 * k + 1, len(num))
temp2 = 0
while temp < len(num):
    temp3 = num2[-1] - num[temp2] - num[temp2 + 1] + num[temp]
    if temp + 1 < len(num):
        temp3 += num[temp + 1]
    temp += 2
    temp2 += 2
    num2.append(temp3)
print(max(num2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
s = input()
count = 0
flag = 1
que = deque([0]*(2*k+1))
ans = 0
tmp = 0
for x in s:
    if x == '0':
        if flag == 1:
            que.append(count)
            tmp += count - que.popleft()
            ans = max(ans, tmp) 
            count = 0
        flag = 0
        count += 1
    else:
        if flag == 0:
            que.append(count)         
            tmp += count - que.popleft()
            count = 0
        flag = 1
        count += 1

que.append(count)
tmp += count - que.popleft()
if s[-1] == '0':
    tmp -= que.popleft()
ans = max(ans,sum(que))
print(ans)

Submission status: Accepted

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

if s[0] == "0":
    a.append(0)

zero_cnt = 0
one_cnt = 0
for i in range(n):
    if s[i] == "0":
        zero_cnt += 1
        if one_cnt > 0:
            a.append(one_cnt)
            one_cnt = 0
    else:
        one_cnt += 1
        if zero_cnt > 0:
            a.append(-1 * zero_cnt)
            zero_cnt = 0

if zero_cnt > 0:
    a.append(-1 * zero_cnt)
elif one_cnt > 0:
    a.append(one_cnt)

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

a_len = len(a)

cum = [0] * (a_len + 1)
for i in range(1, a_len + 1):
    cum[i] = cum[i - 1] + abs(a[i - 1])

ans = 0

for left in range(0, a_len + 1, 2):
    right = left + k * 2 + 1
    if right > a_len:
        right = a_len

    ans = max(ans, cum[right] - cum[left])

print(ans)

Submission status: Accepted

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

if N==1:
  print(1)
  exit()

S2=[]
signs=[]
if S[0]=='1':
  sign=1
else:
  sign=0
count = 1
for i in range(1,N):
  if S[i] != S[i-1]:
    S2.append(count)
    signs.append(sign)
    sign = 1- sign
    count = 0
  count += 1
  
S2.append(count)
signs.append(sign)
  
cumS = [0]
for i in range(len(S2)):
  cumS.append(cumS[-1]+S2[i])
  
k = K*2+1
if len(S2)>=k:
  MAX=0
  for i in range(len(S2)-k+1):
    if signs[i] == 1:
      tmp = cumS[i+k]-cumS[i]
      if tmp > MAX:
        MAX = tmp
  
  if signs[0]==0:
    MAX = max(MAX,cumS[k-1]-cumS[0])
  if signs[-1]==0:
    MAX = max(MAX,cumS[-1]-cumS[-k])
    
else:
  MAX=cumS[-1]
  
print(MAX)

Submission status: Accepted

Solution code:
from itertools import groupby
import sys

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

S = [[i, len(list(j))] for i, j in groupby(S)]

if len(S) // 2 <= K:
    if len(S) % 2 == 1 and S[-1][0] == "0":
        if len(S) == 1:
            print(sum([j for i, j in S]))
            sys.exit()
            
    else:
        print(sum([j for i, j in S]))
        sys.exit()

ans = 0
cnt = 0
lidx = -1
for i, j in S:
    lidx += 1
    if cnt == K and i == "0":
        break
    ans += j
    if i == "0":
        cnt += 1
sidx = 0
mans = ans
for i in range(lidx,len(S)):
    ans += S[i][1]
    if i == len(S)-1 or S[i][0] == "1":
        while True:
            ans -= S[sidx][1]
            sidx += 1
            if S[sidx][0] == "1":
                break
        mans = max(mans, ans)

print(mans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
dp=[]
p,q=0,0
for i in S:
  if i=='1':
    if 0<q:
      dp.append(q)
    p+=1
    q=0
  else:
    if 0<p:
      dp.append(p)
    p=0
    q+=1
if 0<p:
  dp.append(p)
else:
  dp.append(q)
if S[0]=='0':
  if len(dp)<=2*K:
    print(sum(dp))
  else:
    if S[N-1]=='0':
      dp.append(0)
    dp.insert(0,0)
    ans=sum(dp[:2*K+1])
    bns=ans
    for i in range(2*K,len(dp),2):
      if i==2*K:
        continue
      bns+=dp[i]+dp[i-1]-dp[i-2*K-1]-dp[i-2*K-2]
      ans=max(ans,bns)
    print(ans)
else:
  if len(dp)<=2*K+1:
    print(sum(dp))
  else:
    if S[N-1]=='0':
      dp.append(0)
    ans=sum(dp[:2*K+1])
    bns=ans
    for i in range(2*K,len(dp),2):
      if i==2*K:
        continue
      bns+=dp[i]+dp[i-1]-dp[i-2*K-1]-dp[i-2*K-2]
      ans=max(ans,bns)
    print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
a = []
b = []
c = 0
d = "1"
for i in s:
  if d == i:
    c += 1
  else:
    if d == "1":
      b.append(c)
      d = "0"
      c = 1
    else:
      a.append(c)
      d = "1"
      c = 1
if d == "1":
  b.append(c)
else:
  a.append(c)
  b.append(0)
if k >= len(a):
  print(n)
else:
  e = sum(a[:k])+sum(b[:k+1])
  ans = e
  for i in range(len(a)-k):
    e = e-a[i]-b[i]+a[i+k]+b[i+k+1]
    ans = max(ans,e)
  print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
ms = 0
ps = 0
temp = [0]
if s[0] == "0":
    temp.append(0)
for i in s:
    # print(i,ps,ms)
    if i == "0":
        ms += 1
        if ps:
            temp.append(ps)
            ps = 0
    else:
        ps += 1
        if ms:
            temp.append(ms)
            ms = 0
if ms:
    temp.append(ms)
else:
    temp.append(ps)
# print(temp)
temp.append(0)
for i in range(len(temp)-1):
    temp[i+1] += temp[i]
# print(temp)
ans = 0
if len(temp)-(2*k+1) <= 0:
    ans = temp[-1]
else:
    for i in range(0,len(temp)-(2*k+1),2):
        ans = max(ans,temp[i+2*k+1]-temp[i])
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=[int(i) for i in input()]
l1,l0=[],[]
b,c=1,0
for i in s:
  if b==i: c+=1
  else:
    if b: l1+=[c]
    else: l0+=[c]
    c=1
  b=i
if b:
  l1+=[c]
  l0+=[0]
else:
  l0+=[c]
S=[0]
for i,j in zip(l1,l0):
  S+=[S[-1]+i+j]
l1+=[0]
m=len(S)
if m<=k:
  print(n)
  exit()
a=0
for i in range(k,m):
  a=max(a,S[i]-S[i-k]+l1[i])
print(a)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=[int(i) for i in input()]
l1,l0=[],[]
b,c=1,0
for i in s:
  if b==i: c+=1
  else:
    if b: l1+=[c]
    else: l0+=[c]
    c=1
  b=i
if b:
  l1+=[c]
  l0+=[0]
else:
  l0+=[c]
S=[0]
for i,j in zip(l1,l0):
  S+=[S[-1]+i+j]
l1+=[0]
l0+=[0]
m=len(S)
if m<=k: print(n)
else:
  a=0
  for i in range(k,m):
    a=max(a,S[i]-S[i-k]+l1[i])
  print(a)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
L = [0]
X = ['1']
pos = 0
for i in range(N):
  if S[i] != X[pos]:
    L.append(1)
    X.append(S[i])
    pos += 1
  else:
    L[pos] += 1
while pos < 2 * K + 4:
  L.append(0)
  X.append('1')
  pos += 1
L.append(0)
X.append('1')
n = len(L)
for i in range(1, n):
  L[i] += L[i-1]
M = L[2*K]
for i in range(1, n-2*K):
  if X[i] == '1':
    M = max(L[2*K+i] - L[i-1], M)
print(M)

Submission status: Accepted

Solution code:
from itertools import groupby
from math import ceil

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

block = [sum(1 for _ in it) for k, it in groupby(s)]
if s[0] != '1':
    block.insert(0, 0)

m = len(block)
left, right = 0, 2*k
res = val = sum(block[left:right-1])
while right <= m:
    val += block[right-1] if right == m else block[right-1] + block[right]
    res = max(res, val)
    val -= block[left] + block[left+1]
    left += 2
    right += 2
print(res)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
S = list(map(int, list(input())))
# 尺取り法.
## 右側の初期化.//これを不規則に動かす.
ridx = 1
## パラメータの初期化.//これでridxを制御する.
### 最初が0だった場合、最初から反転が必要.
cnt = 0 if S[0]==1 else 1
## 答えの初期化.//この最大を探す.
ans = 0
## 左側を0からn-1まで動かしていく.
for lidx in range(n):
    # 現在地が1で一つ前が0だった場合、カウントを減らす.
    if lidx>0 and S[lidx]==1 and S[lidx-1]==0:
        cnt -= 1
    # 右端がn未満なら右に一つずつ動かしていく.
    while ridx < n:
        ## もし現在地が0で、一つ前が1なら
        if S[ridx]==0 and S[ridx-1]==1:
            ### カウントがk未満ならカウントを増やし、そうでないならループを脱する.
            if cnt < k:
                cnt += 1
            else:
                break
        ridx += 1
    ans = max(ans, ridx-lidx)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()+"2"
L = []
cnt = 0
temp = int(S[0])

for x in S:
  if temp == int(x):
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
    temp = int(x)

if S[0] == "0":
  Lcs = [0, 0]
else:
  Lcs = [0]

for x in L:
  Lcs.append(Lcs[-1] + x)
 
ans = Lcs[1]
N = len(Lcs)
i = 2

if i + 2*(K-1) > N-1:
  print(Lcs[-1])
else:
  while i + 2*(K-1) <= N-1:
    if i + 2*(K-1) == N-1:
      ans = max(ans, Lcs[i + 2*(K-1)]-Lcs[i-2])
    else:
      ans = max(ans, Lcs[i + 2*(K-1) +1]-Lcs[i-2])
    i += 2
  print(ans)

Submission status: Accepted

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

cl = 0
cr = 0
a = []
ans = 0
if s[0] == '1':
    ck = 0
    ans = 1
else:
    ck = 1
    a.append([0,0])
while True:
    while ck <= k and cr < n-1:
        cr += 1
        if s[cr-1] == '1' and s[cr] == '0':
            if ck < k:
                ck += 1
                a.append([cr, cr])
            else:
                break
        elif s[cr-1] == '0' and s[cr] == '1':
            a[-1][1] = cr
        ans = max(ans, cr - cl + 1)
    if cr < n-1:
        tl, tr = a.pop(0)
        cl = tr
        cr -= 1
        ck -= 1
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
I  = [0]
for i in range(1,n):
    if s[i-1] != s[i]:
        I.append(i)
I.append(n)
r = len(I)-1
X = []
for i in range(r):
    if s[I[i]] == "0":
        X.append(I[min(2*k+i,r)]-I[i])
    else:
        X.append(I[min(2*k+1+i,r)]-I[i])
print(max(X))

Submission status: Accepted

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

lengths = []

if S.startswith('0'):
    lengths.append(0)

cont = 0
for s0, s1 in zip(S, S[1:] + 'x'):
    cont += 1
    if s0 != s1:
        lengths.append(cont)
        cont = 0

if S.endswith('0'):
    lengths.append(0)

window = 2 * K + 1

buf = sum(lengths[0:window])
ans = buf
for i in range(window, len(lengths)):
    buf += lengths[i]
    buf -= lengths[i - window]
    if i % 2 == 0:
        ans = max(ans, buf)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc124/tasks/abc124_d

N, K = map(int, input().split())
S = input()
arr = []
prev = '1'
length = 0
for c in S:
  if prev != c:
    arr.append(length)
    length = 0
  length += 1
  prev = c
arr.append(length)
if S[-1] == '0':
  arr.append(0)

arr = [0] + arr
for i in range(len(arr) - 1):
    arr[i + 1] += arr[i]

L = K * 2 + 1
if L >= len(arr):
  print(N)
  exit()
ans = 0
for i in range(0, len(arr) - L, 2):
    t = arr[i + L] - arr[i]
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc124/tasks/abc124_d

N, K = map(int, input().split())
S = input()
arr = []
prev = '1'
length = 0
for c in S:
  if prev != c:
    arr.append(length)
    length = 0
  length += 1
  prev = c
arr.append(length)
if S[-1] == '0':
  arr.append(0)

arr = [0] + arr
for i in range(len(arr) - 1):
    arr[i + 1] += arr[i]


L = K * 2 + 1
if L >= len(arr):
  print(N)
  exit()
ans = 0
for i in range(0, len(arr) - L, 2):
  t = arr[i+L] - arr[i]
  ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc124/tasks/abc124_d

N, K = map(int, input().split())
S = input()
arr = []
prev = '1'
length = 0
for c in S:
  if prev != c:
    arr.append(length)
    length = 0
  length += 1
  prev = c
arr.append(length)
if S[-1] == '0':
  arr.append(0)

sarr = [0]
for a in arr:
  sarr.append(sarr[-1] + a)

L = K * 2 + 1
if L >= len(sarr):
  print(N)
  exit()
ans = 0
for i in range(0, len(sarr)-L, 2):
  t = sarr[i+L] - sarr[i]
  ans = ans if ans > t else t
print(ans)

Submission status: Accepted

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

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

m = len(cnt)
if( m <= 2*k+1):
    print(n)
    exit()

l = 0
r = 2*k+1
tmp = sum(cnt[:r])
ans = tmp
while(r+2 <= m):
    tmp += cnt[r] + cnt[r+1] - cnt[l] - cnt[l+1]
    ans = max(ans,tmp)
    l += 2
    r += 2
print(ans)

Submission status: Accepted

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

now = 1
cnt = 0
for ele in s:
    if int(ele) == now:
        cnt += 1
    else:
        ls.append(cnt)
        now = 1 - now #1と0の切替
        cnt = 1
ls.append(cnt)

# 1-0-1-0-1が欲しい
# 1-0-1-0の場合、1の場合を足す
if len(ls) % 2 == 0:
    ls.append(0)

Add = 2*k+1 #[left, right)
ans = 0

left = 0
right = 0
tmp = 0 # [left, right)のsum

# print(ls)
# 1-0-1-0..の１から始める
for i in range(0,len(ls),2):
    nextLeft = i
    nextRight = min(i + Add, len(ls))
    # print(" value", tmp)
    # print(" p left ", left)
    # print(" p right", right)

    while nextLeft > left:
        # print("left  point, value", left, tmp)
        tmp -= ls[left]
        left += 1
    while nextRight > right:
        # print("right point, value", right, tmp)
        tmp += ls[right]
        right += 1

    ans = max(tmp, ans)
    # print("ans",ans)
    # print("\n")

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

ans = 0
cnt = 0
right = 1
for left in range(0, n):
    if left == 0 and s[left] == '0':
        cnt += 1

    if left > 0 and s[left] == '1' and s[left-1] == '0':
        cnt -= 1

    while right <= n - 1:
        if s[right] == '0' and s[right-1] == '1':
            if cnt < k:
                cnt += 1
            else:
                break
        right += 1

    ans = max(ans, right - left)

print(ans)

Submission status: Accepted

Solution code:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
        if S[i] == '0':
            cnt += 1
    num += 1
L.append(num)
if S[-1] == '0':
    cnt += 1
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, K = map(int, input().split())
    S = input()
    A = []
    if S[0]=='1':
        nw = 1
    else:
        nw = -1
    for i in range(1,N):
        if S[i]=='1' and nw<0:
            A.append(nw)
            nw = 1
        elif S[i]=='0' and nw>0:
            A.append(nw)
            nw = -1
        else:
            nw += 2*(S[i]=='1')-1
    A.append(nw)
    if len(A)==1:
        print(N)
        exit()
    B = [0]*(len(A)+1)
    for i in range(len(A)):
        B[i+1] = B[i]+abs(A[i])
    if A[0]<0:
        fm = 0
    else:
        fm = 1
    ret = 0
    for i in range(fm, len(A), 2):
        ret = max(ret, B[min(i+2*K,len(B)-1)]-B[max(i-1,0)])
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k <= len(off)-1:
        b += off[i+k]
      b -= off[i-1]
    # print (a,b)
    s = a+b
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k-1 <= len(off)-1:
        b += off[i+k-1]
      b -= off[i-2]
    s = a+b
    # print (a,b)
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
*s, =map(int, input())
mark=[]
for i in range(n):
    if i==0 and s[i]==1:
        mark.append((i,1))
    elif i==0 and s[i]==0:
        mark.append((i,0))
    elif s[i-1]==0 and s[i]==1:
        mark.append((i,1))
    elif s[i-1]==1 and s[i]==0:
        mark.append((i,0))

X=[0]*n
for i in range(len(mark)):
    ist,jst=mark[i]
    if jst==0:
        if i+2*k<len(mark):
            igo, jgo=mark[i+2*k]
            X[ist]=igo-ist
        else:
            X[ist]=n-ist
    if jst==1:
        if i+2*k+1<len(mark):
            igo, jgo=mark[i+2*k+1]
            X[ist]=igo-ist
        else:
            X[ist]=n-ist

print(max(X))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N+1)

for l in range(N):
	if S[l] + S[l-1] == 0:
		continue
	while r < N and used[r] - used[l-1] <= K:
		r += 1
		if S[r-1] == 1 and S[r] == 0:
			used[r] = used[r-1] + 1
		else:
			used[r] = used[r-1]
	ans = max(ans, r-l)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

flg = [S[0]] #各連続部分の数字
count = []   #連続部分の個数
cnt = 1
tmp = S[0]

for x in S[1:]:
	if x == tmp:
		cnt += 1
	else:
		tmp = x
		flg.append(tmp)
		count.append(cnt)
		cnt = 1
count.append(cnt)

count += [0]*(2*K+1)
count = [0] + list(accumulate(count))

ans = 0

for i in range(len(flg)):
	if flg[i] == "1":
		ans = max(ans, count[i+2*K+1] - count[i])
	else:
		ans = max(ans, count[i+2*K] - count[i])

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N+1)

for l in range(N):
	if S[l] + S[l-1] == 0:
		continue
	while r < N and used[r] - used[l-1] <= K:
		r += 1
		if S[r-1] == 1 and S[r] == 0:
			used[r] = used[r-1] + 1
		else:
			used[r] = used[r-1]
	ans = max(ans, r-l)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
S = list(input())
nums = []
now = 1
cnt = 0
for s in S:
    if s == 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)

sums = [0] + list(np.cumsum(nums))
left = 0
right = left + K * 2
maxi = 0
if N < 3:
    maxi = N
while right < len(nums):
    if sums[right+1] - sums[left] > maxi:
        maxi = sums[right+1] - sums[left]
    right += 2
    left += 2
if maxi == 0:
    maxi = sum(nums)
print(maxi)

Submission status: Accepted

Solution code:
"""
keyword: 累積和
"""

import sys
sys.setrecursionlimit(10**6)

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

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

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1 # 0と1を切り替える
        cnt = 1 # 新しいのをカウント
if cnt != 0:
    nums.append(cnt)

# 1-0-1-0-1-0-1って感じの配列が欲しい
# 1-0-1-0みたいに0で終わっていたら、適当に1つ足す
# 補足：1-0-1-0-1というのは、1が0個、0が2個、1が1個、、、などと並んでいるという意味。このとき1つ目の0をひっくり返すと1-1-1と連続する。1-...-1と連続している数が求める値なので、左端と右端は1にしたい
if len(nums)%2 == 0:
    nums.append(0)
    
add = 2*k+1

# 累積和を作る
tot = [0]*(len(nums)+1)
for i in range(len(nums)):
    tot[i+1] = tot[i]+nums[i]

ans = 0

# 1-0-1...の、1から始まり1で終わる範囲を見るので、偶数番目だけ見る
for i in range(0, len(nums), 2):
    
    # 次のleft, rightを計算する
    left = i
    right = min(i+add, len(nums))
    tmp = tot[right] - tot[left]
    
    ans = max(tmp, ans)
    
print(ans)

Submission status: Accepted

Solution code:
#create date: 2020-07-03 22:02

import sys
stdin = sys.stdin
from itertools import groupby, accumulate

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, k = na()
    s = ns()
    a = list()
    if s[0] == "0":
        a.append(0)
    gr = groupby(s)
    for key, group in gr:
        a.append(len(list(group)))
    if s[-1] == "0":
        a.append(0)
    acum = list(accumulate(a))
    m = len(acum)
    l = 2*k + 1
    if m == 1:
        print(acum[0])
        quit()
    if l > m:
        print(acum[-1])
        quit()
    ans = acum[l-1]
    for i in range(0, m-l+1, 2):
        ans = max(ans, acum[i+l-1] - acum[i-1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

nums=[]

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

num=s[0]
numi=0
for i in range(n):
    if(s[i]==num):
        numi+=1
    else:
        nums.append(numi)
        numi=1
        num=s[i]
else:
    nums.append(numi)

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

#print(nums)

ans=0
zero_num=len(nums)//2
if(zero_num<=k):
    print(sum(nums))
else:
    l=2*k
    sumi=sum(nums[:l+1])
    ans=sumi
    i=0
    while(l+2<len(nums)):
        sumi+=(nums[l+1]+nums[l+2])
        l+=2
        sumi-=(nums[i]+nums[i+1])
        i+=2
        ans=max(ans,sumi)
#    print(nums[-2*k:])
    ans=max(ans,sum(nums[-2*k:]))
    print(ans)

Submission status: Accepted

Solution code:
"""
keyword: 尺取法
"""

import sys
sys.setrecursionlimit(10**6)

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

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

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1 # 0と1を切り替える
        cnt = 1 # 新しいのをカウント
if cnt != 0:
    nums.append(cnt)

# 1-0-1-0-1-0-1って感じの配列が欲しい
# 1-0-1-0みたいに0で終わっていたら、適当に1つ足す
# 補足：1-0-1-0-1というのは、1が0個、0が2個、1が1個、、、などと並んでいるという意味。このとき1つ目の0をひっくり返すと1-1-1と連続する。1-...-1と連続している数が求める値なので、左端と右端は1にしたい
if len(nums)%2 == 0:
    nums.append(0)
    
add = 2*k+1

ans = 0
left = 0
right = 0
tmp = 0 # [left, right)のsum

# 1-0-1...の、1から始まり1で終わる範囲を見るので、偶数番目だけ見る
for i in range(0, len(nums), 2):
    
    nextleft = i
    nextright = min(i+add, len(nums))
    
    # 左端を移動
    while (nextleft > left):
        tmp -= nums[left]
        left += 1
    # 右端を移動
    while (nextright > right):
        tmp += nums[right]
        right += 1
        
    ans = max(tmp, ans)
    
print(ans)

Submission status: Accepted

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

L = []
from itertools import groupby
for key ,value in groupby(s):
    L.append((key,len(list(value))))
#print(L)
c = []
for i in range(len(L)):
    c.append(L[i][1])
c = [0] + c

for i in range(1,len(c)):
    c[i] +=c[i-1]
#print(c)
l = 0 
r = 2*k

ans = 0
while True:
    if L[l][0] == "1":
        if l + r +1 < len(L):
            ans = max(ans,c[l+r+1] - c[l])#add 5
        else:
            ans = max(ans,c[len(L)] - c[l])
    elif L[l][0] == "0":
        if l + r < len(L):
            ans = max(ans,c[l+r] - c[l])#add 4
        else:
            ans = max(ans,c[len(L)] - c[l])
    if l == len(L)-1:
        break
    l +=1
print(ans)

Submission status: Accepted

Solution code:
import sys

def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()

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

A = []
count = 0
for i in range(N):
    if i == 0:
        count = 1
    else:
        if S[i] == S[i-1]:
            count += 1
        else:
            A.append(count)
            count = 1
A.append(count)

if len(A) <= 2*K-1:
    print(N)
    exit()

if S[0] == 1:
    A = [1] + A
if S[-1] == 1:
    A = A + [1]
# 両端は0だと考えてよい

from itertools import accumulate

M = (len(A)-1)//2
A = list(accumulate([0]+A))

ans = 0
for i in range(M-K+2):
    if i == 0:
        ans = max(ans,A[2*(K+i)]-A[2*i])
    elif i == M-K+1:
        ans = max(ans,A[2*(K+i)-1]-A[2*i-1])
    else:
        ans = max(ans,A[2*(K+i)]-A[2*i-1])

print(ans)