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: Wrong Answer

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

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

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

cum = [0]
for x in l:
    cum.append(cum[-1] + x)
# print(l)
# print(cum)
ans = max(l)
for i in range(0, n, 2):
    r = i + 2 * k + 1
    if r >= len(cum):
        break
    # print(cum[r] - cum[i])
    ans = max(ans, cum[r] - cum[i])

print(ans)

Submission status: Wrong Answer

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

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

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

cum = [0]
for x in l:
    cum.append(cum[-1] + x)
# print(l)
# print(cum)
ans = max(l)
for i in range(0, n, 2):
    r = i + 2 * k + 1
    if r >= len(cum):
        break
    print(cum[r] - cum[i])
    ans = max(ans, cum[r] - cum[i])

print(ans)

Submission status: Wrong Answer

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

parity = []
runlength = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        parity.append(bool(int(prev)))
        runlength.append(run)
        run = 0
    prev = c
    run += 1
parity.append(bool(int(prev)))
runlength.append(run)

if parity.count(False) <= K:
    print(N)
    quit()

argmax = 0
maximum = 0

L = len(parity)
for i in range(L):
    total = sum(runlength[max(0, i - 1): min(L, i + 2)])
    if not parity[i] and total > maximum:
        argmax = i
        maximum = total

while True:
    parity[argmax] = True
    runlength[argmax] = maximum
    if argmax + 1 < L:
        del parity[argmax + 1]
        del runlength[argmax + 1]
    if argmax - 1 >= 0:
        del parity[argmax - 1]
        del runlength[argmax - 1]
    K -= 1
    if not K:
        print(maximum)
        break

    L = len(parity)
    maximum = 0
    for i in range(max(0, argmax - 2), min(L, argmax + 2)):
        total = sum(runlength[max(0, i - 1): min(L, i + 2)])
        if not parity[i] and total > maximum:
            argmax = i
            maximum = total

Submission status: Wrong Answer

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

parity = []
runlength = []

prev = S[0]
run = 0
for c in S:
    if c != prev:
        parity.append(bool(int(prev)))
        runlength.append(run)
        run = 0
    prev = c
    run += 1
parity.append(bool(int(prev)))
runlength.append(run)

if parity.count(False) <= K:
    print(N)
    quit()

parity = [not parity[0]] + parity + [not parity[-1]]
runlength = [0] + runlength + [0]

while True:
    argmax = 0
    maximum = 0
    for i in range(1, len(parity) - 1):
        total = sum(runlength[i - 1: i + 2])
        if not parity[i] and total > maximum:
            argmax = i
            maximum = total

    parity[argmax] = True
    runlength[argmax] = maximum
    del parity[argmax + 1]
    del parity[argmax - 1]
    del runlength[argmax + 1]
    del runlength[argmax - 1]

    K -= 1
    if not K:
        print(maximum)
        break

    if runlength[0]:
        parity = [not parity[0]] + parity
        runlength = [0] + runlength
    if runlength[-1]:
        parity += [not parity[-1]]
        runlength += [0]

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input() + "#"
count = 1
group = 0
L = []
for i in range(n):
  if s[i] == s[i+1]:
    count += 1
  else:
    L.append(count)
    group += 1
    count = 1
