Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

Constraints

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

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

The length of the string S is N.

Each character of the string S is 0 or 1.

Input

Input is given from Standard Input in the following format:

N K
S

Output

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

Sample Input 1

5 1
00010

Sample Output 1

4

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

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

Sample Input 2

14 2
11101010110011

Sample Output 2

8

Sample Input 3

1 1
1

Sample Output 3

1

No directions are necessary.



Sample input:
5 1
00010


Sample output:
4

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
a = []
for i in range(n):
    if i == 0 or s[i] != s[i - 1]:
        a.append(1)
    else:
        a[len(a) - 1] += 1
for i in range(1, len(a)):
    a[i] += a[i - 1]
cur = int(s[0])
ans = 0
for i in range(len(a)):
    tmp = a[i]
    if cur:
        if i > 2 * m:
            tmp -= a[i - 2 * m - 1]
    else:
        if i > 2 * m - 1:
            tmp -= a[i - 2 * m]
    ans = max(ans, tmp)
    cur = 1 - cur
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

i = 1
seq_cnt = 1
while i != n:
    if s[i] != s[i-1]:
        seq.append(seq_cnt)
        seq_cnt = 1
    else:
        seq_cnt += 1
    i += 1

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

b = [0] + list(itertools.accumulate(seq))

ans = 0
for left in range(0, len(b), 2):
    right = left + 2*k + 1
    if right >= len(b):
        right = len(b)-1

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

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
li=[]
if s[0]=="0":
  a=0
  s.insert(0,"p")
  len_s=len(s)
  for i in range (1,len_s):
    if s[i-1]==s[i]:
      a=a+1
    else:
      li.append(a)
      a=1
  li.append(a)
  if s[n-1]=="0":
    li.append(0)
else:
  a=1
  len_s=len(s)
  for j in range (1,len_s):
    if s[j-1]==s[j]:
      a=a+1
    else:
      li.append(a)
      a=1
  li.append(a)
  if s[n-1]=="0":
    li.append(0)
len_li=len(li)
lis=[0]
t=0
for l in range (0,len_li):
  t=t+li[l]
  lis.append(t)
if 2*k+1>=len_li:
  print(n)
elif k==0:
  import math
  o=math.ceil(len_li/2)
  le=[]
  for f in range (0,o):
    le.append(li[2*f])
    le.sort()
  print(le[len(le)-1])
else:
  import math
  u=0
  w=0
  while w<=len(lis)-2*k-2:
    d=lis[w+2*k+1]-lis[w]
    if u<=d:
      u=d
    w=w+2
  print(u)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
li=[]
if s[0]=="0":
  a=0
  s.insert(0,"p")
  len_s=len(s)
  for i in range (1,len_s):
    if s[i-1]==s[i]:
      a=a+1
    else:
      li.append(a)
      a=1
  li.append(a)
  if s[n-1]=="0":
    li.append(0)
else:
  a=1
  len_s=len(s)
  for j in range (1,len_s):
    if s[j-1]==s[j]:
      a=a+1
    else:
      li.append(a)
      a=1
  li.append(a)
  if s[n-1]=="0":
    li.append(0)
len_li=len(li)
lis=[0]
t=0
for l in range (0,len_li):
  t=t+li[l]
  lis.append(t)
if 2*k+1>=len_li:
  print(n)
elif k==0:
  import math
  o=math.ceil(len_li/2)
  le=[]
  for f in range (0,o):
    le.append(li[2*f])
    le.sort()
  print(le[len(le)-1])
