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:
def solve():
  n,k = (int(i) for i in input().split())
  s = input()
  one = []
  zero = []  
  for i in range(n):
    if i == 0:
      if s[i] == "0":
        one.append(0)
        zero.append(1)
      else:
        one.append(1)
    
    else:     
     if s[i] == s[i-1]:
      if s[i] == "0":
        zero[-1]+= 1
      else:
        one[-1] += 1
     else:
      if s[i] == "0":
        zero.append(1)
      else:
        one.append(1)
  ans = 0 
  if len(zero) <= k:
    ans = n

  else:
   one = one + [0]*5
   zero = zero + [0]*5
   tmp = 0
   for i in range(k+1):
    tmp += one[i]
   for i in range(k):
    tmp += zero[i]
   ans = max(tmp,ans)
   for i in range(len(zero)-k-1):
        
       tmp -=  one[i]
       tmp +=  one[i+k+1]
       tmp -=  zero[i]
       tmp +=  zero[i+k]
       ans = max(ans,tmp)

  #print (one) 
 # print(zero)
  print(ans)
    
solve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
S = list(map(int, input()))
T = []    
if S[0] == 1:
    T.append(1)
else:
    T.append(0)
    T.append(-1)
for i in range(1, n):
    if S[i] == S[i-1] and S[i] == 1:
        T[-1] += 1
    elif S[i] == S[i-1]:
        T[-1] -= 1
    elif S[i] == 1:
        T.append(1)
    else:
        T.append(-1)
if T[-1] < 0:
    T.append(0)
m = len(T)

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

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
L = []
cur = S[0]
cnt = 0
if S[len(S)-1] == '1':
  S += '0'
else:
  S += '1'
for i in range(len(S)):
  if S[i] == cur:
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
    cur = S[i]
ruiseki = [L[0]]
for i in range(len(L)-1):
  ruiseki.append(ruiseki[i]+L[i+1])
ruiseki.insert(0,0)
if len(ruiseki) == 2:
  print(len(S)-1)
else:
  if S[0] == '1' and S[len(S)-2] == '1':
    if (len(L)-1)/2 > K:
      ans = 0
      for i in range(len(ruiseki)-2*K-1):
        if i%2 == 0:
          if ans <= ruiseki[i+2*K+1]-ruiseki[i]:
            ans = ruiseki[i+2*K+1]-ruiseki[i]
      print(ans)
    else:
      print(len(S)-1)
  elif S[0] == '1' and S[len(S)-2] == '0':
    if len(L)/2 > K:
      ans = 0
      for i in range(len(ruiseki)-2*K-2):
        if i%2 == 0:
          if ans <= ruiseki[i+2*K+1]-ruiseki[i]:
            ans = ruiseki[i+2*K+1]-ruiseki[i]
      print(max(ans,ruiseki[len(ruiseki)-1]-ruiseki[len(ruiseki)-1-2*K]))
    else:
      print(len(S)-1)
  elif S[0] == '0' and S[len(S)-2] == '1':
    if len(L)/2 > K:
      ans = 0
      for i in range(1,len(ruiseki)-2*K):
        if i%2 != 0:
          if ans <= ruiseki[i+2*K+1]-ruiseki[i]:
            ans = ruiseki[i+2*K+1]-ruiseki[i]
      print(max(ans,ruiseki[2*K]-ruiseki[0]))
    else:
      print(len(S)-1)
  else:
    ans = 0
    if (len(L)+1)/2 > K:
      for i in range(len(ruiseki)-2*K-3):
        if i%2 != 0:
          if ans <= ruiseki[i+2*K+1]-ruiseki[i]:
            ans = ruiseki[i+2*K+1]-ruiseki[i]
      print(max(ans,ruiseki[2*K]-ruiseki[0],ruiseki[len(ruiseki)-1]-ruiseki[len(ruiseki)-1-2*K]))
    else:
      print(len(S)-1)

Submission status: Accepted

Solution code:
n, k = [int(_) for _ in input().split()]
s = input()
x = []

cnt = 0
c0 = '1'
for c in s:
    if c == c0:
        cnt += 1
    else:
        x.append(cnt)
        c0 = c
        cnt = 1
else:
    if cnt != 0:
        x.append(cnt)

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

