Problem:


Score : 400 points

Problem Statement

N people are arranged in a row from left to right.

You are given a string S of length N consisting of 0 and 1, and a positive integer K.

The i-th person from the left is standing on feet if the i-th character of S is 0, and standing on hands if that character is 1.

You will give the following direction at most K times (possibly zero):

Direction: Choose integers l and r satisfying 1 \leq l \leq r \leq N, and flip the l-th, (l+1)-th, ..., and r-th persons. That is, for each i = l, l+1, ..., r, the i-th person from the left now stands on hands if he/she was standing on feet, and stands on feet if he/she was standing on hands.

Find the maximum possible number of consecutive people standing on hands after at most K directions.

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of consecutive people standing on hands after at most K directions.

Sample Input 1

5 1
00010

Sample Output 1

4

We can have four consecutive people standing on hands, which is the maximum result, by giving the following direction:

Give the direction with l = 1, r = 3, which flips the first, second and third persons from the left.

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N,K=map(int,readline().split())
    S=readline().strip()

    li=[]
    i=0
    now=0
    if S[0]=="0":
        li.append(0)
    while i<len(S):
        if S[i]=="1":
            while True:
                if S[i]=="1":
                    now+=1
                    i+=1
                    if i==len(S):
                        break
                else:
                    break
        elif S[i]=="0":
            while True:
                if S[i]=="0":
                    now+=1
                    i+=1
                    if i==len(S):
                        break
                else:
                    break
        li.append(now)
        now=0
                
    #累積和
    for i in range(len(li)):
        if i==0:
            continue
        else:
            li[i]+=li[i-1]

    res=0
    if len(li)>=2*K+1:
        for left in range(0,len(li),2):
            if left==0:
                res=li[2*K]
            else:
                res=max(res,li[min(2*K+left,len(li)-1)]-li[left-1])
    else:
        res=li[-1]
    print(res)
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

# 連続で0か1が連なっているリストを作成
# (0or1, 個数)
sum_s = []
cnt = 0
flag = int(s[0])
if flag == 0:
    sum_s.append((1, 0))
flag = int(s[0])
for i in range(n):
    if s[i] == '0':
        if flag == 0:
            cnt += 1
        else:
            sum_s.append((flag, cnt))
            flag, cnt = 0, 1
    else:
        if flag == 0:
            sum_s.append((flag, cnt))
            flag, cnt = 1, 1
        else:
            cnt += 1
sum_s.append((flag, cnt))
#print(sum_s)

# 累積和
rs = [0] * (len(sum_s)+1)
for i in range(1, len(sum_s)+1):
    rs[i] = rs[i-1] + sum_s[i-1][1]

ans = 0

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

Submission status: Accepted

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

ans = 0

check =[[0]]
i = 0
while i < n:
    if l[i] == "1":
        a = i
        while i < n and l[i] == "1":
            i += 1
        check.append([a,i-1])
    i += 1
check.append([n-1])
if len(check)-k < 1:
    print(n)
    exit()
for i in range(len(check)-k):
       
    ans = max(ans,check[i+k][-1]-check[i][0]+1)
print(ans)

Submission status: Accepted

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

if S[0]=='0':
  counts.append(0)
if N == 1:
  counts.append(1)
  
for i in range(1,N):
  if S[i-1]!=S[i]:
    counts.append(cnt)
    cnt = 1
  else:
    cnt += 1
  #print(i)
  if i == N-1:
    counts.append(cnt)