else:
  import math
  u=0
  w=0
  while w<=len(lis)-2*k-2:
    d=lis[w+2*k+1]-lis[w]
    if u<=d:
      u=d
    w=w+2
  print(u)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    s = list(input())
    
    tank = []
    cnt = 1
    for i in range(1, n):
        if s[i] != s[i-1]:
            tank.append(cnt)
            cnt = 0
        cnt += 1
        if i == n-1:
            tank.append(cnt)
            
    p = len(tank)
    
    if s[0] == '0' and (p+1)//2 <= k:
        print(n)
        exit()
    if p//2 <= k and s[0] == '1':
        print(n)
        exit()
        
    ans = 0
    res = 0
    if s[0] == '0':
        for j in range(2*k):
            res += tank[j]
        ans = res
        for j in range(2*k, p):
            if j == 2*k:
                res -= tank[0]
            elif j%2 == 0:
                res = res - tank[j-2*k] - tank[j-2*k-1]
            res += tank[j]
            ans = max(ans, res)
            
    else:
        for j in range(2*k+1):
            res += tank[j]
        ans = res
        for j in range(2*k+1, p):
            if j%2 == 1:
                res = res - tank[j-2*k-1] - tank[j-2*k]
            res += tank[j]
            ans = max(ans, res)
            
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


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

    #tank: '0...0'と'1...1'の塊の数リスト
    #ex. 0001011ならtank = [3,1,1,2] (0が3つ,1が1つ,0が2つ,1が2つ)
    tank = []
    cnt = 1
    for i in range(1,n):
        if s[i] != s[i-1]:
            tank.append(cnt)
            cnt = 0
        cnt += 1
        if i == n-1:
            tank.append(cnt)
    #p:tankの長さ
    p = len(tank)

    #全部1にできてしまう場合
    if s[0] == '0' and (p+1)//2 <= k:
        print(n)
        exit()
    if p//2 <= k and s[0] == '1':
        print(n)
        exit()

    
    ans = 0
    #res:tank[j]が1...1の右端の時の解
    res = 0
    if s[0] == '0':
        for j in range(2*k):
            res += tank[j]
        ans = res
        for j in range(2*k,p):
            if j == 2*k:
                res -= tank[0]
            elif j%2 == 0:
                res= res - tank[j-2*k] -tank[j-2*k-1]
            res += tank[j]
            ans = max(ans,res)

    else:
        for j in range(2*k+1):
            res += tank[j]
        ans = res
        for j in range(2*k+1,p):
            if j % 2 == 1:
                res = res- tank[j-2*k-1]-tank[j-2*k]
            res += tank[j]
            ans = max(ans,res)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

onezero+=[cnt]

x=len(onezero)

if siten=='1':
    onezero+=[onezero[-1]]*2
    t=int(x/2-1)
    if k>=t:
        print(n)
    else:
        ans=[0]
        for i in range(t-k+2):
            ans+=[onezero[2*(i+k)+1]-onezero[2*i]]
        print(max(ans))

else:
    onezero+=[onezero[-1]]
    t=int(x/2)
    if k>=t:
        print(n)
    else:
        ans=[onezero[2*k]]
        for i in range(t-k):
            ans+=[onezero[2*(i+k+1)]-onezero[2*i+1]]
        print(max(ans))

Submission status: Accepted

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

for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(count)
    count += 1
li.append(count)

m = len(li)

if s[0] == '1':
    li.append(li[-1])
    li.append(li[-1])
    t = int(m/2-1)
    if k >= t:
        print(n)
    else:
        max1 = 0
        for i in range(t-k+2):
            max1 = max(li[2*(i+k)+1] - li[2*i],max1)
        print(max1)