if len(x) <= k*2+1:
    print(sum(x))
else:
    y = sum(x[0:k*2+1])
    ans = y
    for i in range(2,len(x)-k*2,2):
        y = y - sum(x[i-2:i]) + sum(x[i+2*k-1:i+2*k+1])
        if ans < y:
            ans = y
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = list(input())
current = S[0]
L0 = []
L1 = []
Lall = []
stack = 0
for i in range(N):
    if current == S[i]:
        stack += 1
    else:
        if current == '0':
            L0.append(stack)
        else:
            L1.append(stack)
        Lall.append(stack)
        stack = 1
        current = S[i]
if current == '0':
    L0.append(stack)
else:
    L1.append(stack)
Lall.append(stack)
len0 = len(L0)
len1 = len(L1)
if len0 == 0:
    print(L1[0])
elif len1 == 0:
    if K != 0:
        print(L0[0])
    else:
        print(0)
elif len0 <= K:
    print(len(S))
else:
    L = [0]
    for i in range(len(Lall)):
        L.append(L[-1] + Lall[i])
    if len0 < len1:
        ans = 0
        for k in range(len0-K+1):
            ans = max(ans, L[2*k + 2*K + 1]-L[2*k])
    elif len0 > len1:
        ans = max(L[2*K]-L[0], L[-1]-L[-1-2*K])
        for k in range(len0-K-1):
            ans = max(ans, L[2*k + 2*K + 2]-L[2*k + 1])
    elif S[0] == '0':
        ans = L[2*K]-L[0]
        for k in range(len0 - K):
            ans = max(ans, L[2*k + 2*K + 2]-L[2*k + 1])
    else:
        ans = L[-1]-L[-1-2*K]
        for k in range(len0 - K):
            ans = max(ans, L[2 * k + 2 * K + 1] - L[2 * k])
    print(ans)

Submission status: Accepted

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

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

n0 = (len(seq) - 1) // 2
if n0 <= K:
    ans = N
else:
    total = [0]
    for s in seq:
        total.append(total[-1] + int(s))

    ans = 0
    for i in range(n0 - K + 1):
        ans = max(ans, total[(i + K) * 2 + 1] - total[i * 2])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,K=map(int,input().split())
S=input()
zeros=deque()
ichistart=0
zeros.append([-1,-1])
streak=0#0が何人連続した塊なのか
hajime=0
for k,i in enumerate(S):
    if i=="0":
        if streak==0:
            hajime=k
        streak+=1
    elif streak!=0:
        owari=hajime+streak-1
        streak=0
        zeros.append([hajime,owari])
if streak!=0:
    zeros.append([hajime,N-1])
zeros.append([N,N])
curmax=0
done=0
z=len(zeros)
if z<=K+1:
    print(N)
    done=1
if not done:
    for n,[s,f] in enumerate(zeros):
        if n+K+1<z:
            curmax=max(curmax,zeros[n+K+1][0]-f-1)
    print(curmax)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = input()
split_list = [0]
section_list = [0]
for i in range(1, N):
    if S[i-1] != S[i]:
        section_list.append(i - split_list[-1])
        split_list.append(i)
split_list.append(N)
section_list.append(split_list[-1] - split_list[-2])
del split_list[0]
del section_list[0]
answer = 0
if len(section_list) <= 2 * K:
    answer= N
else:
    total = sum(section_list[:2 * K + 1])
    if S[0] == '0':
        for i in range(len(section_list) - 2 * K - 1):
            total = total - section_list[i] + section_list[i+2*K+1]
            if i % 2 == 0:
                if total >= answer:
                    answer = total
    if S[0] == '1':
        answer = total
        for i in range(len(section_list) - 2 * K - 1):
            total = total - section_list[i] + section_list[i+2*K+1]
            if i % 2 == 1:
                if total >= answer:
                    answer = total
    # 0から始まるパターン
    total = sum(section_list[:2 * K])
    if total > answer:
        answer = total
    #0で終わるパターン
    total = sum(section_list[- 2 * K:])
    if total > answer:
        answer = total
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
S = input()
c0, c1 = [], []
if S[0] == '1':
    c0.append(0)
i = 0
while i < N:
    p = S[i]
    c = 1
    i += 1
    while i < N and S[i] == p:
        i += 1
        c += 1
    if p == '0':
        c0.append(c)
    else:
        c1.append(c)