f = 0 if s[0] == "0" else 1
if (f==0 and k >= (group+1)//2) or (f==1 and k>=group//2):
  ans = n
else:
  temp = sum(L[:f+2*k])
  ans = temp
  for i in range(f+2*k+1, group, 2):
    temp -= L[i-2*k-1-f] + L[i-2*k-f]
    temp += L[i-1] + L[i]
    ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input() + "#"
count = 1
group = 0
L = []
for i in range(n):
  if s[i] == s[i+1]:
    count += 1
  else:
    L.append(count)
    group += 1
    count = 1
f = 0 if s[0] == "0" else 1
if (f==0 and k >= (group+1)//2) or (f==1 and k>=group//2):
  ans = n
else:
  temp = sum(L[:f+2*k])
  ans = temp
  for i in range(f+2*k+1, group, 2):
    temp -= L[i-2*k-2] + L[i-2*k-1]
    temp += L[i-1] + L[i]
    ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
s = input() + "#"
count = 1
group = 0
L = []
for i in range(n):
  if s[i] == s[i+1]:
    count += 1
  else:
    L.append(count)
    group += 1
    count = 1
ans = 0
if k >= group//2:
  ans = n
else:
  temp = sum(L[:2*k+1])
  ans = temp
  for i in range(2*k+1, group):
    temp -= L[i-(2*k+1)]
    temp += L[i]
    ans = max(temp, ans)
print(ans)

Submission status: Wrong Answer

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


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


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


def S(): return input()


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


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


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


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


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


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


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


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


# show_flg = True
show_flg = False


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

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


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


def S(): return input()


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


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


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


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


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


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


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


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


# show_flg = True
show_flg = False


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

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def score(N:int,S:list,start:int,K:int)->int:
    cnt = 0
    ans = 0
    index = start
    S += [1]
    while cnt < K:
        if not(S[index]):
            nxt = S[index:].index(1)
            ans += min(K -cnt,nxt - index)
            index = nxt
            cnt += 1
        if index == N:
            return ans
    return ans


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def score(N:int,S:list,start:int,K:int)->int:
    cnt = 0
    ans = 0
    index = start
    S += [1]
    while cnt < K:
        if not(S[index]):
            nxt = S[index:].index(1)
            ans += min(K -cnt,nxt - index)
            index = nxt
            cnt += 1
        if index == N:
            return ans
    return ans


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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

leng=len(num_cnt)
if leng//2>k:
  ans=sum(num_cnt[:2*k])

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

Submission status: Wrong Answer

Solution code:
def solve(s, k):

    target = ''
    c = []

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

    is_start_with_zero = 1 - int(s[0])
    end = len(c)-2*k+1
    ans = sum(c[0:2*k]) if is_start_with_zero else 1

    for i in range(is_start_with_zero, end, 2):
        t = sum(c[i:i+2*k+1])
        ans = t if ans < t else ans

    return ans


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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import accumulate
n,k=map(int,input().split())
s=input()
l=[]
cnt=1
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
  else:
    l.append(cnt)
    cnt=1
l.append(cnt)
al=deepcopy(l)
al=[0]+al
al=list(accumulate(al))
al+=[n+1]
ans=0
for i in range(len(al)):
  if s[0]=='0':
    if i%2:
      ans=max(ans,al[min(i+2*k-1,len(al)-1)]-al[i-1])
  else:
    if i%2:
      ans=max(ans,al[min(i+2*k,len(al)-1)]-al[i-1])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import accumulate
n,k=map(int,input().split())
s=input()
l=[]
cnt=1
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
  else:
    l.append(cnt)
    cnt=1
l.append(cnt)
al=deepcopy(l)
al=[0]+al
al=list(accumulate(al))
ans=0
for i in range(len(al)):
  if s[0]=='0':
    if i%2:
      ans=max(ans,al[min(i+2*k-1,len(al)-1)]-al[i-1])
  else:
    if i%2:
      ans=max(ans,al[min(i+2*k,len(al)-1)]-al[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import accumulate
n,k=map(int,input().split())
s=input()
l=[]
cnt=1
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
  else:
    l.append(cnt)
    cnt=1
l.append(cnt)
al=deepcopy(l)
al=[0]+al
al=list(accumulate(al))
print(al)
ans=0
for i in range(len(al)):
  if s[0]=='0':
    if i%2:
      ans=max(ans,al[min(i+2*k-1,len(al)-1)]-al[i-1])
  else:
    if i%2:
      ans=max(ans,al[min(i+2*k,len(al)-1)]-al[i-1])
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import accumulate
n,k=map(int,input().split())
s=input()
l=[]
cnt=1
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
  else:
    l.append(cnt)
    cnt=1
l.append(cnt)
al=deepcopy(l)
al=[0]+al
al=list(accumulate(al))
ans=0
for i in range(len(al)):
  if s[0]=='0':
    if i%2==0:
      ans=max(ans,al[min(i+2*k,len(al)-1)]-al[i])
  else:
    if i%2==0:
      ans=max(ans,al[min(i+2*k+1,len(al)-1)]-al[i])
print(ans)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
S = input()
s = int(S)
if s == N:
    print(N)
    exit()
# 連続した 0 と 1 の数を数える
cnt_list = []
flag = True if S[0] == '1' else False
cnt = 1
flag_flag = True
for i in range(1, N):
    if S[i] == '1':
        if i == N - 1:
            flag_flag = True
        if flag:
            cnt += 1
        else:
            flag = True
            cnt_list.append([cnt, -1])
            cnt = 1
    if S[i] == '0':
        if i == N - 1:
            flag_flag = False
        if flag:
            flag = False
            cnt_list.append([-1, cnt])
            cnt = 1
        else:
            cnt += 1
if not flag_flag:
    cnt_list.append([cnt, -1])
else:
    cnt_list.append([-1, cnt])

# 指示する回数を求める． K 回 or 連続した 0 の個数
n = len(cnt_list)
if cnt_list[0][0] == -1:
    k = min(K, math.ceil(n/2))
else:
    k = min(K, n//2)

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

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

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
S = input()
s = int(S)
if s == N:
    print(N)
    exit()
# 連続した 0 と 1 の数を数える
cnt_list = []
flag = True if S[0] == '1' else False
cnt = 1
flag_flag = True
for i in range(1, N):
    if S[i] == '1':
        if i == N - 1:
            flag_flag = True
        if flag:
            cnt += 1
        else:
            flag = True
            cnt_list.append([cnt, -1])
            cnt = 1
    if S[i] == '0':
        if i == N - 1:
            flag_flag = False
        if flag:
            flag = False
            cnt_list.append([-1, cnt])
            cnt = 1
        else:
            cnt += 1
if not flag_flag:
    cnt_list.append([cnt, -1])
else:
    cnt_list.append([-1, cnt])

# 指示する回数を求める． K 回 or 連続した 0 の個数
n = len(cnt_list)
if cnt_list[0][0] == -1:
    k = min(K, math.ceil(n/2))
else:
    k = min(K, n//2)

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

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

print(ans)

Submission status: Wrong Answer

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

first = now = S[0]

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

count.append(c)

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

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


if first == '0': # 直立している人から始まる場合
  ans = sum(count[:2*K])
  s = ans
  idx1 = 0
  idx2 = 2*K
  while idx2 < l-1:
    if idx1 == 0:
      s = s - count[0] + sum(count[idx2:idx2+2])
      idx1 += 1
    else:    
      s = s - sum(count[idx1:idx1+2]) + sum(count[idx2:idx2+2])
      idx1 += 2
    
    idx2 += 2
    ans = max(ans, s)
  
  print(ans)
else: # 逆立ちしている人から始まる場合
  ans = sum(count[:2*K+1])
  s = ans
  idx1 = 1
  idx2 = 2*K+1
  while idx2 < l-1:
    if idx1 == 1:
      s = s - sum(count[:2]) + sum(count[idx2:idx2+2])
      idx1 += 1
    else:
      s = s - sum(count[idx1:idx1+2]) + sum(count[idx2:idx2+2])
      idx1 += 2
    
    idx2 += 2
    ans = max(ans, s)
  
  print(ans)

Submission status: Wrong Answer

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

if __name__ == "__main__":
    main()