else:
    li.append(li[-1])
    t = int(m/2)
    if k >= t:
        print(n)
    else:
        max1 = li[2*k]
        for i in range(t-k):
            max1 = max(li[2*(i+k+1)] - li[2*i+1],max1)
        print(max1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s_list=[]
first=s[0]
last=s[n-1]
state=first
length=1
for i in range(1,n):
    if (state=='0' and s[i]=='0') or (state=='1' and s[i]=='1'):
        state=s[i]
        length=length+1
    else:
        state=s[i]
        s_list.append(length)
        length=1
s_list.append(length)
m=len(s_list)
if first=='0' and last=='0':
    if (len(s_list)+1)/2<=k:
        Max=n
    else:
        p_list=s_list[0:2*k]
        Sum=sum(p_list)
        Max=Sum
        i=1
        p_list=s_list[i:i+2*k+1]
        Sum=sum(p_list)
        if Sum>Max:
            Max=Sum
        i=i+2
        while i+2*k<m-1:
            Sum=Sum-s_list[i-2]-s_list[i-1]+s_list[i+2*k-1]+s_list[i+2*k]
            if Sum>Max:
                Max=Sum
            i=i+2
        p_list=s_list[m-2*k:]
        if sum(p_list)>Max:
            Max=sum(p_list)
elif first=='0' and last=='1':
    if len(s_list)/2<=k:
        Max=n
    else:
        p_list=s_list[0:2*k]
        Sum=sum(p_list)
        Max=Sum
        i=1
        p_list=s_list[i:i+2*k+1]
        Sum=sum(p_list)
        if Sum>Max:
            Max=Sum
        i=i+2
        while i+2*k<=m-1:
            Sum=Sum-s_list[i-2]-s_list[i-1]+s_list[i+2*k-1]+s_list[i+2*k]
            if Sum>Max:
                Max=Sum
            i=i+2
elif first=='1' and last=='0':
    if len(s_list)/2<=k:
        Max=n
    else:
        p_list=s_list[0:2*k+1]
        Sum=sum(p_list)
        Max=Sum
        i=2
        while i+2*k<m-1:
            Sum=Sum-s_list[i-2]-s_list[i-1]+s_list[i+2*k-1]+s_list[i+2*k]
            if Sum>Max:
                Max=Sum
            i=i+2
        p_list=s_list[m-2*k:]
        if sum(p_list)>Max:
            Max=sum(p_list)
elif first=='1' and last=='1':
    if (len(s_list)-1)/2<=k:
        Max=n
    else:
        p_list=s_list[0:2*k+1]
        Sum=sum(p_list)
        Max=Sum
        i=2
        while i+2*k<=m-1:
            Sum=Sum-s_list[i-2]-s_list[i-1]+s_list[i+2*k-1]+s_list[i+2*k]
            if Sum>Max:
                Max=Sum
            i=i+2
print(Max)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = list(input())
s = list((map(int, s)))
tipS = []
cnt = 1
ans = 0
zeroInd = []
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        tipS.append([s[i], cnt])
        cnt = 1
tipS.append([s[-1], cnt])
total_sum = [0] * len(tipS)
total_sum[0] += tipS[0][1]
for i in range(len(tipS)):
    if tipS[i][0] == 0:
        zeroInd.append(i)
    if i != 0:
        total_sum[i] += tipS[i][1] + total_sum[i-1]
if len(zeroInd) != 0:
    start = zeroInd[0]
tmp_cnt = 0
tmp = 0
tmp2 = 0
before = 0
#print(total_sum)
for i in range(len(tipS)):

    if tipS[i][0] == 0:
        tmp_cnt += 1


        if tmp_cnt > k:
            ans = max(tmp, ans)
            #print("ans: {}".format(ans))
            tmp -= (total_sum[start] - before)
            before = total_sum[start]
            #print("minus{}".format(tmp))
            tmp += tipS[i][1]
            tmp_cnt -= 1
            tmp2 += 1
            start = zeroInd[tmp2]

        else:
            tmp += tipS[i][1]


    else:
        tmp += tipS[i][1]
    #print("tmp_cnt: {}".format(tmp_cnt))
    #print("tmp: {}".format(tmp))

ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
class BufInput:
  def __init__(self):
    self.save = False
    self.buf = None
  def read(self, save=False):
    if self.save:
      ret = self.buf
    else:
      try:
        ret = input()
      except EOFError as e:
      	ret = None
    self.save = save
    self.buf = ret
    return ret
    
  
bi = BufInput()
while bi.read(True):
  n, k = map(int, bi.read().split())
  s = bi.read().rstrip()

  def findEx(s, f, pos, notfound):
    pos = s.find(f, pos)
    if pos == -1:
      pos = notfound
    return pos

  ans = 0
  left = 0
  right = 0
  while right < n:
      if k > 0:
          right = findEx(s, '01', right, n-1) + 1
          k = k - 1
          right = findEx(s, '10', right, n-1) + 1
          ans = max(ans, right - left)
      else:
          left = findEx(s, '01', left, n-1) + 1
          k = k + 1

  print(ans)

Submission status: Accepted

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

def findEx(s, f, pos, notfound):
  pos = s.find(f, pos)
  if pos == -1:
    pos = notfound
  return pos
    
ans = 0
left = 0
right = 0
while right < n:
    if k > 0:
        right = findEx(s, '01', right, n-1) + 1
        k = k - 1
        right = findEx(s, '10', right, n-1) + 1
        ans = max(ans, right - left)
    else:
        left = findEx(s, '01', left, n-1) + 1
        k = k + 1

print(ans)

Submission status: Accepted

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

memo = [0]
run = 0
turn = '1'

for s in S:

    if s == turn:
        run += 1
    else:
        turn = s
        memo.append(run)
        run = 1

memo.append(run)
if turn == '0':
    memo.append(0)


if len(memo) > K*2+1:
    memo = list(accumulate(memo))
    res = max(x-y for x,y in zip(memo[K*2+1::2], memo[:-(K*2+1):2]))
else:
    res = N
print(res)

Submission status: Accepted

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

L = [0]
R = []
for i in range(0, len(S) - 1):
    if S[i:i + 2] == "01":
        L.append(i + 1)
j = 0
while j < len(S) and S[j] == '1':
    j += 1
for i in range(j, len(S) - 1):
    if S[i:i + 2] == "10":
        R.append(i)
R.append(len(S) - 1)

ans = 0
z = min(len(L) - K, len(R) - K)
if z <= 0:
    ans = len(S)

for i in range(z + 1):
    Ri = max(0, i + K - 1)
    d = R[Ri] - L[i] + 1
    # print("(l,r)=({},{}) : {}".format(L[i], R[Ri], d))
    ans = max(ans, d)

# print(L)
# print(R)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = input().rstrip()
ans = 1
i = 0
left = 0
right = 1
while i < n:
    if k > 0:
        pos = s.find('01', i)
        if pos == -1:
            i = n
            right = n - 1
        else:
            pos = s.find('10', pos + 1)
            if pos == -1:
                i = n
                right = n - 1
            else:
                right = pos
                i = pos + 1
        k = k - 1
        ans = max(ans, right - left + 1)
    else:
        pos = s.find('01', left)
        left = pos + 1
        k = k + 1

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
k += 1
s = "01" + input().rstrip()
n += 2
ans = 0
i = 0
left = 2
right = 1
while i < n:
    if k > 0:
        pos = s.find('01', i)
        if pos == -1:
            i = n
            right = n - 1
        else:
            pos = s.find('10', pos + 1)
            if pos == -1:
                i = n
                right = n - 1
            else:
                right = pos
                i = pos + 1
        k = k - 1
        ans = max(ans, right - left + 1)
    else:
        pos = s.find('01', left)
        left = pos + 1
        k = k + 1

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
starts = []
idx = 0
while idx < len(S):
    starts.append(idx)
    while idx < len(S) and S[starts[-1]] == S[idx]:
        idx += 1
starts.append(len(S))
ans = 0
for i, start in enumerate(starts[:-1]):
    if S[start] == '0':
        stop = starts[min(len(starts) - 1, i + 2 * K)]
    else:
        stop = starts[min(len(starts) - 1, i + 2 * K + 1)]
    ans = max(ans, stop - start)
print(ans)

Submission status: Accepted

Solution code:
def solve(N, K, S):
    max_len = 0
    change_sum = 0
    start = 0
    end = 0

    while 1:
        if end == 0:
            if S[end] == '0':
                change_sum = change_sum + 1

        # 切り替え総数がK以下ならこの区間はOK
        if change_sum <= K:
            if max_len < end - start + 1:
                max_len = end - start + 1
            end = end + 1
            # Sの最後までたどり着いたら終了
            if end >= len(S):
                break
            if S[end - 1] == '1' and S[end] == '0':
                change_sum = change_sum + 1
        else:
            start = start + 1
            if start >= len(S):
                break
            if S[start - 1] == '0' and S[start] == '1':
                change_sum = change_sum - 1

        #print(start, end, change_sum, max_len)

    return max_len

input_line = input().rstrip().split(' ')
N = int(input_line[0])
K = int(input_line[1])
S = input()

print(solve(N, K, S))

Submission status: Accepted

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

# 累積和で実装

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

# print(nums)

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

# print(cumulative_sum)

ans = 0
start = 0
final = 2 * K
answers = []

# M = len(nums) = len(cumulative_sum)
# if M < 2 * K + 1:
#     print(len(S))
# else:
if final <= M-1:
    while(final <= M-1):
        if start == 0:
            answers.append(cumulative_sum[final])
        else:
            ans = cumulative_sum[final] - cumulative_sum[start-1]
            answers.append(ans)

        # print(start, final, ans)
        start += 2
        final += 2
    print(max(answers))
else:
    print(cumulative_sum[-1])

# print(answers)

Submission status: Accepted

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

# 累積和で実装

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

# print(nums)

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

# print(cumulative_sum)

ans = 0
start = 0
final = 2 * K
answers = []

# M = len(nums) = len(cumulative_sum)
if M < 2 * K + 1:
    print(len(S))
    exit()
if final <= M-1:
    while(final <= M-1):
        if start == 0:
            answers.append(cumulative_sum[final])
        else:
            ans = cumulative_sum[final] - cumulative_sum[start-1]
            answers.append(ans)

        # print(start, final, ans)
        start += 2
        final += 2
    print(max(answers))
else:
    print(cumulative_sum[0])

# print(answers)

Submission status: Accepted

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

S=input()

left = 0
right = 0

max_len = N

count0 =0
henka = 0
first = int(S[0])
for i in range(1,N):
    if S[i-1]!=S[i]:
        henka +=1
    if S[i]=='0'and henka == (2*K+first):
        right = i-1
        max_len = i
        break

    


# print(max_len)  
right_count = 3
left_count = 3

while(1):
    # print(left,right)
    if right_count <= 2: break
    if max_len == N:break
    #３変化する前までrightを動かす
    right_count = 0
    while(1):
        if right+1 >= N: break
        if S[right+1] !=  S[right]:
            right_count += 1
        if right_count >2 : break
        right += 1
    left_count = 0
    #leftを動かす
     
    if S[left] =='0':
        left_count = 1
    else:
        left_count = 0
    while(1):
        if right_count == 0:break
        if S[left+1] !=  S[left]:
            left_count += 1
        left += 1
        if left_count >1 : break
        
    

    
    max_len = max(right-left+1,max_len)

print(max_len)

Submission status: Accepted

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

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)

