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:
_, K = map(int, input().split())
S = input()

offset = not (int(S[0]) ^ (K & 1))
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
answer = prev

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    if prev > answer:
        answer = prev

print(answer)

Submission status: Accepted

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

offset = not (int(S[0]) ^ (K & 1))
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
answer = prev

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    answer = max(answer, prev)

print(answer)

Submission status: Accepted

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

offset = int(S[0]) == (K & 1)
runs = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        runs.append(run)
        run = 0
    prev = c
    run += 1
runs.append(run)

L = len(runs)
candidates = []

prev = sum(runs[max(0, offset - K): min(L, offset + K + 1)])
candidates.append(prev)

for i in range(offset + 2, L, 2):
    now = prev
    old_left = i - 2 - K
    new_right = i + K
    if old_left >= 0:
        now -= runs[old_left]
    if old_left + 1 >= 0:
        now -= runs[old_left + 1]
    if new_right - 1 < L:
        now += runs[new_right - 1]
    if new_right < L:
        now += runs[new_right]
    prev = now
    candidates.append(prev)

print(max(candidates))

Submission status: Accepted

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


# しゃくとり法
ans = 0
L, R = 0, 0
s.append(-1)  # 右端の処理

# 指定区間で直立した人の連続数の数
counter = 0
    
while R < n:
    # 右端を進める場合
    if (counter < k) or (counter == k and s[R] == 1):
        if s[R] == 0 and s[R+1] == 1:
            counter += 1
        ans = max(ans, R - L + 1)
        R += 1
    # 右端をこれ以上進められない場合
    # 左端を進める場合
    elif L < R:
        if s[L] == 0 and s[L+1] == 1:
            counter -= 1
        L += 1        
    # 左端も進められない（右端に追いついてしまった）場合
    # 区間全体を右に進める
    elif L == R:  
        L += 1
        R += 1
        
print(ans)

Submission status: Accepted

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

def runLength(s):
  if len(s) == 0: return []
  if len(s) == 1: return [(s, 1)]
  res = []
  lc = 1
  for i in range(1, len(s)):
    if s[i-1] == s[i]:
      lc += 1
    else:
      res.append((s[i-1], lc))
      lc = 1
  res.append((s[i], lc))
  return res

S = runLength(input())
accsum = [0] * (1 + (S[0][0] == "0"))
for i in range(len(S)):
  accsum.append(accsum[-1] + S[i][1])
if S[-1][0] == "0":
  accsum.append(accsum[-1])
print(max([accsum[i] - accsum[i-2*K-1] for i in range(2*K+1, len(accsum), 2)]) if len(accsum) > 2*K+2 else N)

Submission status: Accepted

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

t = list(map(int, list(s)))
lt = len(t)
w = []
sumw = []
u = 0
u1 = t[0]
ans1 = []
ans = 0
for i in range(lt):
    if t[i] == u1:
        u += 1
    if t[i] != u1:
        u = u if u1 == 1 else u*-1
        w.append(u)
        ans += abs(u)
        ans1.append(ans if u > 0 else ans*-1)
        u = 1
        u1 = 1 if u1 == 0 else 0

u = u if u1 == 1 else u*-1
w.append(u)
ans += abs(u)
ans1.append(ans if u > 0 else ans*-1)

ans2 = []
for i in range(len(ans1)):
    if i == 0:
        ans2.append(ans1[i])
    elif ans1[i] > 0:
        if i - 2*k - 1 >= 0:
            ans2.append(ans1[i] + ans1[i - 2*k - 1])
        else:
            ans2.append(ans1[i])
    else:
        if i - 2*k >= 0:
            ans2.append(ans1[i]*-1 + ans1[i - 2*k])
        else:
            ans2.append(ans1[i]*-1)

