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: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    S = SS()

    # 1の塊の長さと位置を調べる
    l = []
    if S[0] == '1':
        l.append(0)
    for i in range(N - 1):
        if S[i] == '0' and S[i+1] == '1':
            l.append(i + 1)
        elif S[i] == '1' and S[i+1] == '0':
            l.append(i + 1)
    if S[-1] == '1':
        l.append(N)
    # print(l)

    # 1の塊をK+1個くっつけた場合の長さを調べる
    ans = 0
    for i in range(len(l) // 2 - K):
        ans = max(l[2*i+2*K+1] - l[2*i], ans)

    # 端の0を逆立ちさせた場合
    if S[0] == '0':
        ans = max(l[2*K-1], ans)
    if S[-1] == '0':
        ans = max(N - l[len(l)//2-K], ans)
    
    # 全部1だった場合(塊の間も無いし端の0もない)
    if l == [0, N]:
        ans = N

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        ans = 0
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                pass # ここから何か書いてね

def solve():
    n, k = getList()
    S = getS()
    ren = []
    if S.startswith("0"):
        ren.append(0)

    ctmp = ""
    ntmp = 0
    for c in S:
        if ctmp != "" and ctmp != c:
            ren.append(ntmp)
            ntmp = 1
            ctmp = c
        else:
            ntmp += 1
            ctmp = c
    ren.append(ntmp)
    if S.endswith("0"):
        ren.append(0)

    # print(ren)
    for i in range(len(ren) - 1):
        ren[i+1] += ren[i]

    if 2 + k + 1 >= len(ren):
        print(ren[-1])
        return
    # print(ren)
    off = 0
    ans = 0
    while True:
        if off == 0:
            ans = max(ans, ren[2 * (off + k)])
        else:
            ans = max(ans, ren[2 * (off + k)] - ren[2 * off - 1])

        off += 1
        if 2 * (off + k) >= len(ren):
            print(ans)
            return

def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Runtime Error

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

k = min(k,len(s)//2)
ans = 0

for j in range(len(s)//2-k+1):
    if j==0:
        now = sum(s[:k*2+1])
        ans = now
    else:
        now = now-s[j*2-1]-s[j*2-2]+s[(j+k)*2]+s[(j+k)*2-1]
        ans = max(ans,now) 
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
s = input()
sento = 0
ketu = 0
tmp = '1'
zeroichi = []
cnt = 0

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

zeroichi.append(cnt)

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

if len(zeroichi) == 1:
    zeroichi.append(0)
    zeroichi.append(0)

i = 0
ans = 0
ans_list = []
j = 0
right = 1+k*2
left = 0

while i != right:
    ans += zeroichi[i]
    i += 1

ans_list.append(ans)

while right != len(zeroichi):
    ans -= zeroichi[left]
    ans -= zeroichi[left+1]
    ans += zeroichi[right]
    ans += zeroichi[right+1]
    ans_list.append(ans)
    left += 2
    right += 2

print(max(ans_list))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
s = input()
zero,one = [],[]
cnt = 0
if s[0] == "0":
    flag = True
else:
    flag = False
for i in range(n-1):
    if s[i] == "0" and flag == True:
        cnt +=1
        if s[i] == "0" and s[i+1] =="1":
            zero.append(cnt)
            flag = False
            cnt = 0
    elif s[i] == "1" and flag == False:
        cnt +=1
        if s[i+1] =="0":
            one.append(cnt)
            flag = True
            cnt = 0
    else:
        cnt +=1
        
    if i == n-2:
        if s[i+1] == "0":
            cnt +=1
            zero.append(cnt)
        elif s[i+1] == "1":
            cnt +=1
            one.append(cnt)
            
sum1 = sum(zero[:k]) + sum(one[:k+1])
ans = sum1
#print(sum1,ans,len(zero),zero,one)
if k >= len(zero):
    print(n)
    exit()
else:
    if s[0] == "1":
        for i in range(1,len(zero)-k):
            #print(sum1)
            sum1 -=(zero[i] + one[i])
            sum1 +=(zero[i+k] + one[i+k+1])
            ans = max(ans,sum1)
            #print(sum1,ans)
    elif s[0] =="0":
        print(sum1,ans)
        for i in range(1,len(zero)-k):
            sum1 -=(zero[i] + one[i])
            
            sum1 +=(zero[i+k] + one[i+k])
            ans = max(ans,sum1)
            
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from itertools import groupby
import sys

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

S = [[i, len(list(j))] for i, j in groupby(S)]

if len(S) // 2 <= K:
    if len(S) % 2 == 1 and S[-1][0] == "0":
        pass
    else:
        print(sum([j for i, j in S]))
        sys.exit()

ans = 0
cnt = 0
lidx = -1
for i, j in S:
    lidx += 1
    if cnt == K and i == "0":
        break
    ans += j
    if i == "0":
        cnt += 1
sidx = 0
mans = ans
for i in range(lidx,len(S)):
    ans += S[i][1]
    if i == len(S)-1 or S[i][0] == "1":
        while True:
            ans -= S[sidx][1]
            sidx += 1
            if S[sidx][0] == "1":
                break
        mans = max(mans, ans)

print(mans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
s=list(input())
t=[int(int(i)==0) for i in s]
for i in range(1,n):
  t[i]+=t[i-1]
# print(t)
t=t[0]+t+t[-1]
from bisect import*
ans=0
for i in range(t[-1]):
  tmp=bisect(t,i+k+1)-bisect(t,i)
  ans=max(ans,tmp)
print(ans+1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

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

sums = [0] * (len(li)+1)
for i in range(0,len(li)):
    sums[i+1] = li[i] + sums[i]

ans = 0
ma = k*2+1 if fi == 1 else k*2
nn = max(1, len(sums) - ma)
for i in range(nn, len(sums)):
    sum = sums[i] - sums[i-ma]
    ans = max(ans, sum)

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
    num += 1
    if S[i] == '0':
        cnt += 1
L.append(num)
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 0
cnt = 0
L = []
for i in range(N):
    if i < num:
        continue
    s = S[i]
    for j in range(i,N):
        if S[j] != s:
            L.append(j-num)
            num = j
            break
s = S[-1]
for i in range(N-1,-1,-1):
    if S[i] != s:
        L.append(N-1-i)
        break
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
start = 0
ans = 0
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
    start = 1
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
    if start == 1:
        cnt = (N+1)//2
    else:
        cnt = N//2
else:
    cnt = N//2
if cnt <= K:
    print(N)
    exit()
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
print(ans)

Submission status: Runtime Error

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      if i+k <= len(off)-1:
        b += off[i+k]
      b -= off[i-1]
    # print (a,b)
    s = a+b
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
    else:
      a += on[i+k-1]
      a -= on[i-1]
      b += off[i+k-1]
      b -= off[i-1]
    s = a+b
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Runtime Error

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
      s = a+b
    else:
      a += on[i+k-1]
      a -= on[i-1]
      b += off[i+k]
      b -= off[i-1]
      s = a+b
    # print (a,b)
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
      s = a+b
      # print (sum(on[i:i+k]),sum(off[i:i+k]))
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
      s = a+b
    else:
      a += on[i+k-1]
      a -= on[i-1]
      b += off[i+k-1]
      b -= off[i-1]
      #s = sum(on[i:i+k]) + sum(off[i-1:i+k])
      # print (sum(on[i:i+k]),sum(off[i-1:i+k]))
      s = a+b
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Runtime Error

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

on = []
off = []

acnt = 0
bcnt = 0
for i in s:
  if i == '0':
    if bcnt > 0:
      off.append(bcnt)
      bcnt = 0
    acnt += 1
  else:
    if acnt > 0:
      on.append(acnt)
      acnt = 0
    bcnt += 1
if bcnt > 0:
  off.append(bcnt)
  bcnt = 0
if acnt > 0:
  on.append(acnt)
  acnt = 0
ans = 0
if s[0] == '1':
  for i in range(len(on)-k+1):
    s = 0
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k+1])
      s = a+b
    else:
      a += on[i+k-1]
      a -= on[i-1]
      b += off[i+k]
      b -= off[i-1]
      s = a+b
    print (a,b)
    ans = max(ans,s)
else:
  for i in range(len(on)-k+1):
    if i == 0:
      a = sum(on[i:i+k])
      b = sum(off[i:i+k])
      s = a+b
      # print (sum(on[i:i+k]),sum(off[i:i+k]))
    elif i == 1:
      a = sum(on[i:i+k])
      b = sum(off[i-1:i+k])
      s = a+b
    else:
      a += on[i+k-1]
      a -= on[i-1]
      b += off[i+k-1]
      b -= off[i-1]
      #s = sum(on[i:i+k]) + sum(off[i-1:i+k])
      # print (sum(on[i:i+k]),sum(off[i-1:i+k]))
      s = a+b
    ans = max(ans,s)
if ans == 0:
  print (n)
else:
  print (ans)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = [int(s) for x in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N+1)

for l in range(N):
	if s[l] + s[l-1] == 0:
		continue
	while r < N and used[r] - used[l-1] <= K:
		r += 1
		if S[r-1] == 1 and S[r] == 0:
			used[r] == used[r-1] + 1
		else:
			used[r] = used[r-1]
	ans = max(ans, r-l)

print(ans)

Submission status: Runtime Error

Solution code:
"""
keyword: 尺取法
"""

import sys
sys.setrecursionlimit(10**6)

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

nums = []
now = 1 # 今見ている数
cnt = 0 # nowがいくつ並んでいるか

for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1 # 0と1を切り替える
        cnt = 1 # 新しいのをカウント
if cnt != 0:
    nums.append(cnt)

# 1-0-1-0-1-0-1って感じの配列が欲しい
# 1-0-1-0みたいに0で終わっていたら、適当に1つ足す
# 補足：1-0-1-0-1というのは、1が0個、0が2個、1が1個、、、などと並んでいるという意味。このとき1つ目の0をひっくり返すと1-1-1と連続する。1-...-1と連続している数が求める値なので、左端と右端は1にしたい
if len(nums)%2 == 0:
    nums.append(0)
    
add = 2*k+1

# 累積和を作る
tot = [0]*(len(nums)+1)
for i in range(len(tot)):
    tot[i+1] = tot[i]+nums[i]

ans = 0

# 1-0-1...の、1から始まり1で終わる範囲を見るので、偶数番目だけ見る
for i in range(0, len(nums), 2):
    
    # 次のleft, rightを計算する
    left = i
    right = min(i+add, len(nums))
    tmp = tot[right] - tot[left]
    
    ans = max(tmp, ans)
    
print(ans)

Submission status: Runtime Error

Solution code:
#create date: 2020-07-03 22:02

import sys
stdin = sys.stdin
from itertools import groupby, accumulate

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, k = na()
    s = ns()
    a = list()
    if s[0] == "0":
        a.append(0)
    gr = groupby(s)
    for key, group in gr:
        a.append(len(list(group)))
    if s[-1] == "0":
        a.append(0)
    acum = list(accumulate(a))
    m = len(acum)
    l = 2*k + 1
    if m == 1:
        print(acum[0])
        quit()
    ans = acum[l-1]
    for i in range(0, m-l+1, 2):
        ans = max(ans, acum[i+l-1] - acum[i-1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def f(s):
    if s == "":
        return []
    if s[0] == "1": 
        if "0" in s:
            i = s.index("0")
            return [len(s[:i])]+f(s[i:])
        else:
            return [len(s)]
    else:
        if "1" in s:
            i = s.index("1")
            return [-len(s[:i])]+f(s[i:])
        else:
            return [-len(s)]
from itertools import accumulate
N,K = map(int,input().split())
S = input()
ls = f(S)
inds = []
for i in range(len(ls)):
    if ls[i] < 0:
        inds.append(i)
acc1 = [0]+list(accumulate(ls, lambda x,y:max(x,0)+max(0,y)))
if acc1[1] < 0:
    acc1[1] *= -1
acc2 = [0]+list(accumulate([-ls[i] for i in inds], lambda x,y:x+y))
ans = max(ls)

for i in range(len(inds)-K+1):
    #print(acc2[i+K]-acc2[i], acc1[min(inds[i+K-1]+2, len(acc1)-1)],acc1[max(inds[i]-1,0)])
    ans = max(acc2[i+K]-acc2[i]+acc1[min(inds[i+K-1]+2, len(acc1)-1)]-acc1[max(inds[i]-1,0)], ans)
print(ans)

Submission status: Runtime Error

Solution code:

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

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

ans = 0

x = []

f = s[0]

z = 0
o = 0
ans = 0

for i in s:
    if i == 0:
        if f == 1:
            x.append(o)
            o = 0
            z += 1
            f = 0
        else:
            z += 1
    else:
        if f == 0:
            x.append(z)
            z = 0
            o += 1
            f = 1
        else:
            o += 1
    
if s[-1] != s[-2]:
    x.append(1)
else:
    x[-1] += 1
    
    
    
if k > len(x):
    print(sum(x))
else:
    for i in range(len(x)-k):
        ans = max(ans,sum(x[i:i+k+1]))
    print(ans)

Submission status: Runtime Error

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n,k = lr()
s = sr()
length1 = 0
tmp1 = 0
one = []
for c in s:
    if c == '1':
        tmp1+=1
    else:
        if tmp1 != 0:
            length1 += 1
            one.append(tmp1)
            tmp1 = 0
if tmp1 != 0:
    length1 += 1
    one.append(tmp1)

zero = [0 for i in range(length1+1)]
ind = 0
while ind != n and s[ind] == '0':
    zero[0]+=1
    ind+=1
tmp0 = 0
ind0 = 1
while ind != n:
    while ind != n and s[ind] == '1':
        if tmp0 != 0:
            zero[ind0] = tmp0
            tmp0 = 0
            ind0+=1
        ind+=1
    while ind != n and s[ind] == '0':
        tmp0+=1
        ind+=1
if tmp0 != 0:
    zero[-1] = tmp0

a2 = [0 for i in range(len(zero)+1)]
a2[1] = zero[0]+one[0]
for i in range(2,len(zero)):
    a2[i] = a2[i-1]+zero[i-1]+one[i-1]
a2[len(zero)] = a2[len(zero)-1]+zero[len(zero)-1]

def sumArea(l,r):
    if l == 0:
        return a2[r]-a2[l]
    else:
        return a2[r]-a2[l]+one[l-1]

ans = 0
for i in range(len(zero)-k+1):
    ans = max(ans, sumArea(i,i+k))
print(ans)

Submission status: Runtime Error

Solution code:
N, K = 13, 1
S = "0000011100110"

# N, K = 2, 2
# S = "00"


# N, K = 1, 1
# S = "1"
#
#
# N, K = 5, 1
# S = "00010"
#
N, K = map(int,input().split())
S = input()

def calculate(n, k, s):
    s = list(s)

    result = [{'start': 0, 'end': 0}]
    for i in range(n):

        previous = s[i - 1]
        current = s[i]

        if i == 0:
            if s[i] == '1':
                result.append({'start': 0})
        else:
            if (current == '0') and (previous == '1'):
                res = result[-1]
                res.__setitem__('end', i)
                result[-1] = res

            if (current == '1') and (previous == '0'):
                result.append({'start': i})

            if i == n - 1 and s[i] == '1':
                res = result[-1]
                res.__setitem__('end', i + 1)
                result[-1] = res

    result.append({'start': n, 'end': n})
    maxValue = 0
    if len(result) > k:
        for i in range(len(result) - k):
            val = result[i + k]['end'] - result[i]['start']
            maxValue = max(val, maxValue)
    else:
        maxValue = max(maxValue, result[-1]['end'] - result[0]['start'])
    print(maxValue)


calculate(N, K, S)

Submission status: Runtime Error

Solution code:
N, K = 13, 1
S = "0000011100110"

# N, K = 2, 2
# S = "00"


# N, K = 1, 1
# S = "1"
#
#
# N, K = 5, 1
# S = "00010"
#
N, K = map(int,input().split())
S = input()

def calculate(n, k, s):
    s = list(s)

    result = [{'start': 0, 'end': 0}]
    for i in range(n):

        previous = s[i - 1]
        current = s[i]

        if i == 0:
            if s[i] == '1':
                result.append({'start': 0})
        else:
            if (current == '0') and (previous == '1'):
                res = result[-1]
                res.__setitem__('end', i)
                result[-1] = res

            if (current == '1') and (previous == '0'):
                result.append({'start': i})

            if i == n - 1 and s[i] == '1':
                res = result[-1]
                res.__setitem__('end', i + 1)
                result[-1] = res

    result.append({'start': n, 'end': n})
    maxValue = 0
    if len(result) > k:
        for i in range(len(result) - k):
            val = result[i + k]['end'] - result[i]['start']
            maxValue = max(val, maxValue)
    else:
        maxValue = max(maxValue, result[-1]['end'] - result[0]['start'])
    print(result)
    print(maxValue)


calculate(N, K, S)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
s = input()

compressed = []

first = s[0]
prev = s[0]
cnt = 1
for x in s[1:]:
    if prev == x:
        cnt += 1
    else:
        if x == "1":
            compressed.append(cnt)
            cnt = 1
        else:
            compressed.append(cnt)
            cnt = 1
    prev = x
compressed.append(cnt)


result = [0] + list(accumulate(compressed))

ans = []
if first == "1":
    for i in range(0, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k + 1] - result[i])
    for i in range(1, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k] - result[i])
else:
    for i in range(0, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k] - result[i])
    for i in range(1, (len(s) - 2 * k) // 2, 2):
        ans.append(result[i + 2 * k + 1] - result[i])

print(max(ans))

Submission status: Runtime Error

Solution code:
n, k=[int(i) for i in input().split()]
s=input()
count = 0
pos_prev = 0
result=1
for i in range(1,n):
  if s[i-1] == '0' and s[i] == '1':
    if count == 0:
      pos_next = i
      j = i
      count += 1
    
    while count < k:
      j += 1
      if j > n:
        count = k
        break
      if s[j-1] == '0' and s[j] == '1':
        count += 1

    pos_end = n-1
    for m in range(j,n-1):
      if s[m] == '1' and s[m+1] == '0':
        pos_end = m
        break

    if count == k or i == n-1:
      len = pos_end - pos_prev + 1
      result = max(len, result)
      pos_prev = pos_next
      count = 0
print(result)

Submission status: Runtime Error

Solution code:
n, k=[int(i) for i in input().split()]
s=input()
count = 0
pos_prev = 0
result=1
for i in range(1,n):
  if s[i-1] == '0' and s[i] == '1':
    if count == 0:
      pos_next = i
      j = i
      count += 1
    
    while count < k:
      j += 1
      if j > n:
        break
      if s[j-1] == '0' and s[j] == '1':
        count += 1

    pos_end = n-1
    for m in range(j,n-1):
      if s[m] == '1' and s[m+1] == '0':
        pos_end = m
        break

    if count == k or i == n-1:
      len = pos_end - pos_prev + 1
      result = max(len, result)
      pos_prev = pos_next
      count = 0
print(result)

Submission status: Runtime Error

Solution code:

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

a = []
f = S[0]
l = 0
for i in range(1, N+1):
    #print(S[i])
    if f != S[i]:
        #a.append([l, i-1, int(f)])
        #a.append([i-l, int(f)])
        a.append(i-l)
        l = i
        f = S[i]
        
#print(a)

if S[0] == '0':
    a = [0] + a

#print(a[0:0+2*K+1])
SUM = sum(a[0:0+2*K+1])

MAX = max(0, SUM)
for i in range(1, len(a)//2+len(a)%2):
    if i % 2 == 0:
        #print(a[i:i+2*K+1])
        #print(a[i-2], a[i-1])
        #print(a[i+2*K-1], a[i+2*K])
        #print(sum(a[i:i+2*K+1]))
        #MAX = max(MAX, sum(a[i:i+2*K+1]))
        SUM = SUM-(a[i-2]+a[i-1])+(a[i+2*K-1]+a[i+2*K])
        MAX = max(MAX, SUM)

print(MAX)

Submission status: Runtime Error

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

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

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

cs = [0] * (len(cnt)+1)
for i in range(len(cnt)):
    cs[i+1] = cs[i] + cnt[i]

ans = 0
m = 2 * k + 1
for i in range(0, len(cnt), 2):
    ans = max(ans, cs[i+m] - cs[i])

print(ans)

Submission status: Runtime Error

Solution code:
N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
max_n=sum_n
for i in range(len(ans)-end+1):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         print(max_n)
         exit()
      now=0
   max_n=max(sum_n,max_n)
print(max_n)

Submission status: Runtime Error

Solution code:
N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
max_n=sum_n
for i in range(len(ans)-end+1):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         print(max_n)
         exit()
      now=0
   max_n=max(sum_n,max_n)

Submission status: Runtime Error

Solution code:
N,K=list(map(int,input().split()))
l=input()
n=l[0]
cnt=0
ans=[]
for i in l:
   if i != n:
      ans.append(cnt)
      cnt=1
      n=i
   else:
      cnt+=1
ans.append(cnt)
if l[0] == "0":
   sum_n=sum(ans[0:K*2])
   now=1
   end=K*2
else:
   sum_n=sum(ans[0:K*2+1])
   now=0
   end=K*2+1
max_n=sum_n
for i in range(len(ans)-end+1):
   sum_n-=ans[i]
   if now==0:
      now=1
   else:
      try:
         sum_n=sum_n+ans[end]+ans[end+1]
         end+=2
      except IndexError:
         sum_n+=ans[end]
         max_n=max(sum_n,max_n)
         break
      now=0
   max_n=max(sum_n,max_n)
print(max_n)

Submission status: Runtime Error

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

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

if N == 1:
  if S == "1" or K >= 1:
    print(1)
  else:
    print(0)
    
else:
  num = deque([])
  if S[0] == "0":
    num.append(0)
  cnt = 1
  ans = 0
  M = 2 * K + 1
  
  for i in range(1,N):
    if S[i] == S[i - 1]:
      cnt += 1
    else:
      num.append(cnt)
      cnt = 1
      
    if len(num) > M:
      num.popleft()

    if S[i - 1] == "1":
      ans = max(sum(num),ans)
    
    if i == N - 1:
      num.append(cnt)
      if len(num) > M:
        num.popleft()
      if S[i] == "1":
        ans = max(sum(num),ans)
  
  print(ans)