Submission status: Accepted

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

c = [0]
import itertools
for _, g in itertools.groupby(s):
  c.append(c[-1] + len(list(g)))
  
c = c[1:]
if s[0] == "1":
  c = [0] + c
else:
  c = [0,0] + c
if s[-1] == "0":
  c = c + [c[-1]]

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

print(ans)

Submission status: Accepted

Solution code:
import re

input_str=input()
N=int(input_str.split()[0])
K=int(input_str.split()[1])
str_teams = str(input())
sub_str_teams = str_teams

def next_check_val(check_val):
  if check_val == '1':
    return '0'
  else:
    return '1'

cur_check_val = str_teams[0]
teams_group = []
teams_state = ''

## 直立/逆立ちのグループに分ける処理
for i in range(N):
  person = str_teams[i]
  if str_teams[i] == cur_check_val:
    teams_state = teams_state + str_teams[i]
  else:
    teams_group.append(teams_state)
    teams_state = str_teams[i]
    cur_check_val = next_check_val(cur_check_val)

teams_group.append(teams_state)
#print(teams_group)

## 0グループの個数がK以下の場合
## 人数を回答にしてexitする
count_0 = 0
for i in range(len(teams_group)):
  if teams_group[i].startswith('0'):
    count_0 += 1
if count_0 <= K:
  print(N)
  exit()