print(abs(max(ans2)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import groupby
from itertools import accumulate

def solve(N: int, K: int, S: str):
    group = groupby(S)

    one = []
    zero = []
    for key,value in group:
        if key == "1":
            one.append(len(list(value)))
        else:
            zero.append(len(list(value)))
    
    if len(zero) <= K:
        print(sum(one)+sum(zero))
        return
    
    # one がzeroより一つ多くなるように
    if len(one) == len(zero):
        if S[0] == "1":
            one.append(0)
        else:
            one = [0]+one
    elif len(zero) > len(one):
        one = [0]+one+[0]
    

    accum_zero = [0] + list(accumulate(zero))
    accum_one = [0] + list(accumulate(one))

    answer = 0
    for i in range(len(zero)-K+1):
        total = (accum_one[i+K+1]-accum_one[i]) + accum_zero[i+K]-accum_zero[i]
        answer = max(total,answer)
    
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
s = input()
#尺取り法
right = -1
left = -1
now_k = 0
while right + 1 < n and s[right + 1] == '1': 
    right += 1
#初めのrightの位置を決める
while now_k < k:
    now_k += 1
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
#今の時点で、rightがいい感じの場所にいる。
ans = (right + 1)
while right + 1 < n:
    while right + 1 < n and s[right + 1] == '0':
        right += 1
    while right + 1 < n and s[right + 1] == '1':
        right += 1
    while left + 1 < n and s[left + 1] == '1':
        left += 1
    while left + 1 < n and s[left + 1] == '0':
        left += 1
    left += 1
    ans = max(ans, right - left + 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

L = deque()

l = 0 # 連続する0の塊がK個含まれるSの連続部分列の左端の位置
r = 0 # 連続する0の塊がK個含まれるSの連続部分列の右端の位置
n_zero = 0  # lとrの間に含まれる0の塊の数
ans = 0

while r < N:
    while r < N and n_zero < K:
        if S[r] == "0": n_zero += 1
        while r < N and S[r] == "0":
            r += 1
        if 0 < r < N and S[r] == "1":
            L.append(r)
        while r < N and S[r] == "1":
            r += 1
    ans = max(ans, r - l)
    if len(L) > 0:
        l = L.popleft()
        n_zero -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

L = deque()

n_zero = 0  # 通過した0の塊の数
r = 0 # 連続する0の塊がK個含まれるSの連続部分列の右端の位置
l = 0
# rの値を探す
while r < N and n_zero < K:
    if S[r] == "0": n_zero += 1
    while r < N and S[r] == "0":
        r += 1
    if 0 < r < N and S[r] == "1":
        L.append(r)
    while r < N and S[r] == "1":
        r += 1

ans = r

while len(L) > 0 and r < N:
    l = L.popleft()
    while r < N and S[r] == "0":
        r += 1
    if r < N and S[r] == "1":
        L.append(r)
    while r < N and S[r] == "1":
        r += 1
    ans = max(ans, r - l)

print(ans)

Submission status: Accepted

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

if S[0] == '0':
    Sc = [0]
else:
    Sc = []

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

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

#print(Sc)

ansp = [sum(Sc[:2*K+1])]

for i in range(2*K+1, len(Sc), 2):
    ansp.append(ansp[-1]-Sc[i-2*K-1]-Sc[i-2*K]+Sc[i]+Sc[i+1])
ans = max(ansp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

tmp = None
cnt = 0
for s in S:
  if tmp == None:
    cnt += 1
    tmp = s
  else:
    if s == tmp:
      cnt += 1
    else:
      L.append(cnt)
      tmp = s
      cnt = 1
else:
  L.append(cnt)
  L.insert(0,0)

if S[0] == "0":
  L.insert(0,0)

acc = list(accumulate(L))

ans = 0
last = len(acc)

for i in range(0, last, 2):
  right = 2 * K + i + 1
  left = i
  ans = max(ans, acc[min(last-1, right)] - acc[left])

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


def main():
    N, K = MI()
    s = S()
    a = [0]
    first_zero = s[0] == '0'
    cur = s[0]

    for i in range(len(s)):
        if cur == s[i]:
            a[-1] += 1
        else:
            cur = s[i]
            a.append(1)

    # print(a)
    # print(first_zero, limit)
    ans = 0
    cur = 0
    right = 0
    for left in range(len(a)):
        if first_zero:
            if left % 2 == 0:
                limit = 2 * K
            else:
                limit = 2 * K + 1
        else:
            if left % 2 == 0:
                limit = 2 * K + 1
            else:
                limit = 2 * K
        # limit = 2 * K if first_zero else 2 * K + 1

        while right < len(a) and right - left < limit:
            cur += a[right]
            right += 1

        ans = max(cur, ans)
        cur -= a[left]
        # print(ans, cur, cur + a[left], left, right)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    lz = []
    lo = []
    o = z = 0
    for i in S:
        if i == '1':
            o += 1
            if z > 0:
                lz.append(z)
                z = 0
        else:
            z += 1
            if o > 0:
                lo.append(o)
                o = 0
    lo.append(o)
    if z > 0:
        lz.append(z)
    if len(lz) <= K:
        return N
    if S[0] == '1':
        lz[0] += lo[0]
        lo = lo[1:]
    lo.append(0)
    m = t = sum(lz[:K]) + sum(lo[:K])
    for i in range(len(lz) - K):
        if i == 0:
            t -= lz[i]
        else:
            t -= (lz[i] + lo[i-1])
        t += (lz[i + K] + lo[i + K])
        m = max(m, t)
    return m
print(main())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    lz = []
    lo = []
    o = 0
    z = 0
    for i in S:
        if i == '1':
            o += 1
            if z > 0:
                lz.append(z)
                z = 0
        if i == '0':
            z += 1
            if o > 0:
                lo.append(o)
                o = 0
    if o > 0:
        lo.append(o)
    if z > 0:
        lz.append(z)
    if len(lz) <= K:
        return N
    if S[0] == '0':
        m = t = sum(lz[:K]) + sum(lo[:K])
        for i in range(len(lz) - K):
            if i == 0:
                t -= lz[i]
            else:
                t -= (lz[i] + lo[i-1])
            if len(lo) == (i + K):
                t += lz[i + K]
            else:
                t += (lz[i + K] + lo[i + K])
            m = max(m, t)
        return m
    if S[0] == '1':
        m = t = sum(lz[:K]) + sum(lo[:K+1])
        for i in range(len(lz) - K):
            t -= (lz[i] + lo[i])
            if len(lo) == (i + K + 1):
                t += lz[i + K]
            else:
                t += (lz[i + K] + lo[i + K + 1])
            m = max(m, t)
        return m
print(main())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    class LL:
        def __init__(self, v, p, n):
            self.v = v
            self.p = p
            self.n = n
    T = []
    m = 0
    for s in S:
        if s == '0':
            if m >= 0:
                T.append(m)
                m = 0
            m -= 1
        else:
            if m < 0:
                T.append(-m)
                m = 0
            m += 1
    T.append(abs(m))
    if m < 0:
        T.append(0)
    m = t = sum(T[:K * 2 + 1])
    L = K * 2 + 1
    for i in range(0, len(T) - L, 2):
        t = t + T[L + i] + T[L + i + 1] - T[i] - T[i + 1]
        m = max(m, t)
    print(m)
main()

Submission status: Accepted

Solution code:
from operator import itemgetter

def main():
    N,K = map(int,input().split())
    S = [int(s) for s in input()] + [1]
    used = [0]*(N + 3)
    right = -1
    ans = 0
    for left in range(N):
        if S[left] + S[left - 1] == 0:
            continue
        while right < N and used[right] - used[left-1] <= K:
            right += 1
            if S[right]:
                used[right] = used[right - 1]
            else:
                if S[right-1]:
                    used[right] = used[right - 1] + 1
                else:
                    used[right] = used[right - 1]
        ans = max(ans,right - left)
    print(ans)
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

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

S += '2'
l = []
cnt = 1
for i in range(N):
  if S[i] == S[i+1]:
  	cnt += 1
  else:
    l.append(cnt)
    cnt = 1

if S[0] == '0':
  cur = sum(l[:2*K])
  ans = cur
  for j in range(1, len(l), 2):
    cur += -sum(l[max(0, j-2): j]) + sum(l[j+2*K-1:j+2*K+1])
    ans = max(ans, cur)
else:
  cur = sum(l[:2*K+1])
  ans = cur
  for j in range(2, len(l), 2):
    cur += -sum(l[max(0, j-2): j]) + sum(l[j+2*K-1:j+2*K+1])
    ans = max(ans, cur)
print(ans)

Submission status: Accepted

Solution code:
def solve(s, k):
    c = []
    if s[0] == '0':
        c.append(0)

    target = ''

    for si in s:
        if si != target:
            target = si
            c.append(1)
        else:
            c[-1] += 1

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

    c_len = len(c)

    if 2*k+1 >= c_len:
        return sum(c)
    else:
        current = sum(c[0:2*k+1])
        ans = current

        for i in range(2, c_len-2*k, 2):
            current -= (c[i-2] + c[i-1])
            current += (c[i+2*k-1]+c[i+2*k])
            ans = current if current > ans else ans
    return ans


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

Submission status: Accepted

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

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

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

leng=len(num_cnt)
if leng/2>k:
  ans=sum(num_cnt[:2*k])
  tot=ans
  
  if leng%2==0:
    limit=leng//2-k
  else:
    num_cnt.append(0)
    limit=leng//2-k+1
  
  #print(ans)
  #print(num_cnt)
  tmp2=num_cnt[2*k]+num_cnt[2*k+1]-num_cnt[0]
  tot+=tmp2
  if tot>ans:
    ans=tot
  
  for i in range(1,limit):
    #print(2*(i+k)+1)
    tmp=num_cnt[2*(i+k)]+num_cnt[2*(i+k)+1]-num_cnt[2*i]-num_cnt[2*i-1]
    #print(tot)
    tot+=tmp
    if tot>ans:
      ans=tot
else:
  ans=n
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
s = readline().rstrip().decode('utf-8')

if s[0] == 0: #反転からスタート
    r = 0
else: #無操作からスタート
    r = 1

if r==0:
    lst1 = [0] #裏からに調整
else:
    lst1 = []
res = 0
cache = str(r)
for i in s:
    if i != cache:
        lst1.append(res)
        cache = "1" if cache=="0" else "0"
        res = 1
    else:
        res += 1

lst1.append(res)
lst1.append(0)

#全部1で埋められるなら
if len(lst1) <= 2*k:
    print(n)
    exit()

#累積和
for i in range(len(lst1)-1):
    lst1[i+1] += lst1[i]

def cumsumdif(a,b,lst): #求めたい差のインデックスを入れる
    if a == 0:
        return lst[b]
    else:
        return lst[b] - lst[a-1]
i = 0
ans = 0
while True:
    if i+(k*2) >= len(lst1):
        break
    ans = max(ans,cumsumdif(i,i+2*k,lst1))
    i += 2

print(ans)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    S = str(input())
    if S[0] == "1":
        z,o = [0],[]
    else:
        z,o = [0],[0]
        
    for i in range(N-1):
        if S[i+1] != S[i]:
            if S[i] == "1":
                o.append(i+1)
            else:
                z.append(i+1)
                
    o.append(N)            
    if S[-1] == "0":
        z.append(N)

    l = len(o)
    if l == 1:
        print(N)
    else:
        if K+1 > l:
            print(N)
        else:
            ans = 0
            for i in range(l-K):
                u = o[i+K]-z[i]
                ans = max(ans,u)
            print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import add
N, K = map(int, input().split())
S = input()

Nums = []

tmp = "1"
cnt = 0
for s in S:
  if s == tmp:
    cnt += 1
  else:
    Nums.append(cnt)
    tmp = s
    cnt = 1
else:
  Nums.append(cnt)
  if tmp == "0":
    Nums.append(0)

T = list(accumulate(Nums))
T.insert(0,0)

ans = 0
len_t = len(T)
for i in range(0, len_t, 2):
  left = i
  right = min(len_t - 1, (2 * K + 1) + i)
  ans = max(ans, T[right] - T[left])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

# 連続した 0 と 1 の数を数える
cnt_list = []
flag = True if S[0] == '1' else False
cnt = 1
flag_flag = True
for i in range(1, N):
    if S[i] == '1':
        if i == N - 1:
            flag_flag = True
        if flag:
            cnt += 1
        else:
            flag = True
            cnt_list.append([cnt, -1])
            cnt = 1
    if S[i] == '0':
        if i == N - 1:
            flag_flag = False
        if flag:
            flag = False
            cnt_list.append([-1, cnt])
            cnt = 1
        else:
            cnt += 1
if not flag_flag:
    cnt_list.append([cnt, -1])
else:
    cnt_list.append([-1, cnt])
# 指示する回数を求める． K 回 >= 連続した 0 の個数の時は上手に行えば全て逆立ちできる
n = len(cnt_list)
if cnt_list[0][0] == -1:    # 1 スタート
    if K >= n//2:
        print(N)
        exit()
    k = K
else:                       # 0 スタート
    if K >= math.ceil(n/2):
        print(N)
        exit()
    k = K

# あとは区間内の総和を計算するのに累積和を用いる
# 累積和を計算
cumsum = [0] * (n+1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + max(cnt_list[i])

ans = 0
if cnt_list[0][0] == -1:        # 1 start
    if cnt_list[-1][0] == -1:   # 1 end
        for i in range(1, n - 2 * k + 1, 2):
            ans = max(ans, cumsum[2 * k + i] - cumsum[i-1])
    else:                        # 0 end
        for i in range(1, n - 2*k + 1, 2):
            ans = max(ans, cumsum[2 * k + i] - cumsum[i-1])
        ans = max(ans, cumsum[n] - cumsum[n - 2*k])
    
else:                           # 0 start
    if cnt_list[-1][0] == -1:   # 1 end
        ans = cumsum[2*k] - cumsum[0]
        for i in range(2, n - 2 * k + 1, 2):
            ans = max(ans, cumsum[2 * k + i] - cumsum[i-1])
    else:                       # 0 end
        ans = cumsum[2 * k] - cumsum[0]
        for i in range(2, n - 2 * k + 1, 2):
            ans = max(ans, cumsum[ 2* k + i] - cumsum[i-1])
        ans = max(ans, cumsum[n] - cumsum[n - 2*k])
##print(cumsum)
print(ans)

Submission status: Accepted

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

first = now = S[0]

count = [] # 逆立ち、直立している人がそれぞれ何人連続しているか
c = 0
for s in S:
  if s == now:
    c += 1
  else:
    count.append(c)
    c = 1
    now = s

count.append(c)

l = len(count)
if first == '0':
  up_group = -(-l//2) # 直立しているグループ数
else:
  up_group = l//2

if up_group <= K: # 直立している人全員を逆立ちに変えられる
  print(N)
  quit()


if first == '0':
  ans = sum(count[:2*K])
  s = ans
  idx1 = 0
  idx2 = 2*K
  while idx2 < l:
    if idx1 == 0:
      s = s - count[0] + sum(count[idx2:idx2+2])
      idx1 += 1
    else:    
      s = s - sum(count[idx1:idx1+2]) + sum(count[idx2:idx2+2])
      idx1 += 2
    
    idx2 += 2
    ans = max(ans, s)
  
  print(ans)
else:
  ans = sum(count[:2*K+1])
  s = ans
  idx1 = 1
  idx2 = 2*K+1
  while idx2 < l:
    if idx1 == 1:
      s = s - sum(count[:2]) + sum(count[idx2:idx2+2])
      idx1 += 1
    else:
      s = s - sum(count[idx1:idx1+2]) + sum(count[idx2:idx2+2])
      idx1 += 2
    
    idx2 += 2
    ans = max(ans, s)
  
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from itertools import groupby
def input(): return sys.stdin.readline().rstrip()

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

    ans = 0
    l = 0
    que = deque()
    que_sum = 0
    for k, v in groupby(S):
        if k == '0':
            l0 = len(tuple(v))
            que_sum += l0
            que.append(l + l0)
            if len(que) > K:
                que_sum -= que.popleft()
        else:
            l = len(tuple(v))
            que_sum += l
        if que_sum > ans:
            ans = que_sum
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

xs = []
cur, length = S[0], 1
for i in range(1, N):
    if S[i] != cur:
        xs.append((cur, length))
        cur = S[i]
        length = 1
    else:
        length += 1
xs.append((cur, length))

if sum(1 for v, l in xs if v == 0) <= K:
    print(N)
else:
    length = 0
    changed_count = 0
    for i, (v, l) in enumerate(xs):
        if v == 0:
            changed_count += 1
        length += l
        if changed_count == K:
            left = 0 if xs[0][0] == 0 else 1
            if i + 1 < len(xs):
                length += xs[i + 1][1]
            break
    max_length = length
    for right in range(i + 2, len(xs), 2):
        length -= xs[left][1]
        if 0 <= left - 1:
            length -= xs[left - 1][1]
        length += xs[right][1]
        if right + 1 < len(xs):
            length += xs[right + 1][1]
        max_length = max(max_length, length)
        left += 2
    print(max_length)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n,k = inpm()
    s = list(input())
    t = [0]
    for i in range(n-1):
        if s[i] != s[i+1]:
            t.append(i+1)
    a = len(t)
    if len(t)<2*k-1:
        print(n)
        return
    for i in range(2*a+4):
        t.append(n)
    ans = 0
    if s[0]=='1':
        for i in range(a):
            if 2*k+2*i+1 >= len(t):
                break
            ans = max(ans,t[2*k+2*i+1]-t[2*i])
    else:
        ans = t[2*k]
        for i in range(a):
            if 2*k+2*i+2 >= len(t):
                break
            ans = max(ans,t[2*k+2*i+2]-t[2*i+1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
s=input()
if '0' not in s:
    print(len(s))
else:
    s2 = [0]
    count = 0
    for i in range(len(s)-1):
        count += 1
        if s[i] != s[i+1]:
            s2.append(count)
    s2.append(count+1)
    if s[0] == '0':
        s2.insert(0,0)
    ans = 0
    for i in range(0,len(s2)-1,2):
        ans = max(ans,s2[min(len(s2)-1,i+2*K+1)] - s2[i])
    print(ans)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()
s += '0'

def main():
    l = [0]
    r = [0]
    flag = False
    for i in range(n+1):
        if s[i] == '1':
            if not flag:
                l.append(i)
            flag = True
        else:
            if flag:
                r.append(i-1)
            flag = False

    l.append(n-1)
    r.append(n-1)
    m = len(l)

    if k >= m - 1:
        return n
    res = 0
    for i in range(m-k):
        res = max(res, r[i+k]-l[i]+1)
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = list(input())
s_0_1 = [1]*(k+int(s[0]))
s_1_0 = []
for i in range(n-1):
    if s[i] == "0" and s[i+1] == "1":
        s_0_1.append(i+2)
    elif s[i] == "1" and s[i+1] == "0":
        s_1_0.append(i+1)
s_1_0.extend([n]*(k+int(s[-1])))
ans = 0
for i in range(len(s_0_1)):
    ans = max(ans, s_1_0[i]-s_0_1[i]+1)
print(ans)

Submission status: Accepted

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

c0 = S.count('0')
if c0 == 0 or c0 == N:
  ans = N
else:
  A = [[0, 0, 0]]
  c = 0
  now = '1' if S[0]=='0' else '0'
  for s in S:
    if s == '0':
      if now == '1':
        A[-1][2] = c
        A.append([c, 1, 0])
        c = 1
        now = '0'
      else:
        c += 1
    else:
      if now == '1':
        c += 1
      else:
        A[-1][1] = c
        c = 1
        now = '1'
  
  A = A[1:]  
  if s == '0':
    if S[-2] == '0':
      A[-1][1] = c
  else:
    if S[-2] == '0':
      A[-1][2] = 1
    else:
      A[-1][2] = c
  m = len(A)
  if m <= K:
    ans = N
  else:
    ans = 0
    for i, a in enumerate(A):
      ans += a[0]+a[1]
      if i == K-1:
        ans += a[2]
        break

    l = ans
    for i in range(1, m-K+1):
      a1 = A[i-1]
      a2 = A[i+K-1]
      l = l-(a1[0]+a1[1])+(a2[1]+a2[2])
      ans = max(ans, l)


print(ans)

Submission status: Accepted

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

cnt = 0

if s[0] == '0': ss.append(0)
i = 0
while i < n:
    j = i
    while j < n and s[i] == s[j]: j += 1
    ss.append(j-i)
    i = j
if s[-1] == '0': ss.append(0)

right = 2*k+1
left = 0
val = sum(ss[:right])
ans = val

#print(ss)
while right < len(ss):
    for i in [1, 2]:
        #print('for', ss[left], ss[right])
        val += ss[right]
        val -= ss[left]
        left += 1
        right += 1
    #print(left, right, val)
    ans = max(ans, val)
    
print(ans)

Submission status: Accepted

Solution code:
def f(nums, l):
  out=sum(nums[:l])
  tmp=sum(nums[:l])
  n=len(nums)
  i=2
  while i+l-1<n:
    tmp=tmp-nums[i-2]-nums[i-1]+nums[i+l-2]+nums[i+l-1]
    out=max(out, tmp)
    i+=2
  return out

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

i=0
j=1
nums=[]
while i<N:
  while j<N and S[i]==S[j]:
    j+=1
  nums.append(j-i)
  i=j
  j=i+1
  
if S[0]=='0':
  nums=[0]+nums
  
if S[-1]=='0':
  nums=nums+[0]
  
ans=f(nums, 2*K+1)
print(ans)

Submission status: Accepted

Solution code:
#1からスタートして2*K+1個

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

s=1
temp=0
for i in range(N):
    if s!= int(S[i]):
        A.append(temp)
        temp=1
        s=(s+1)%2
    else:
        temp+=1
        
A.append(temp)
if s==0:
    A.append(0)
        
NA=len(A)
if 2*K+1>=NA:
    ans=N
else:
    temp=sum(A[:2*K+1])
    ans=temp
    for i in range(0,NA-2*K-2,2):
        temp=temp-A[i]-A[i+1]+A[i+2*K+1]+A[i+2*K+2]
        ans=max(ans,temp)
        
print(ans)

Submission status: Accepted

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

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

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

ans = 0

k = min(k,len(stand)-1)
for i in range(len(rev) - k - 1):
	sms = rev[i+k+1] - rev[i] + stand[i+k] - stand[i]
	ans = max(ans,sms)

print(ans)