if S[N-1] == '0':
    c1.append(0)
l0 = len(c0)
if l0 < K:
    K = l0
ans = sum(c0[0:K]) + sum(c1[0:K])
for i in range(1, l0):
    c0[i] += c0[i-1]
    c1[i] += c1[i-1]
l = l0 - K + 1
if l0 == 2 and S[0] == '1':
    ans = N
else:
    for i in range(1, l):
        tmp = c0[i+K-1] - c0[i-1] + c1[i+K-1]
        if i - 2 >= 0:
            tmp -= c1[i-2]
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
instr=input()
lft=0
rgt=1
voids=0 if instr[0] == '1' else 1

rlast='1' if instr[0] == '1' else '0'
llast='1' if instr[0] == '1' else '0'
maxlen=0
while lft < rgt:
    # print("lft {} rgt {} maxlen {} void {} {}".format(lft, rgt, maxlen, voids, instr[lft:rgt]))
    if voids <= K and rgt < N:
        maxlen = max(maxlen, rgt-lft)
        if instr[rgt-1] == '1' and instr[rgt] == '0':
            voids+=1
            rlast = '0'
        rlast = instr[rgt-1]
        rgt += 1
    else:
        if (voids <= K):
            maxlen = max(maxlen, rgt-lft)
        llast = instr[lft]
        if lft+1 < N and instr[lft] == '0' and instr[lft+1] == '1':
            voids -= 1
        lft += 1

print(maxlen)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
next = 0
l = []
ans = 0
if s[0]=='0':
    cnt=1
else:
    cnt = 0
for i in range(1,n):
    if s[i]=='0' and s[i-1]=='1':
        cnt += 1
    if s[i]=='1' and s[i-1]=='0':
        l.insert(0,i)
    if s[i]=='0' and s[i-1]=='1' and cnt==k+1:
        ans = max(ans,i-next)
        next = l.pop()
        cnt -= 1
    if i==n-1 and s[i]=='1':
        ans = max(ans,i+1-next)
    if i==n-1 and s[i]=='0':
        ans = max(ans,i+1-next)
if ans==0:
    print(n)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,K = (int(x) for x in input().split())
S = list(input())
size = [1]
memo = S[0]
for i in range(1,N):
    if S[i] == memo:
        size[-1] += 1
    else:
        memo = S[i]
        size += [1]

if S[0] == '0':
    size = [0] + size
if S[-1] == '0':
    size += [0]

if int((len(size)-1)/2) <= K:
    print(N)
else:
    ans = sum(size[0:K*2+1])
    a = ans
    for i in range(2,len(size)-(K*2))[::2]:
        a = a - (size[i-2] + size[i-1]) + (size[i+K*2-1] + size[i+K*2])
        if ans < a:
            ans = a
    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=input()
s_dimlist=[s[i+1]==s[i] for i in range(n-1)]
s_seqcnt=[]
if s[0]=='0':
    s_seqcnt.append(0)
pre=-1
for i in range(n-1):
    if not s_dimlist[i]:
        s_seqcnt.append(i-pre)
        pre=i
s_seqcnt.append(n-1-pre)
if s[n-1]=='0':
    s_seqcnt.append(0)