#print(counts)
K = min(K,len(counts)//2)
for i in range(len(counts)//2-K+1):
  if i == 0:
    s = sum(counts[:2*K+1])
    m = s
  else:
    s += sum(counts[2*(i+K)-1:2*(i+K)+1])-sum(counts[2*i-2:2*i])
    m = max(m,s)
  #print(s)
print(m)

Submission status: Accepted

Solution code:
import bisect
# from collections import Counter, defaultdict, deque, namedtuple
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

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

    lg = [0] * (n+3)

    s_first = s[0]
    s_last =s[-1]

    idx = 0

    if s_first == "0":
        lg[0] = 0
        idx = 1

    s_groupby = itertools.groupby(s)

    for _, group in s_groupby:
        lg[idx] = len(list(group))
        idx += 1

    if s_last == "0":
        idx += 1

    rn = 2*k + 1

    if rn >= idx:
        print(n)
        sys.exit()

    temp = sum(lg[0:rn])
    ans = temp

    for i in range(2, idx-rn+1, 2):
        temp -= (lg[i-2] + lg[i-1])
        temp += (lg[i-2+rn] + lg[i-1+rn])
        ans = max(ans, temp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

scomp = []

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


lens = len(scomp)
ans = 0

start = 0
if s[0] == '0':
    start = 1
    end = min(k*2,lens)
    tmp = sum(scomp[:end])
    ans = max(ans,tmp)

end = min(start + k*2+1,lens)
tmp = sum(scomp[start:end])
ans = max(ans,tmp)
for i in range(start,lens-k*2-2,2):
    tmp -= scomp[i]
    tmp -= scomp[i+1]
    tmp += scomp[i+k*2+1]
    tmp += scomp[i+k*2+2]
    ans = max(ans,tmp)

if s[-1] == '0':
    start = max(lens-k*2,0)
    tmp = sum(scomp[start:])
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

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

# nums[i]: iが偶数なら1の個数 奇数なら0の個数
nums = []

if S[0] == "0":
    nums.append(0)

# 尺取り法
left = 0
while left < N:
    right = left
    while right < N and S[right] == S[left]:
        right += 1
    nums.append(right - left)
    left = right

if S[-1] == "0":
    nums.append(0)

from itertools import accumulate

nums = [0] + list(accumulate(nums))

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

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
r = [0, 1]
prev = s[0]

for i in range(1, len(s)):
    if prev == s[i]:
        r[-1] += 1
    else:
        r.append(r[-1] + 1)
    prev = s[i]

lr = len(r)
import math
# 0の数よりkが大きい
if s[0] == '0' and math.ceil((lr-1) / 2) <= k:
    print(len(s))
    exit()
if s[0] == '1' and math.floor((lr-1) / 2) <= k:
    print(len(s))
    exit()

start = 0
if s[0] == '0':
    start = 1

ans = 0
for i in range(start, lr - (2 * k + 1), 2):
    ans = max(ans, r[i + (2 * k + 1)] - r[i])
    #print(i, i+(2*k)+1, r[i+(2 * k)+1] - r[i])

#print(ans)
# 0始まり
if s[0] == '0':
    ans = max(ans, r[2 * k] - r[0])
    #print(ans)
# 0終わり
if s[-1] == '0':
    ans = max(ans, r[-1] - r[lr - 2 * k - 1])
    #print(ans)
#print(r)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
l = [1]
for i in range(N-1):
    if S[i] == S[i+1]:
        l[-1] += 1
    else:
        l.append(1)
if S[0] == "0":
    l = [0] + l
if S[-1] == "0":
    l += [0]
s = [0]
for i in range(len(l)):
    s.append(s[-1]+l[i])
if len(l) <= 2*K + 1:
    print(s[-1])
else:
    cnt = 0
    for i in range((len(l)-2*K-1)//2+1):
        cnt = max(cnt,s[2*K+2*i+1]-s[2*i])
    print(cnt)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(sl):

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append(c)
      a=x
      c=1
  res.append(c)

  return res
# Summarize count of factor within list --- END ---

def main():
  n,k=LI()
  s=list(S())

  l=summarize_list(s)
  # print(l)

  # 1 0 1 0... の形にする
  if s[0]=='0':
    l=[0]+l

  # ...0 1 0 1 の形にする
  if s[-1]=='0':
    l+=[0]

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

  l=[0]+l

  # print(l)

  ans=0
  left=0
  while True:
    right=min(len(l)-1,left+2*k+1)
    if left>=len(l):
      return ans

    # print(right,left)
    ans=max(ans,l[right]-l[left])

    left+=2

# main()
print(main())

Submission status: Accepted

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

if s[0]=='0':
    seq=[0]
else:
    seq=[]

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

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

bleft=0
bright=min(2*k,len(seq)-1)

cursum=sum(seq[bleft:bright+1])
ret=cursum

for i in range(2,len(seq),2):
    left=i
    right=min(i+2*k,len(seq)-1)

    if bleft!=left:
        cursum-=seq[bleft]+seq[bleft+1]
        bleft=left
    if bright!=right:
        cursum+=seq[right-1]+seq[right]
        bright=right
    
    ret=max(ret,cursum)
    
print(ret)

Submission status: Accepted

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

prev = S[0]
renzoku_start = [0]
for i in range(1, N):
  if prev == S[i]:
    continue
  else:
    prev = S[i]
    renzoku_start.append(i)
renzoku_start.append(N)

ans = []
l = len(renzoku_start)
for j in range(l):
  if S[renzoku_start[j]] == 0:
    if j + 2 * K >= l:
      ans.append(N - renzoku_start[j])
      break
    ans.append(renzoku_start[j + 2 * K] - renzoku_start[j])
  else:
    if j + 2 * K + 1 >= l:
      ans.append(N - renzoku_start[j])
      break
    ans.append(renzoku_start[j + 2 * K + 1] - renzoku_start[j])

if ans:
  print(max(ans))
else:
  print(N)

Submission status: Accepted

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

count = 1
Nums_count = []
now = s[0]
start = 0
for i in range(1,n):
    if s[i] == str(now):
        count += 1
    else:
        Nums_count.append([start, count])
        now = s[i]
        start = i
        count = 1
    if i == n-1:
        Nums_count.append([start, count])
if len(s) == 1:
    Nums_count.append([0,1])

Nums_count_rui = [[-1, 0]]
for i in range(len(Nums_count)):
    Nums_count_rui.append([Nums_count[i][0],Nums_count[i][1]+Nums_count_rui[-1][1]])

# print(Nums_count_rui)
ans = 0
m = len(Nums_count_rui)

if s[0] == '0' and m <= 2*k:
    ans = n
elif s[0] == '1' and m <= 2*k+1:
    ans = n

for i in range(1,m):
    if s[Nums_count_rui[i][0]] == '0':
        if i+2*k-1 >= m:
            tot = Nums_count_rui[-1][1] - Nums_count_rui[i-1][1]
        else:
            tot = Nums_count_rui[i+2*k-1][1] - Nums_count_rui[i-1][1]
    else:
        if i+2*k >= m:
            tot = Nums_count_rui[-1][1] - Nums_count_rui[i-1][1]
        else:
            tot = Nums_count_rui[i+2*k][1] - Nums_count_rui[i-1][1]
    ans = max(tot, ans)
print(ans)

Submission status: Accepted

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

change = [0]
for i, (e1, e2) in enumerate(zip(s, s[1:])):
	e1 = int(e1)
	e2 = int(e2)
	if e1 ^ e2:
		change.append(i + 1)

change.append(n)
end = len(change) - 1

ans = 0
for i, l in enumerate(change[:-1]):
	if s[l] == "1":
		ri = min(i + 2 * k + 1, end)
	else:
		ri = min(i + 2 * k, end)

	r = change[ri]

	ans = max(ans, r - l)

print(ans)

Submission status: Accepted

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

from itertools import groupby

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

S_groupby = groupby(S)

zero_idx = [] # ゼロが何番目か
value_list = [] # 各インデックスのキーに対する個数
i = -1
for j in S_groupby:
    i += 1
    key, value = j[0], len(list(j[1]))
    value_list.append(value)
    if key == '0':
        zero_idx.append(i)

if len(zero_idx) <= K:
    print(len(S))
    sys.exit()

left = zero_idx[0]
right = zero_idx[K - 1]
if zero_idx[0] == 0:
    ans = [sum(value_list[left:right + 2])]
else:
    ans = [sum(value_list[left - 1:right + 2])]

for i in range(K, len(zero_idx)):
    new_right = zero_idx[i]
    new_left = zero_idx[i - K + 1]
    new_ans = ans[-1] + value_list[new_right] - value_list[left]
    if new_right + 1 < len(value_list):
        new_ans += value_list[new_right + 1]
    if left - 1 >= 0:
        new_ans -= value_list[left - 1]
    ans.append(new_ans)
    right, left = new_right, new_left

print(max(ans))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from bisect import bisect_left,bisect_right,insort
#input = sys.stdin.readline

def main():
    n,k=map(int,input().split())
    s=list(input())
    flg,cnt,chk='1',0,[0]    
    for i in range(n):
        if s[i]==flg:
            chk[cnt]+=1
        else:
            flg=str((int(flg)+1)%2)
            cnt+=1
            chk.append(1)
    if s[-1]=='0':
        chk.append(0)
    lng=len(chk)
    if k*2>lng:
        print(n)
    else:
        ans=0
        acc=[0]+list(accumulate(chk))
        for i in range(0,len(chk)-2*k,2):
            ans=max(ans,acc[i+2*k+1]-acc[i])
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input()
seq = []
pre = '1'
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        pre = c
        seq.append(count)
        count = 1
seq.append(count)

n = len(seq)
sum = sum(seq[:2*k + 1])
ans = sum
seq.append(0)
for i in range(0, n - 2*k - 1, 2):
    sum -= seq[i] + seq[i + 1]
    sum += seq[i + 2*k + 1] + seq[i + 2 * k + 2]
    ans = max(ans, sum)
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
one = [0]
zero = [0]
if S[0] == '0':
    one.append(0)
cnt = 1
for i in range(1,len(S)):
    if S[i] != S[i-1]:
        if S[i-1] == '1':
            one.append(cnt+one[-1])                
        else:
            zero.append(cnt+zero[-1])                
        cnt = 1
    else:
        cnt += 1
else:
    if S[-1] == '1':
        one.append(cnt+one[-1])                
    else:
        zero.append(cnt+zero[-1])                
        one.append(one[-1])                
window_size = min(len(zero)-1,K)
MAX = 0
for i in range(len(zero)-window_size):
    if MAX < (zero[i+window_size] - zero[i]) + (one[i+window_size+1] - one[i]):
        MAX = (zero[i+window_size] - zero[i]) + (one[i+window_size+1] - one[i])

print(MAX)

Submission status: Accepted

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

def main():
  n, k = map(int, input().split())
  s = input().strip()
  sz, ez = [], []
  i = 0
  while i < n:
    if s[i] == '0':
      sz.append(i)
      while i < n and s[i] == '0': i += 1
      ez.append(i)
    else:
      i += 1
  
  if k >= len(sz):
    print(len(s))
    return 
  max = -1
  for i in range(len(sz)-k+1):
    if i==0:
      score = sz[i+k] - 0
    elif i==len(sz)-k:
      score = n - ez[i-1]
    else:
      score = sz[i+k] - ez[i-1]
    if max < score:
      max = score
  print(max)
      

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S=list(input())
A=[]
a=1
for i in range(n-1):
  if S[i]==S[i+1]:
    a=a+1
  else:
    A.append(a)
    a=1
A.append(a)
b=len(A)
if S[0]=="0":
  if k>=(b+1)//2:
    print(n)
  else:
    A.insert(0,0)
    ans=0
    d=0
    for i in range(2*k+1):
      d=d+A[i]
      ans=d
    for i in range((b-2*k)//2):
      d=d-A[2*i]-A[2*i+1]+A[(k+i)*2+1]+A[(k+i+1)*2]
      if d>ans:
        ans=d
    if S[-1]=="0":
      d=d-A[b-(k+1)*2+1]-A[b-(k+1)*2+2]+A[b]
      if d>ans:
        ans=d
    print(ans)  
else:
  if k>=len(A)//2:
    print(n)
  else:
    ans=0
    d=0
    for i in range(2*k+1):
      d=d+A[i]
      ans=d
    for i in range((b-2*k-1)//2):
      d=d-A[2*i]-A[2*i+1]+A[(k+i)*2+1]+A[(k+i+1)*2]
      if d>ans:
        ans=d
    if S[-1]=="0":
      d=d-A[b-(k+1)*2]-A[b-(k+1)*2+1]+A[b-1]
      if d>ans:
        ans=d
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
l = [1]
for i in range(N-1):
  if S[i] == S[i+1]:
    l[-1] += 1
  else:
    l.append(1)
if S[0] == "0":
  l = [0] + l
if S[-1] == "0":
  l += [0]
#print(l)
n = len(l)
ans = sum(l[:min(K*2+1, n+1)])
i = 0
M = ans
while True:
  if K*2 + i+1 >= n:
    break
  M = M + l[K*2+1 + i] + l[K*2+1 + i+1] - l[i] -l[i+1]
  #print(ans, M)
  ans = max(ans, M)
  i += 2
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
nums = []
now = 1
cnt = 0
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

csum = [0] * (len(nums) + 1)
for i in range(len(nums)):
    csum[i + 1] = csum[i] + nums[i]

add = 2 * K + 1
ans = 0
tmp = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(i + add, len(nums))
    tmp = csum[right] - csum[left]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
nums = []
now = 1
cnt = 0
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * K + 1
ans = 0
left = 0
right = 0
tmp = 0
for i in range(0, len(nums), 2):

    next_left = i
    next_right = min(i + add, len(nums))

    while next_left > left:
        tmp -= nums[left]
        left += 1

    while next_right > right:
        tmp += nums[right]
        right += 1

    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
C=[]
flag=False
count=0
prv=S[0]
if S[0]!="1":
    C.append(0)
"""
for i in range(N):
    if prv!=S[i]:
        C.append(count)
        count=1
    else:
        count+=1
    prv=S[i]
if count>0:
    C.append(count)
"""
tmp=0
for i in range(len(S)):
    if i<tmp:
        continue
    j=tmp
    while(S[j]==S[i]):
        j+=1
        if j==len(S):
            break
    C.append(j-i)
    tmp=j
if S[-1]=="0":
    C.append(0)
if len(C)==1:
    print(sum(C))
    exit()
ans=0
#print(C)
sums=[0]*(len(C))
sums.append(0)
for i in range(len(C)):
    sums[i+1]=sums[i]+C[i]
#print(sums)
for left in range(0,len(sums),2):
    right=left+2*K+1
    if right>=len(sums):
        right=int(len(sums))-1
    ans=max(ans,sums[right]-sums[left])
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(100001)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n, k = map(int, input().split())
d = str(input())
tmp = list(d)
data = [int(s) for s in tmp]

ans = 0

cnt_list = []

tmp = 1
cnt = 0
for i in range(n):
    if data[i] == tmp:
       cnt += 1
    else:
        cnt_list.append(cnt)
        cnt = 1
        tmp = 1 - tmp
if cnt != 0:
    cnt_list.append(cnt)

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

sum_list = [0]
sum_num = 0
for d in cnt_list:
    sum_num += d
    sum_list.append(sum_num)

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

print(ans)

Submission status: Accepted

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

L = [0]
tmp = '1'

"""
下記をLに格納する。

0,2,4,6...番目のidxは1の値の個数
1,3,5,7,...番目のidxは0の値の個数

また、Lの最後の要素は「1の値の個数」となるようにする。
（なので、0になることもある）
これで、無理やりLの要素数を必ず奇数になるように強制する。
これで「1の値の個数」で始まって終わる配列を取得する。
"""

for s in S:
  if s == tmp:
    L[-1] += 1
  else:
    L.append(1)
  tmp = s

if tmp == '0':
  L.append(0)


## 全てを1、もしくは0で表現できてしまう場合は文字列の長さをそのまま出力する
M = len(L)
if M <= 2*K+1:
  ans = N
  print(ans)
  exit()


## 累積を計算
## 最初の要素は使わない（下記のループを簡単に書くために要素を一個多くしているだけ）
X = [0]*(M+1)
for i in range(M):
  X[i+1] = X[i] + L[i]


## answer
ans = 0
for m in range(0,M-2*K,2):
  _ = X[2*K+m+1]-X[m]
  ans = max(ans, _)


print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=input()
L=[0]
#even:1
#odd:0
tmp="1"
for i in range(N):
    if tmp!=S[i]:
        L.append(1)
    else:
        L[-1]+=1
    tmp=S[i]

if tmp=="0":
    L.append(0)


M=len(L)
## 1しか無い場合は長さを出力して終わり
if M<=2*K+1:
    print(N)
    exit()


X=[0 for i in range(M+1)]
for i in range(M):
    X[i+1]=L[i]+X[i]


ans=0
for i in range(0,M-2*K,2):
    #print(X[i],X[i+2*K+1])
    ans=max(ans,X[i+2*K+1]-X[i])
print(ans)

Submission status: Accepted

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

cnt_sum=[0]
for i in range(len(cnt)):
    tmp=cnt_sum[i]+cnt[i]
    cnt_sum.append(tmp)
    
ans=1
for i in range(0,len(cnt_sum),2):
    res=cnt_sum[min(len(cnt_sum)-1,2*K+1+i)]-cnt_sum[i]
    ans=max(ans,res)
    
print(ans)

Submission status: Accepted

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

s=input()
s = list(map(int,s))

memo = [0]

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

ans = 0
for i in range(len(memo)):
    start = memo[i]
    if (s[start] == 1):
        end = i + 2*k +1
    else:
        end = i + 2*k
    if end < len(memo):
        end = memo[end]
    else:
        end = len(s)
    ans = max(ans, end-start)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import groupby,accumulate
n,k = map(int,stdin.readline().rstrip().split())
s = stdin.readline().rstrip()
li = []
for key, value in groupby(s):
    li.append((key,len(list(value))))
#とりあえず逆立ちしている人（透明人間含）でサンドイッチしていることにする
if li[0][0] != "1":
    li = [("1",0)]+li
if li[-1][0] != "1":
    li.append(("1",0))
lin = [i[1] for i in li]
if len(lin)//2 < k:
    k = len(lin)//2
lin = [0,0]+list(accumulate(lin))
ma = lin[2]#とりうる最大の人数
for i in range((k+1)*2,len(lin),2):
    ma = max(ma,lin[i]-lin[i-(k+1)*2+1])
print(ma)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()+"w"
A = []
if S[0]=="0":A.append(0)
a,b = 0,""
for s in S:
    if b!="" and b!=s:
        A.append(a)
        a=1
    else:a+=1
    b=s
if S[-2]=="0":A.append(0)
B = [0]
for i in range(len(A)):
    B.append(B[i]+A[i])
ans = 0
N = len(B)
for i in range(2*K+1,N):
    if i%2==0:continue
    ans = max(ans,B[i]-B[i-2*K-1])
print(ans if ans else B[N-1])

Submission status: Accepted

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

T='0'+S+'0'
ans,cnt=0,0
for i,(a,b) in enumerate(zip(S,S[1:])):
  if a=='0' and b=='1':
    cnt+=1
  elif cnt==k and a=='1' and b=='0':
    ans=max(ans,i+1)
    break
else:
  print(n)
  exit()
  
S,cnt=S[::-1],0
for i,(a,b) in enumerate(zip(S,S[1:])):
  if a=='0' and b=='1':
    cnt+=1
  elif cnt==k and a=='1' and b=='0':
    ans=max(ans,i+1)
    break
else:
  print(n)
  exit()
  
x,y=[],[]
for i,(a,b) in enumerate(zip(T,T[1:])):
  if a==b: continue
  if a=='0':
    x.append(i)
  else:
    y.append(i)
for a,b in zip(x,y[k:]):
  ans=max(ans,b-a)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,K = map(int,input().split())
S = input()
stands = []
temp = ''
first_handstand = False
for i,s in enumerate(S):
    if i == 0:
        temp += s
        continue
    if temp[-1] == s:
        temp += s
    else:
        stands.append(len(temp))
        temp = s
stands.append(len(temp)) # 最後の連続列
if S[0] == '0':
    stands.insert(0,0)
if S[-1] == '0':
    stands.append(0)
cumsum_stands = np.cumsum(np.array(stands))
cumsum_stands = np.insert(cumsum_stands,0,0)

ans = 0

for l in range(0,len(cumsum_stands),2):
    r = min(l + 2*K+1,len(cumsum_stands)-1)
    ans = max(ans, cumsum_stands[r] - cumsum_stands[l])
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
s = input()
lis=[]
z_cnt=0
o_cnt=0
for num in s:
    if num=="0":
        z_cnt+=1
        if o_cnt!=0:
            lis.append(o_cnt)
            o_cnt=0
    else:
        o_cnt+=1
        if z_cnt!=0:
            lis.append(z_cnt)
            z_cnt=0
if z_cnt!=0:
    lis.append(z_cnt)
if o_cnt!=0:
    lis.append(o_cnt)

first_zero = s[0]=="0"
if first_zero:
    ind=k*2
    low=-1
else:
    ind=1+k*2
    low=0
sm=0

if ind > len(lis):
    print(sum(lis))
    exit()
for i in range(ind):
    sm+=lis[i]
ans=sm
while True:
    if low ==-1:
        sm-=lis[0]
    else:
        sm-=lis[low+1]+lis[low]
    if ind+1>=len(lis):
        sm+=lis[ind]
    else:
        sm+=lis[ind]+lis[ind+1]
    if sm > ans:
        ans=sm
    ind+=2
    low+=2
    if ind+1>len(lis):
        break
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate as ac

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

l = []
c = 0

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

if S[0]==0:
    l = [0]+l
if S[-1]==0:
    l.append(0)

size = len(l)
*a, = ac([0]+l)
group_size = min(2*K+1,size)

ans = 0
for i in range(group_size, size+1, 2):
    ans = max(ans, a[i]-a[i-group_size])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate as ac

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

l = []
c0, c1 = 0, 0

prev = 0
for i, j  in enumerate(S):
    if i==0:
        if j==0:
            c0 += 1
        else:
            c1 += 1
    else:
        if prev!=j:
            if prev==1:
                l.append(c1)
                c1 = 0
            else:
                l.append(c0)
                c0 = 0
        if j==0:
            c0 += 1
        else:
            c1 += 1
    prev = j

if c0:
    l.append(c0)
if c1:
    l.append(c1)

if S[0]==0:
    l = [0]+l
if S[-1]==0:
    l.append(0)

size = len(l)
accum = list(ac([0]+l))
start = min(2*K+1,size)

ans = 0
for i in range(start, size+1, 2):
    ans = max(ans, accum[i]-accum[i-start])
print(ans)

Submission status: Accepted

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

ZERO, ONE = [], []
now = "1"
count = 0
for c in s:
    if c == now:
        count += 1
    else:
        if now == "0":
            ZERO.append(count)
        else:
            ONE.append(count)
        now = c
        count = 1
ONE.append(count)
ONE[0] -= 1; ONE[-1] -= 1

m = len(ZERO)
if k >= m:
    print(n)
    exit()

answer = temporary = sum(ZERO[:k]) + sum(ONE[:k + 1])
for i in range(m - k):
    temporary += ZERO[i + k] + ONE[i + k + 1]
    temporary -= ZERO[i] + ONE[i]
    answer = max(answer, temporary)

print(answer)

Submission status: Accepted

Solution code:
from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    first=[int(S[i]) for i in range(0,N-num+1)]
    last=[int(S[i+num-1]) for i in range(0,N-num+1)]
    test=[]
    for i in range(0,num):
        test.append(int(S[i]))
    sub=groupby(test)
    count=0
    for key,group in sub:
        if key==0:
            count+=1
    if K>=count:
        flag=1
    for i in range(1,N-num+1):
        if first[i-1]==0 and first[i]==1:
            count-=1
        if last[i-1]==1 and last[i]==0:
            count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

Submission status: Accepted

Solution code:
from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    first=[int(S[i]) for i in range(0,N-num+1)]
    last=[int(S[i+num-1]) for i in range(0,N-num+1)]
    test=[]
    for i in range(0,num):
        test.append(int(S[i]))
    sub=groupby(test)
    count=0
    for key,group in sub:
        if key==0:
            count+=1
    if K>=count:
        flag=1
    for i in range(1,N-num+1):
        if first[i-1]==0 and first[i]==1:
            count-=1
        if last[i-1]==1 and last[i]==0:
            count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

Submission status: Accepted

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

how_many=[]
num=[]

counter=0
for i in range(1,n):
    counter+=1
    if s[i-1]!=s[i]:
        how_many.append(counter)
        num.append(int(s[i-1]))
        counter=0
how_many.append(counter+1)
num.append(int(s[-1]))


ans=0
accumulate=[0]
for i in range(len(how_many)):
    accumulate.append(accumulate[-1]+how_many[i])

for g in range(len(num)):
    l=g
    if num[l]==0:
        r=min(g+2*k,len(num))
    else:
        r=min(g+2*k+1,len(num))
    ans=max(ans,accumulate[r]-accumulate[l])
print(ans)