sum_handstand = [] ## 累積和を格納するリスト
handstands = 0     ## 各累積和を一時的に格納する変数


## 最初の累積和を計算する処理
## 先頭が0か1かによって処理を分割している
if ('0' in teams_group[0]):
  for k in range(K*2):
    handstands += len(teams_group[k])
else:
  for k in range(K*2+1):
    handstands += len(teams_group[k])

sum_handstand.append(handstands)

## 途中の累積和を計算する処理
for i in range(1,len(teams_group)-(K*2)):
  ## 先頭が0か1かによって処理を分割している
  if ('0' in teams_group[i]):
    handstands = sum_handstand[i-1]
  else:
    if i == 1:
      handstands = sum_handstand[i-1] - len(teams_group[i-1]) + (len(teams_group[i+2*K-1])+len(teams_group[i+2*K]))
    else:
      handstands = sum_handstand[i-1] - (len(teams_group[i-1])+len(teams_group[i-2])) + (len(teams_group[i+2*K-1])+len(teams_group[i+2*K]))
  sum_handstand.append(handstands)

handstands = 0
## 最後の累積和を計算する処理
if ('0' in teams_group[-1]):
  for k in range(0,K*2):
    handstands += len(teams_group[len(teams_group)-2*K+k])
  sum_handstand.append(handstands)