# print(s_dimlist)
# print(s_seqcnt)
width=2*k+1
length=len(s_seqcnt)
s_sum=[0 for i in range(length//2+length%2)]
s_ruiseki=[0 for i in range(length+1)]
s_ruiseki[0]=0
s_ruiseki[1]=s_seqcnt[0]
for i in range(1,length):
    s_ruiseki[i+1]=s_seqcnt[i]+s_ruiseki[i]
# print(s_ruiseki)
for i in range(length//2+length%2):
    num=0
    if 2*i+width-1>=length:
        s_sum[i]=s_ruiseki[length]-s_ruiseki[2*i]
        break
    else:
        s_sum[i]=s_ruiseki[2*i+width]-s_ruiseki[2*i]
# print(s_sum)
print(max(s_sum))

Submission status: Accepted

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

Submission status: Accepted

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

Z =[]
last=1
cnt =0
n = len(S)

for i,s in enumerate(S):
    if s =="0" and i==n-1:
        if last==0:
            right = i
            Z.append((left, right))
            cnt += 1    #else:
        else:
            Z.append((i,i))
            cnt += 1
    elif last==1 and s=="0":
        left = i
        last = 0
    elif last==0 and s =="1":
        right = i-1
        last  = 1
        Z.append((left, right))
        cnt += 1

    #    pass

#print(cnt)
#print(n)

if K>=cnt:
    print(N)
else:
    #n=len(Z)
    len_z=len(Z)
    rem = cnt - K
    #print(n)
    #print(rem)
    kouho = []
    _, right = Z[rem-1]
    kouho.append(n-1-right)

    left, _ =Z[len_z-rem]
    kouho.append(left)

    for i in range(rem-1):
        L = Z[i]
        R = Z[len_z-rem+i+1]
        _,right = L
        left,_  = R
        kouho.append(left-right-1)

    print(max(kouho))

Submission status: Accepted

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

sentous = []
sentou = 0
max_count = 0
count = 0
prev = '1'
for s in S:
    count += 1
    sentou += 1
    if s != prev and s == '1':
        sentous.append(sentou - 1)
        sentou = 1
    elif s != prev and s == '0':
        if K > 0:
            K -= 1
        else:
            if count - 1 > max_count:
                max_count = count - 1
            count -= sentous.pop(0)
    prev = s

print(max(max_count, count))

Submission status: Accepted

Solution code:
from numpy import cumsum
N, K = map(int, input().split())
S = input()
*S, = map(int, list(S))
zeros = [0]
ones = [0]
if S[0] == 0:
    ones.append(0)
cnt = 1
now = S[0]
for i in range(1, N):
    if now == S[i]:
        cnt += 1
    else:
        if now == 0:
            zeros.append(cnt)
        else:
            ones.append(cnt)
        cnt = 1
        now = S[i]
if now == 0:
    zeros.append(cnt)
else:
    ones.append(cnt)
if S[-1] == 0:
    ones.append(0)

c_zero = cumsum(zeros)
c_one = cumsum(ones)
# print(zeros)
# print(c_zero)
# print(c_one)
if len(zeros) <= K:
    print(len(S))
else:
    ans = 0
    for i in range(0, len(zeros) - K):
        #print(i, K)
        #print(c_zero[i+K]-c_zero[i], c_one[i+K+1]-c_one[i])
        aaa = c_zero[i+K]-c_zero[i] + c_one[i+K+1]-c_one[i]
        #aaa = sum(zeros[i:i + K]) + sum(ones[i:i + K])+ones[i+K]
        # if (S[-1] != 0 and i == saigo)or (S[0] != 0 and i == 0):
        #aaa += ones[i+K]
        ans = max(aaa, ans)
    print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
S = input()
secheadinds = []
secendinds = []
prevone = True
onehead = 0
for ind, si in enumerate(S):
    if prevone == False and si == "1":
        prevone = True
        onehead = ind
    if prevone == True and si == "0":
        secheadinds += [ onehead ]
        secendinds += [ ind - 1 ]
        prevone = False
secendinds += [N-1]

if len(secheadinds) <= K:
    print(N)
else:
    ret = 0
    for ind in range(len(secheadinds) - K + 1):
        seclen = secendinds[ind+K]-secheadinds[ind] + 1
        ret = max(ret,seclen)
    print(ret)

Submission status: Accepted

Solution code:
import numpy as np

n, k = [int(x) for x in input().split()]
s = input()

zero_list = np.array([len(x) for x in s.split("1") if len(x) > 0])
one_list = np.array([len(x) for x in s.split("0") if len(x) > 0])

if k >= len(zero_list):
    print(len(s))
else:
    max_num = 0

    if len(zero_list) < len(one_list):
        for i in range(len(zero_list) - k + 1):
            tmp = zero_list[i:i+k].sum() + one_list[i:i+k+1].sum()
            if tmp > max_num:
                max_num = tmp
    else:
        if len(zero_list) == len(one_list) and int(s[0]) == 1:
            zero_list = np.insert(zero_list, 0, 0)
        max_num = zero_list[:k].sum() + one_list[:k].sum()
        for i in range(len(one_list) - k):
            tmp = zero_list[i+1:i+k+1].sum() + one_list[i:i+k+1].sum()
            if tmp > max_num:
                max_num = tmp
        tmp = zero_list[-k:].sum() + one_list[-k:].sum()
        if tmp > max_num:
            max_num = tmp

    print(max_num)

Submission status: Accepted

Solution code:
from sys import stdin
# import math
import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]
N, K = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip().split()[0]

B = [0]
count = 0
oz = 1
for s in S:
  if int(s) == oz:
    count+=1
  else:
    B.append(count)
    count=1
    oz=int(s)
B.append(count)
if oz==0:
  B.append(0)
# print(B)
L = len(B)-1
if 2*K+1>L:
  K = int(L/2)
# print("K",K)
B = np.cumsum(B)
# print(B)
C = []
for i in range(L):
  start = 2*i
  last = 2*i+2*K+1
  if last>L:
    # print("break",last)
    break
  C.append(B[last]-B[start])
# print(C)
ans = max(C)
print(ans)

Submission status: Accepted

Solution code:

import numpy as np
N, K = map(int, input().split())
s = input()
S = []
S.append(1)
for c in s:
    S.append(int(c))
S.append(1)
#print(S)

Blocks = 2 * K + 1
l = len(S)
count = 0
Zone = []
for i in range(l-1):
    count += 1 
    if S[i] != S[i+1]:
        Zone.append(count)
        count = 0
        
if S[l-2] != S[l-1]:
    Zone.append(1)
else:
    Zone.append(count+1)

#print(Zone)
Persons = []
if Blocks >= len(Zone):
    print(N)
else:
    Persons.append(sum(Zone[0:Blocks]))
    j = 0
    while Blocks + j < len(Zone):
        Persons.append(Persons[int(j/2)]+Zone[Blocks+j]+Zone[Blocks+j+1]-Zone[j]-Zone[j+1])
        j += 2
    Persons[0] -= 1
    Persons[len(Persons)-1] -= 1
    #print(Persons)
    print(max(Persons))

Submission status: Accepted

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

arr = []
now = S[0]
if now == "1":
    count = 1
else:
    count = -1
for c in S[1:]:
    next = c
    if c == now:
        if now == "1":
            count += 1
        else:
            count -= 1
    else:
        arr.append(count)
        if now == "1":
            count = -1
            now = "0"
        else:
            count = 1
            now = "1"
arr.append(count)

anss = []
Sum = 0
head = 0
if arr[0] < 0:
    arr = [0] + arr
arr2 = [0] + list(accumulate(list(map(abs, arr))))
while head+2*K <= len(arr):
    tail = head+2*K
    Sum += arr2[tail+(tail < len(arr2)-1)]-arr2[head]
    #Sum += sum(map(abs, arr[head:tail+1]))
    anss.append(Sum)
    head += 2
    Sum = 0
if anss == []:
    ans = sum(map(abs,arr))
else:
    ans = max(anss)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

n, k = map(int, input().split())
s = input()
s += "2"
n += 1

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

fin = False
i = 0
while i < n:
    if fin:
        break
    for j in range(i, n):
        if s[j] != s[i]:
            nums.append(j-i)
            i = j
            break
        if i == n-1:
            fin = True
            break

if s[-2] == "0":
    nums.append(0)
# print(nums)
length = min([2*k+1, len(nums)])

ans = 0
for i in range(0, length):
    ans += nums[i]

oldsum = ans
for i in range(0, len(nums), 2):
    if i + length + 1 < len(nums):
        newsum = oldsum - (nums[i] + nums[i+1]) + (nums[length+i] + nums[length+i+1])
        if newsum > ans:
            ans = newsum
        oldsum = newsum
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import groupby
from itertools import accumulate

input = sys.stdin.readline

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

sakadati = []

sakadati.append(0)
if S[0] == 0:
    sakadati.append(0)

for key, value in groupby(S):
    sakadati.append(len(list(value)))

sakadati.append(0)

rui = list(accumulate(sakadati))

max = 0
for i in range(len(rui) - 2 * K - 1):
    if i % 2 == 1:
        continue
    cur = rui[i + 2 * K + 1] - rui[i]
    if max < cur:
        max = cur

if len(rui) <= 2*K+1:
    print(len(S))
else:
    print(max)

Submission status: Accepted

Solution code:
import itertools

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

before = s[0]
count = 1
lst = []
head = True if before == '1' else False
tail = True if s[-1] == '1' else False

for i in s[1:]:
    if i == before:
        count += 1
    else:
        lst.append(count)
        count = 1
        before = i
lst.append(count)

S = 0

lst1 = lst
if not head:
    S = sum(lst1[:2*k])
    lst1 = lst1[1:]
if not tail:
    S = max(S, sum(lst1[-2*k:]))
    lst1 = lst1[:-1]

lst1.insert(0,0)
accum_lst = list(itertools.accumulate(lst1))

#print('accum_lst :', accum_lst)
N = len(lst1)
if N <= 2*k + 1:
    S = max(S, accum_lst[-1])
else:
    K = 2*k+1
    for i in range(0, N-K, 2):
        S = max(S, accum_lst[i+K] - accum_lst[i])
        #print(S, accum_lst[i+K], accum_lst[i])

print(S)

Submission status: Accepted

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

cnt = 0
mite = "1"
nlist = []
mlist = []
for i in S:
    if i != mite:
        if mite == "0":
            mite = "1"
            nlist.append(cnt)
            cnt = 0
        else:
            mite = "0"
            mlist.append(cnt)
            cnt = 0
    cnt += 1

if mite == "0":
    nlist.append(cnt)
else:
    mlist.append(cnt)

if len(mlist) == len(nlist):
    mlist.append(0)



#print(mlist)
#print(nlist)

initm = sum(mlist[0 : K + 1]) 
initn = sum(nlist[0 : K]) 

mmm = initm + initn
#print(initm, initn, mmm)

for i in range(len(mlist) - K - 1):
 #   print(i)
    initm += mlist[K + 1 + i]
    initm -= mlist[i]
    initn += nlist[K + i]
    initn -= nlist[i]
    mmm = max(mmm, initm + initn)
  
print(mmm)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
l = [0]*n
if int(s[0]) == 0:
    l[0] = 1
for i in range(1,n):
    if s[i] ==  "0" and s[i-1]=="0":
        l[i] = l[i-1]
    elif s[i] == "0" and s[i-1] =="1":
        l[i] = l[i-1] + 1
    else:
        l[i] = l[i-1]
def solve(x):
    for i in range(0,n-x+1):
        if i ==0:
            if l[x-1] <= k:
                return True
            else:
                continue
        elif s[i] == "0":
            if l[i+x-1] - l[i] + 1 <= k:
                return True
        else:
           if l[i+x-1] - l[i] <= k:
               return True
    return False


def binary_search(ok,ng):
    while abs(ok-ng) >1:
        mid = (ok+ng)//2
        if solve(mid):#判定のとこは別で
            ok = mid
        else:
            ng = mid
    return ok
a = binary_search(1,n)
if solve(a+1):
    print(a+1)
else:
    print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

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

L=[]
cnt0=0
if S[0]=='0':
    L.append(0)
    cur=0
else:
    cur=1
cnt=0
for i in range(N):
    if cur==0:
        if S[i]=='0':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=1
            cnt0+=1
    else:
        if S[i]=='1':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=0
else:
    if cnt!=0:
        if cur==0:
            L.append(cnt)
            cnt0+=1
        else:
            L.append(cnt)
if S[-1]=='0':
    L.append(0)

acc=[0]+list(accumulate(L))
mx=0
if cnt0<K:
    K=cnt0
for i in range(0, len(acc), 2):
    if i+(K*2+1)<len(acc):
        mx=max(mx, acc[i+(K*2+1)]-acc[i])
print(mx)

Submission status: Accepted

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

A = [0]
B = [0]
for s in S:
  if s == '1':
    A[-1] += 1
  elif A[-1] != 0:
    A.append(0)
  if s == '0':
    B[-1] += 1
  elif B[-1] != 0:
    B.append(0)

ans = 0
c,d,e,f = 0,0,0,0

for i in range(min(len(A),len(B))):
  a = 0
  if i == 0:
    if S[0] == '1':
      c,d = sum(A[i:min(i + K + 1,len(A))]),sum(B[i:min(i + K,len(B))])
      a = c + d
    else:
      c,d = sum(A[i:min(i + K,len(A))]) , sum(B[i:min(i + K,len(B))])
      a = c + d
  else:
    if S[0] == '1':
      if i + K < len(A):
        c += A[min(i + K,len(A) - 1)] - A[i - 1]
        d += B[min(i + K - 1,len(B) - 1)] - B[i - 1]
        a = c + d
    else:
      if i + K <= len(A):
        c += A[min(i + K - 1,len(A) - 1)] - (0 if i == 1 else A[i - 2])
        d += B[min(i + K - 1,len(B) - 1)] - B[i - 1]
        a = c + d
  ans = max(ans,a)
print(ans)

Submission status: Accepted

Solution code:
n,k = [int(i) for i in input().split()]
s = [int(i) for i in input()]

num = [0]
which = s[0]
sign = [which]
for i in s:
  if i != which:
    which = 1-which
    num.append(0)
    sign.append(which)
  num[-1] += 1

num_0 = len(sign) - sum(sign)

if k >= num_0:
  print(sum(num))
  exit()

if sign[0] == 0:
  num = [0] + num

if sign[-1] == 0:
  num.append(0)

sum_now = sum(num[0:2*k+1])
ans = sum_now

for i in range(0,len(num),2):
  if i == 0:
    continue
  if i+2*k >= len(num):
    break
  
  plus = num[i+2*k-1]+num[i+2*k]
  minus = num[i-2] + num[i-1]
  diff = plus - minus
  sum_now += diff
  if sum_now > ans:
    ans = sum_now

print(ans)

Submission status: Accepted

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

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    elif s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        elif s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
li = np.array(li)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
if s[0] == "0":
    zero = []
    one = []
    c = 1
    now = s[0]
    for i in range(1, n):
        if s[i] == now:
            c += 1
            if i == n - 1:
                if now == "0":
                    zero.append(c)
                else:
                    one.append(c)
        else:
            if now == "0":
                zero.append(c)
                if i == n - 1:
                    one.append(1)
            else:
                one.append(c)
                if i == n - 1:
                    zero.append(1)
            c = 1
            now = s[i]

    pos_zero = len(zero)
    #print(zero, one)
    if pos_zero <= k:
        print(n)
        exit()
    q = sum(zero[:k])
    sum_zero = [q]
    for i in range(pos_zero - k):
        q = q - zero[i] + zero[k + i]
        sum_zero.append(q)
    pos_one = len(one)
    q = sum(one[:k])
    sum_one = [q]
    for i in range(pos_one - k):
        q = q - one[i] + one[k + i]
        sum_one.append(q)
    ans = sum_zero[0] + sum_one[0]
    #print(sum_zero)
    #print(sum_one)
    for i in range(1, pos_zero - k + 1):
        if i - 1 < pos_one and i < len(sum_one):
            ansq = sum_zero[i] + sum_one[i] + one[i - 1]
        elif i < len(sum_one):
            ansq = sum_zero[i] + sum_one[i]
        elif i-1 < pos_one:
            ansq = sum_zero[i] + one[i-1]
        else:
            ansq = sum_zero[i]
        ans = max(ans, ansq)

    print(ans)
else:
    zero = []
    one = []
    c = 1
    now = s[0]
    for i in range(1, n):
        if s[i] == now:
            c += 1
            if i == n - 1:
                if now == "0":
                    zero.append(c)
                else:
                    one.append(c)
        else:
            if now == "0":
                zero.append(c)
                if i == n - 1:
                    one.append(1)
            else:
                one.append(c)
                if i == n - 1:
                    zero.append(1)
            c = 1
            now = s[i]
    one.append(0)
    pos_zero = len(zero)
    #print(zero, one)
    if pos_zero <= k:
        print(n)
        exit()
    q = sum(zero[:k])
    sum_zero = [q]
    for i in range(pos_zero - k):
        q = q - zero[i] + zero[k + i]
        sum_zero.append(q)
    pos_one = len(one)
    q = sum(one[:k+1])
    sum_one = [q]
    for i in range(pos_one - k -1):
        q = q - one[i] + one[k + i + 1]
        sum_one.append(q)
    ans = sum_zero[0] + sum_one[0]
    #print(sum_zero)
    #print(sum_one)
    for i in range(1, pos_zero - k + 1):
        ansq = sum_zero[i] + sum_one[i]
        ans = max(ans, ansq)

    print(ans)