#print(sum_handstand)
print(max(sum_handstand))

Submission status: Accepted

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

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

add = 2 * K + 1

sum = [0] * (len(nums)+1)

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

print(ans)

Submission status: Accepted

Solution code:

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

a = []
cnt_one = 0
cnt_zero = 0

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

for i in s:
    if i == "1":
        cnt_one += + 1
        if cnt_zero != 0:
            a.append(cnt_zero)
            cnt_zero = 0
    else:
        cnt_zero += 1
        if cnt_one != 0:
            a.append(cnt_one)
            cnt_one = 0

a.append(max(cnt_zero, cnt_one))

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

n = len(a)
right = 2 * k + 1
up = sum(a[:right])
max_up = up

for i in range((n - right) // 2):
    new_up = up + a[right + i * 2] + a[right + i * 2 + 1] - a[i * 2] - a[i * 2 + 1]
    max_up = max(max_up, new_up)
    up = new_up

print(max_up)

Submission status: Accepted

Solution code:
import math
 
N,K = (int(x) for x in input().split())
S = input()
 
list1 = []
now = 1
count = 0
 
for i in range(N):
    if now == int(S[i]):
        count += 1
    else:
        list1.append(count)
        now = 1-now
        count = 1
else:
    list1.append(count)

if len(list1) % 2 == 0:
    list1.append(0)
 
tmp=0
left=0
right=0
ans=0
for i in range(0,len(list1),2):
    nextleft = i
    while left<nextleft:
        tmp = tmp - list1[left]
        left = left + 1
 
    nextright = min(i+2*K+1,len(list1))
    while right<nextright:
        tmp = tmp + list1[right]
        right = right + 1

    ans=max(ans,tmp)

print(ans)

Submission status: Accepted

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

l = [0]
ans = 0

for i in range(1, n):
  if s[i-1]=="1" and s[i]=="0":
    l.append(i)
  if s[i-1]=="0" and s[i]=="1":
    l.append(i)

for i, e in enumerate(l):
  if s[e]=="0":
    if i+2*k>=len(l):
      ans = max(ans, n-e)
    else:
      ans = max(ans, l[i+2*k]-e)
  else:
    if i+2*k+1>=len(l):
      ans = max(ans, n-e)
    else:
      ans = max(ans, l[i+2*k+1]-e)
print(ans)

Submission status: Accepted

Solution code:
def func():
    N,K = map(int,input().split())
    S = input()
    L = []
    L.append(0) if S[0] == '0' else 0
    num = '2'
    for i in range(N):
        if num != S[i]:
            L.append(i)
            num = S[i]
    L.append(N)
    L.append(N)
    ans = 0
    for i in range(0,len(L)-K*2-1,2):
        ans = max(ans,L[i+K*2+1]-L[i])
    return N if N < 3 or K >= len(L)//2 else ans
print(func())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    nums = []
    now = 1
    cnt = 0
    for s in S:
        if int(s) == now:
            cnt += 1
        else:
            nums.append(cnt)
            now ^= 1
            cnt = 1
    if cnt > 0:
        nums.append(cnt)
    if len(nums) % 2 == 0:
        nums.append(0)
    add = 2 * K + 1
    sum = [0 for _ in range(len(nums) + 1)]
    for i in range(len(nums)):
        sum[i + 1] = sum[i] + nums[i]
    ans = 0
    for cnt in range(0, len(nums), 2):
        left = cnt
        right = min(cnt + add, len(nums))
        tmp = sum[right] - sum[left]
        ans = max(tmp, ans)
    print(ans)


main()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    nums = []
    now = 1
    cnt = 0
    for s in S:
        if int(s) == now:
            cnt += 1
        else:
            nums.append(cnt)
            now ^= 1
            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 cnt in range(0, len(nums), 2):
        nleft = cnt
        nright = min(cnt + add, len(nums))
        while nleft > left:
            tmp -= nums[left]
            left += 1
        while nright > right:
            tmp += nums[right]
            right += 1
        ans = max(tmp, ans)
    print(ans)


main()

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
s = input()
s = list(map(int, s))

v = []
now = 1  # 現在見ている数
cnt = 0  # nowが並ぶ数
for ss in s:
    if ss == now:
        cnt += 1
    else:
        v.append(cnt)
        now = 1 - now  # 0と1を切り替える計算 now ^= 1
        cnt = 1  # ss分を計上
if cnt > 0:
    v.append(cnt)
# 1-0-1-0-1-0-1のように
# 1で終わる配列が欲しい
# 1-0-1-0のように0で終わっていたら、1を足す

# ※1の人数-0の人数-...の配列

if len(v) % 2 == 0: v.append(0)
# 1が0個という項を追加して、
# 1-0-1-0-1にする

c_sum = [0] + list(accumulate(v))
# accumulate:=[1項目, 1,2項目の和, ...]

# 1-0-1-...の1から始めるので、偶数番目だけ見る
lv = len(v)
# [left, right)
ans = 0
for i in range(0, lv, 2):
    left = i
    right = min(2 * K + 1 + i, lv)
    ans = max(c_sum[right] - c_sum[left], ans)

print(ans)

# 累積和

# forループの外側にleft, rightを持つ
# 次のleft, rightを計算する
# 左端を移動する
# 右端を移動する

Submission status: Accepted

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

v = []
now = 1  # 現在見ている数
cnt = 0  # nowが並ぶ数
for ss in s:
    if ss == now:
        cnt += 1
    else:
        v.append(cnt)
        now = 1 - now  # 0と1を切り替える計算 now ^= 1
        cnt = 1  # ss分を計上
if cnt > 0:
    v.append(cnt)
# 1-0-1-0-1-0-1のように
# 1で終わる配列が欲しい
# 1-0-1-0のように0で終わっていたら、1を足す

# ※1の人数-0の人数-...の配列

if len(v) % 2 == 0: v.append(0)
# 1が0個という項を追加して、
# 1-0-1-0-1にする


# 1-0-1-...の1から始めるので、偶数番目だけ見る
lv = len(v)
left, right = 0, 0
# [left, right)
ans = 0
cur_total = 0
for i in range(0, lv, 2):
    nextLeft = i
    nextRight = min(2 * K + 1 + i, lv)
    while left < nextLeft:
        cur_total -= v[left]
        left += 1
    while right < nextRight:
        cur_total += v[right]
        right += 1
    ans = max(cur_total, ans)

print(ans)

Submission status: Accepted

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

v = []
now = 1  # 現在見ている数
cnt = 0  # nowが並ぶ数
for ss in s:
    if ss == now:
        cnt += 1
    else:
        v.append(cnt)
        now = 1 - now  # 0と1を切り替える計算 now ^= 1
        cnt = 1  # ss分を計上
if cnt > 0:
    v.append(cnt)
# 1-0-1-0-1-0-1のように
# 1で終わる配列が欲しい
# 1-0-1-0のように0で終わっていたら、1を足す

# ※1の人数-0の人数-...の配列

if len(v) % 2 == 0: v.append(0)
# 1が0個という項を追加して、
# 1-0-1-0-1にする

add = 2 * K + 1

c_sum = [0]
for vv in v:
    c_sum.append(c_sum[-1] + vv)
# print(v, c_sum)

# 1-0-1-...の1から始めるので、偶数番目だけ見る
lv = len(v)
ans = 0
for i in range(0, lv, 2):
    ans = max(ans, c_sum[min(lv, 2 * K + 1 + i)] - c_sum[i])
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
s = input()
S = [int(x) for x in list(str(s))]

l = []
tmp = 1
p = S[0]

for i in range(1, N):
    if p == S[i]:
        tmp += 1
    else:
        l.append(tmp)
        p = S[i]
        tmp = 1
l.append(tmp)

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

i = 0
check = False

if S[0] == 0:
    r = 2 * K - 1
    check = True
else:
    r = 2 * K

ans = sum(l[i:r + 1])
tmp = ans

while r < len(l) - 2:
    tmp += l[r + 1] + l[r + 2]
    r += 2
    if check:
        tmp -= l[i]
        i += 1
        check = False
    else:
        tmp -= l[i] + l[i + 1]
        i += 2
    ans = max(tmp, ans)

if S[-1] == 0:
    tmp += l[r + 1]
    if check:
        tmp -= l[i]
    else:
        tmp -= l[i] + l[i + 1]

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

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []

for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
right = 0
left = 0
g = 0
su = 0
if A[0] == 0:
    for i in range(len(s)):
        su +=s[right]
        if right%2==0:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==0:
                  g -=1
              left +=1
        a = max(a,su)
else:
    for i in range(len(s)):
        su +=s[right]
        if right%2==1:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==1:
                  g -=1
              left +=1
        a = max(a,su)

print(a)

Submission status: Accepted

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

a = [0]

ls = s.replace('10', '1,0')
ls = ls.replace('01', '0,1')
ls = ls.split(',')
for i in ls:
    a.append(a[-1] + len(i))

ans = 0
res = 0
if s[0] == '1':
    for i in range(len(a)):
        if i % 2 == 0:
            ans = a[min(i + 2 * k + 1, len(a) - 1)] - a[i]
        else:
            ans = a[min(i + 2 * k, len(a) - 1)] - a[i]

        res = max(res, ans)

else:
    for i in range(len(a)):
        if i % 2 == 0:
            ans = a[min(i + 2 * k, len(a) - 1)] - a[i]
        else:
            ans = a[min(i + 2 * k + 1, len(a) - 1)] - a[i]

        res = max(res, ans)

print(res)