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:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

N, K = map(int, input().split())
S = input()
def main():
    now = 1
    cnt = 0
    nums = []
    for i in range(N):
        if S[i] == str(now):
            cnt += 1
        else:
            nums.append(cnt);
            now = 1-now
            cnt = 1
    if cnt != 0:
        nums.append(cnt)
    if len(nums)%2 ==0:
        nums.append(0)
    add = 2*K + 1
    res = 0
    # 累積和
    sums = [0]*(len(nums)+1)
    for i in range(len(nums)):
        sums[i+1] = sums[i] + nums[i]
    for i in range(0, len(nums), 2):
        left = i
        right = min(i+add, len(nums))
        tmp = sums[right] - sums[left]
        res = max(tmp, res)
    """
    # 尺取り法
    # ループの外にleft , right
    left = 0
    right = 0
    tmp= 0 # [left, right) のsum
    for i in range(0, len(nums), 2):
        # 次のleft, right を計算
        nextLeft = i
        nextRight = min(i+add, len(nums))
        # 左端を計算
        while (nextLeft > left):
            tmp -= nums[left]
            left += 1
        
        # 右端を計算
        while (nextRight > right):
            tmp += nums[right]
            right +=1
        res = max(tmp, res)
    """
    print(res)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

N, K = map(int, input().split())
S = input()
def main():
    now = 1
    cnt = 0
    nums = []
    for i in range(N):
        if S[i] == str(now):
            cnt += 1
        else:
            nums.append(cnt);
            now = 1-now
            cnt = 1
    if cnt != 0:
        nums.append(cnt)
    if len(nums)%2 ==0:
        nums.append(0)
    add = 2*K + 1
    res = 0
    # ループの外にleft , right
    left = 0
    right = 0
    tmp= 0 # [left, right) のsum
    for i in range(0, len(nums), 2):
        # 次のleft, right を計算
        nextLeft = i
        nextRight = min(i+add, len(nums))
        # 左端を計算
        while (nextLeft > left):
            tmp -= nums[left]
            left += 1
        
        # 右端を計算
        while (nextRight > right):
            tmp += nums[right]
            right +=1
        res = max(tmp, res)
    print(res)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

n_sum = []

ct = 1
for i in range(N-1):
    if S[i+1] == S[i]:
        ct += 1
    else:
        n_sum.append(ct)
        ct += 1

n_sum.append(ct)

if len(n_sum) == 1:
    print(ct)
    sys.exit()

else:
    if S[-1] == '0':
        n_sum.append(ct)
    if S[0] == '0':
        n_sum.insert(0, 0)

if K < len(n_sum)//2:
    Max = -1
    i = 0
    while i+2*K < len(n_sum):
        if i == 0:
            tmp = n_sum[i+2*K]
        else:
            tmp = n_sum[i+2*K] - n_sum[i-1]
        i += 2
        Max = max(Max, tmp)
else:
    Max = ct

print(Max)

Submission status: Accepted

Solution code:

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

I=[0]

for i in range(n-1):
    if s[i]!=s[i+1]:
        I.append(i+1)
        
r=len(I)

for _ in range(10**6):
        I.append(n)

X=[]

for i in range(r):
    if s[I[i]]=='0':
        X.append(I[i+2*k]-I[i])
    else:
        X.append(I[i+2*k+1]-I[i])

print(max(X))

Submission status: Accepted

Solution code:
from numpy import*
from itertools import*
N, K = map(int, input().split())
S=input()
zeros=[0]+[len(list(v)) for k,v in groupby(S) if k=="0"]
ones =[0]+(S[0]=="0")*[0]+[len(list(v)) for k,v in groupby(S) if k=="1"]+(S[-1]=="0")*[0]

#print(zeros,ones)

c_zero= cumsum(zeros)
c_one = cumsum(ones)

#print(c_zero,c_one)

if len(zeros) <= K:
    print(len(S))
else:
    ans = 0
    for i in range( len(zeros)-K ):
        aaa = c_zero[i+K]-c_zero[i] + c_one[i+K+1]-c_one[i]
        ans = max(aaa, ans)
    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s='1'+input()
i=j=0
while j<n:k-='10'==s[j:j+2];i+=k<0;k+=k<0and'01'==s[i:i+2];j+=1
print(n-i)

Submission status: Accepted

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#import math
#n=int(input())
#li=input().split()
#n=int(input())
#l=len(S)

lis=list(map(int,input().split()))
S=input()

ans=0
a=[0]
b=[0]
i,flag=0,0
while i<lis[0]:
    j=1
    if S[i]=="0":
        while flag==0 and i+j<lis[0]:
            if S[i+j]=="0":
                j+=1
            elif S[i+j]=="1":
                flag=1
        a.append(j+a[-1])
        i+=j
    else:
        while flag==0 and i+j<lis[0]:
            if S[i+j]=="1":
                j+=1
            elif S[i+j]=="0":
                flag=1
        b.append(j+b[-1])
        i+=j
    flag=0

A=len(a)-1
B=len(b)-1

if A<=lis[1]:
    ans=lis[0]
else:
    if A>B:
        for i in range(A-lis[1]+1):
            if i==0:
                ans=a[lis[1]]+b[lis[1]]
            elif i>0 and i<A-lis[1]:
                tmp=a[i+lis[1]]-a[i]+b[i+lis[1]]-b[i-1]
                if ans<tmp:
                    ans=tmp
            elif i==A-lis[1]:
                tmp=a[-1]-a[-1-lis[1]]+b[-1]-b[-1-lis[1]]
                if ans<tmp:
                    ans=tmp
    elif A<B:
        for i in range(A-lis[1]+1):
            tmp=a[i+lis[1]]-a[i]+b[i+lis[1]+1]-b[i]
            if ans<tmp:
                ans=tmp
    else:
        if S[0]=="0":
            for i in range(A-lis[1]+1):
                if i==0:
                    ans=a[lis[1]]+b[lis[1]]
                else:
                    tmp=a[i+lis[1]]-a[i]+b[i+lis[1]]-b[i-1]
                    if ans<tmp:
                        ans=tmp
        else:
            for i in range(A-lis[1]+1):
                if i<A-lis[1]:
                    tmp=a[i+lis[1]]-a[i]+b[i+lis[1]+1]-b[i]
                    if ans<tmp:
                        ans=tmp
                else:
                    tmp=a[-1]-a[-1-lis[1]]+b[-1]-b[-1-lis[1]]
                    if ans<tmp:
                        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=list(input())
s=list(map(int,s))
stack=[]
tmp=1
flag=True
for i in range(1,len(s)):
  if s[i]!=s[i-1]:
    stack.append(tmp)
    tmp=1
  else:
    tmp+=1
stack.append(tmp)
left=[0]
right=[0]
tmp=0
if s[0]==0:
  flag=False
  if len(stack)%2==1:
    stack.append(0)
  if len(stack)//2<=k:
    print(len(s))
    exit()
else:
  if len(stack)%2==0:
    stack.append(0)
  if len(stack)//2<=k:
    print(len(s))
    exit()
for i in range(len(stack)):
  tmp+=stack[i]
  if i%2==0:
    if flag:
      right.append(tmp)
    else:
      left.append(tmp)
  else:
    if flag:
      left.append(tmp)
    else:
      right.append(tmp)
ans=0
if flag:
    for i in range(len(right)-k-1):
      ans=max(ans,right[i+k+1]-left[i])
else:
  for i in range(len(right)-k):
    ans=max(ans,right[i+k]-left[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def calc():
    q.appendleft(0)
    ans = 0
    d = '1'
    kc = 0
    for i, c in enumerate(S):
        if c != d:
            d = c
            if c == '0':
                if kc == K:
                    ans = max(ans, i - q.pop())
                else:
                    kc += 1
            else:
                q.appendleft(i)
    return max(ans, N - q.pop())


N, K = map(int, input().split())
S = input()
q = deque()
print(calc())

Submission status: Accepted

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

import sys

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()

L=[]
cnt0=0
# 0始まりの時は番兵的に1の区間0を追加しておく
if S[0]=='0':
    L.append(0)
    cur=0
else:
    cur=1
cnt=0
# 1の区間の長さ、0の区間の長さ、1の区間の長さ...の配列Lを作る
for i in range(N):
    if cur==int(S[i]):
        cnt+=1
    else:
        L.append(cnt)
        if cur==0:
            cnt0+=1
        cnt=1
        # フラグの切り替え
        cur=1-cur
else:
    if cnt!=0:
        L.append(cnt)
        if cur==0:
            cnt0+=1
# 0終わりの時は番兵的に1の区間0を追加しておく
if S[-1]=='0':
    L.append(0)

if cnt0<K:
    # 0区間の数がKより少なかったら、それに合わせて区間和取る長さを短くする
    K=cnt0

# 尺取法
l=0
r=K*2+1
ans=sm=sum(L[:K*2+1])
while l<len(L) and r<len(L):
    for i in range(2):
        sm+=L[r]
        r+=1
        sm-=L[l]
        l+=1
    ans=max(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def nextj(n):
    while S[n] == '0':
        n += 1
        if n == N:
            return N
    q.appendleft(n)
    while S[n] == '1':
        n += 1
        if n == N:
            return N
    return n


def init(n):
    while S[n] == '1':
        n += 1
        if n == N:
            return N
    return n


def calc():
    q.appendleft(0)
    ans = 0
    j = init(0)
    if j == N:
        return N
    for _ in range(K - 1):
        j = nextj(j)
        if j == N:
            return N
    while True:
        j = nextj(j)
        ans = max(ans, j - q.pop())
        if j == N:
            return ans


N, K = map(int, input().split())
S = input()
q = deque()
print(calc())

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()

L=[]
cnt0=0
# 0始まりの時は番兵的に1の区間0を追加しておく
if S[0]=='0':
    L.append(0)
    cur=0
else:
    cur=1
cnt=0
# 1の区間の長さ、0の区間の長さ、1の区間の長さ...の配列Lを作る
for i in range(N):
    if cur==int(S[i]):
        cnt+=1
    else:
        L.append(cnt)
        if cur==0:
            cnt0+=1
        cnt=1
        # フラグの切り替え
        cur=1-cur
else:
    if cnt!=0:
        L.append(cnt)
        if cur==0:
            cnt0+=1
# 0終わりの時は番兵的に1の区間0を追加しておく
if S[-1]=='0':
    L.append(0)

acc=[0]+list(accumulate(L))
mx=0
if cnt0<K:
    # 0区間の数が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:
def main():
    N, K = map(int, input().split())
    S = input()
    # １で始まるグループでK=1を想定する
    # [1，0，1]だとすると、K=1で2K+1で1グループは表せる
    c_num = "1"  # 必ず1でスタートする形とする。0で始まれば、0個の1を頭に入れる
    cnt = 0
    seq = []

    for i in S:
        if i == c_num:
            cnt += 1
        else:
            c_num = i
            seq.append(cnt)
            cnt = 1
    seq.append(cnt)
    # print(seq)
    # print(leng_seq)
    if len(seq) % 2 == 0:  # "1"から始まる順番で、配列が偶数ということは0で終わってる=>ケツに0個の1をブチコム
        seq.append(0)
    # 全部１になるケース
    if len(seq) <= 2*K+1:  # 当該の要素含め前後消えるから2K+1
        print(sum(seq))
        return

    answer = 0
    total = 0
    stpr = 0

    for j in range(len(seq)-2*K):
        while stpr < j+2*K+1:
            total += seq[stpr]
            stpr += 1
        if j % 2 == 0:  # 1からスタートするものだけ2k+1分を抽出
            answer = max(answer, total)
        total -= seq[j]

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    S = input()
    seq = []
    current = "1"
    cnt = 0
    # 初手が0だと0の累積和が最初に入る(e.g. [1,2,1]が[0,1,2,1]となる)
    # ex. 0001011ならseq = [3,1,1,2] (0が3つ,1が1つ,0が2つ,1が2つ)
    for c in S:
        if c == current:
            cnt += 1
        else:
            seq.append(cnt)
            current = c
            cnt = 1
    seq.append(cnt)  # 切り替えのあったタイミングで初めて挿入されるので、最後のカウントは挿入されていないので、ここで入れる
    if len(seq) % 2 == 0:
        seq.append(0)  # 0挿入なので、大勢には影響しない。理由は不明。

    # K1回で2つの切り替え00010001 = [3,1,3,1]=>右の0３つを変えると=>[3,4]となる
    # 現在seqに格納されているのは切り替えデータだからK*2+1以内なら、全て1になる
    if len(seq) <= K*2+1:
        print(sum(seq))
        return
    ans = 0
    total = 0
    j = 0
    # Kで２つseqが消える→rangeはそれを差し引いた回数
    # 2Kの範囲でseqを前から進めていくansが最大となるものをキープし、出力する

    for i in range(len(seq)-K*2):
        while j < i+K*2+1:
            total += seq[j]
            j += 1
        if i % 2 == 0:
            ans = max(ans, total)
        total -= seq[i]  # 今回のtotalは既にキープしてあるので、動いて消える部分は取り除く
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s='1'+input()
i=0
for j in range(n):k-='10'==s[j:j+2];i+=k<0;k+=k<0and'01'==s[i:i+2]
print(n-i)

Submission status: Accepted

Solution code:
def solve():
    N,K=map(int,input().split())
    S=input()
    s2=[]
    cp='_'
    cn=0
    count={'0':0, '1':0}
    for c in S:
        if cp != c:
            if cp != '_':
                s2.append(cn)
                count[cp]+=1
            cp = c
            cn = 0
        cn += 1
    s2.append(cn)
    count[cp]+=1

    csum=[0,0,0,0,0]
    csumval=0
    for v in s2:
        csumval+=v
        csum.append(csumval)

    csum+=[csumval,csumval,csumval,csumval,csumval]
    s2_len = len(s2)
    #print(s2,s2_len)
    #print(csum)
    csumlen=len(csum)

    if count['0'] <= K:
        return csum[-1]

    #print('csumlen =',csumlen)
    ans=0
    if S[0]=='1':
        for i in range(0,s2_len+3,2):
            if 5+i+K*2>=csumlen:
                break
            ans1=csum[5+i+K*2]-csum[5+i-1]
            #print(ans1,i,i+K*2)
            ans=max(ans,ans1)
    else:
        for i in range(-1,s2_len+3,2):
            if 5+i+K*2>=csumlen:
                break
            ans1=csum[5+i+K*2]-csum[5+i-1]
            #print(ans1,i,i+K*2)
            ans=max(ans,ans1)
    return ans

print(solve())

Submission status: Accepted

Solution code:
def solve():
    N,K=map(int,input().split())
    S=input()
    s2=[]
    cp='_'
    cn=0
    count={'0':0, '1':0}
    for c in S:
        if cp != c:
            if cp != '_':
                s2.append(cn)
                count[cp]+=1
            cp = c
            cn = 0
        cn += 1
    s2.append(cn)
    count[cp]+=1

    csum=[0,0,0,0,0]
    csumval=0
    for v in s2:
        csumval+=v
        csum.append(csumval)

    csum+=[csumval,csumval,csumval,csumval,csumval]
    s2_len = len(s2)
    #print(s2,s2_len)
    #print(csum)
    csumlen=len(csum)

    if count['0'] <= K:
        return csum[-1]

    #print('csumlen =',csumlen)
    ans=0
    if S[0]=='1':
        for i in range(0,s2_len//2*2+3,2):
            if 5+i+K*2>=csumlen:
                ans1=csum[csumlen-1]-csum[5+i-1]
            else:
                ans1=csum[5+i+K*2]-csum[5+i-1]
            #print(ans1,i,i+K*2)
            ans=max(ans,ans1)
    else:
        for i in range(-1,s2_len//2*2+3,2):
            if 5+i+K*2>=csumlen:
                ans1=csum[csumlen-1]-csum[5+i-1]
            else:
                ans1=csum[5+i+K*2]-csum[5+i-1]
            #print(ans1,i,i+K*2)
            ans=max(ans,ans1)
    return ans

print(solve())

Submission status: Accepted

Solution code:
N,K=map(int, input().split())
instr=input()
lft=0
rgt=1
voids=int(instr[0] == '0')
maxlen=0
while lft < rgt:
    maxlen = max(maxlen, rgt-lft)
    if rgt < N and (instr[rgt] == '1' or (instr[rgt-1] == '0' and instr[rgt] == '0')):
        rgt += 1
    elif rgt < N and voids < K:
        voids += 1
        rgt += 1
    else:
        voids -= lft+1 < N and instr[lft] == '0' and instr[lft+1] == '1'
        lft += 1
print(maxlen)

Submission status: Accepted

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

l = 0
count = 0

ans = 0
for r in range(N):
    if S[r] == '0':
        if r==0 or S[r-1]=='1':
            count += 1
    if count > K:
        while S[l] == '1':
            l += 1
        while S[l] == '0':
            l += 1
        count -= 1
    ans = max(ans, r-l+1)

print(ans)

Submission status: Accepted

Solution code:
t,s=open(0)
n,k=map(int,t.split())
i=0
for j in range(n):k-='1'>s[j]and'0'!=s[j-1];i+=k<0;k+=k<0and'1'>s[i-1]and'0'<s[i]
print(n-i)

Submission status: Accepted

Solution code:
def solve():
    N,K=map(int,input().split())
    S=input()
    s2=[]
    cp='1'
    cn=0
    count={'0':0, '1':0}
    for c in S:
        if cp != c:
            s2.append(cn)
            count[cp]+=1
            cp = c
            cn = 0
        cn += 1
    s2.append(cn)
    count[cp]+=1
    if cp=='0':
        s2.append(0)

    csum = [0]
    csumval = 0
    for v in s2:
        csumval += v
        csum.append(csumval)

    s2_len = len(s2)
    csum_len = len(csum)

    if count['0'] <= K:
        return csum[-1]

    #print('csumlen =',csumlen)
    ans=0
    for i in range(1,s2_len,2):
        ans1 = csum[min(i+K*2,s2_len)]-csum[i-1]
        #print(ans1,i,i+K*2)
        ans = max(ans,ans1)
    return ans

print(solve())

Submission status: Accepted

Solution code:
t,s=open(0)
n,k=map(int,t.split())
i=0
for j in range(n):
 k-='1'>s[j]and'0'!=s[j-1]
 if k<0:k+='1'>s[i]and'0'<s[i+1];i+=1
print(n-i)

Submission status: Accepted

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

if "0" not in S:
	print len(S)
	quit()
L=[]
if S[0]=="0": L.append(0)
for i,x in enumerate(S):
	if i==0:
		cnt=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
	prev=x
else:
	L.append(cnt)

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

LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)

K=min(K,len(L)/2)

ans=0
len_lsum=len(LSUM)
for l in range(0,len_lsum,2):
	r=l+2*K+1
	if r < len_lsum:
		ans=max(ans , LSUM[r]-LSUM[l])

print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [tuple(map(int, l.split())) for l in sys.stdin]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n,k = LI()
    s = [int(c) for c in S()]
    a = []
    if s[0] == 0:
        a.append(0)
    t = s[0]
    c = 1
    for b in s[1:]:
        if t == b:
            c += 1
        else:
            a.append(c)
            c = 1
            t = b
    a.append(c)
    l = len(a)
    if l // 2 <= k:
        return sum(a)

    r = t = sum(a[:k*2+1])
    if l % 2 == 0:
        a.append(0)
        l += 1
    g = k * 2 + 1
    for i in range(k*2+1,l-1,2):
        t -= a[i-g] + a[i-g+1]
        t += a[i] + a[i+1]
        if r < t:
            r = t

    return r


print(main())

Submission status: Accepted

Solution code:
def main():
	N, K = map(int, input().split())
	S = input()
	current = "1"
	current_len = 0
	nums = []
	for i in range(N):
		if S[i] != current:
			nums.append(current_len)
			current_len = 1
			current = S[i]
		else:
			current_len += 1

	nums.append(current_len)
	if len(nums) %2 == 0:
		nums.append(0)

	distance = 2*K+1
	ans = 0
	sums = [0]*(len(nums)+1)
	for i in range(len(nums)):
		sums[i+1] = sums[i] + nums[i]

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

	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

arr = []
cnt = 0
c = s[0]
for i in range(n):
    if c != s[i]:
        if c == '0':
            arr.append(-cnt)
        else:
            arr.append(+cnt)
        c = s[i]
        cnt = 1
    else:
        cnt += 1
if c == '0':
    arr.append(-cnt)
else:
    arr.append(+cnt)

# if the beginning of arr is negative, attach prefix 0
if arr[0] < 0:
    arr = [0] + arr

s_arr = [0]
for val in arr:
    s_arr.append(s_arr[-1] + abs(val))

max_v = -1
m = len(arr)
for i in range(0, m, 2):
    max_v = max(max_v, s_arr[min(m, i+2*k+1)] - s_arr[i])
print(max_v)

Submission status: Accepted

Solution code:
def main():
	N, K = map(int, input().split())
	S = input()
	current = "1"
	current_len = 0
	nums = []
	for i in range(N):
		if S[i] != current:
			nums.append(current_len)
			current_len = 1
			current = S[i]
		else:
			current_len += 1

	nums.append(current_len)
	if len(nums) %2 == 0:
		nums.append(0)

	distance = 2*K+1
	ans = 0
	left, right = 0, 0
	tmp = 0
	for i in range(0, len(nums), 2):
		next_left = i
		next_right = min(i+distance, len(nums))
		# move left
		while next_left > left:
			tmp -= nums[left]
			left += 1
		# move right
		while next_right > right:
			tmp += nums[right]
			right += 1
		ans = max(tmp, ans)

	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, S: str):
    ranlength = []
    lastBit = ""
    lastLength = 0
    for c in S:
        if lastBit == "":
            lastBit = c
            lastLength += 1
            continue
        if lastBit == c:
            lastLength += 1
            continue
        else:
            ranlength.append((lastLength, int(lastBit)))
            lastLength = 1
            lastBit = c
            continue
    ranlength.append((lastLength, int(lastBit)))
    count0 = 0
    length0 = 0
    end = 0
    for i in range(len(ranlength)):
        if count0 == K and ranlength[i][1] == 0:
            break
        if ranlength[i][1] == 0:
            count0 += 1
        length0 += ranlength[i][0]
        end = i
    # これで最初のKこの入れ替えでの長さが求まる
    nextLength = length0
    lastMax = length0
    begin = 0
    #print(begin, end, nextLength)
    while end + 1 < len(ranlength):
        nextLength += ranlength[end + 1][0]
        end += 1
        for i in range(end + 1, len(ranlength)):
            if ranlength[i][1] == 0:
                break
            else:
                nextLength += ranlength[i][0]
            end = i
        for i in range(begin, len(ranlength)):
            begin = i + 1
            nextLength -= ranlength[i][0]
            if ranlength[i][1] == 0:
                break
        lastMax = max(lastMax, nextLength)
        #print(begin, end, nextLength)
    #print(lastMax, begin, end)
    print(lastMax)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    # print(S)
    solve(N, K, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

arr = []
cnt = 0
comp = S[0]
for s in S:
    if s==comp:
        cnt += 1
    else:
        arr.append(cnt)
        cnt = 1
        comp = s
arr.append(cnt)

if len(arr)<3:
    print(sum(arr))
else:
    if S[0]=='1':
        L = (len(arr)+1)//2 - K +1
        l = 0
        tmp = sum(arr[2*l:2*(l+K)+1])
        ans = tmp
        for l in range(1, L):
            tmp = tmp - (arr[2*(l-1)]+arr[2*l-1]) + sum(arr[2*(l-1+K)+1 : min(2*(l+K)+1, len(arr))])
            ans = max(tmp, ans)
    else:
        L = (len(arr)+1)//2 - K + 1
        l = 0
        tmp = sum(arr[2*l:2*(l+K)])
        ans = tmp
        for l in range(1, L):
            tmp = tmp - sum(arr[max(0,2*l-3) : 2*l-1]) + sum(arr[2*(l+K-1): min(2*(l+K), len(arr))])
            ans = max(tmp, ans)
            
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, S):
    s1 = list(map(lambda x: len(x), filter(lambda x: x != '', S.split('0'))))
    s0 = list(map(lambda x: len(x), filter(lambda x: x != '', S.split('1'))))
    if len(s0) <= K:
        return N
    if S[0] == '0':
        s1.insert(0, 0)
    if S[-1] == '0':
        s1.append(0)
    s = []
    i = 0
    for i in range(len(s0)):
        s.append(s1[i])
        s.append(s0[i])
    s.extend(s1[i+1:])

    sa = [0]
    for v in s:
        sa.append(sa[-1]+v)
        
    ans = 0
    for i in range(0, len(sa), 2):
        if i+2*K+1 < len(sa):
            ans = max(ans, sa[i+2*K+1]-sa[i])
        elif i+2*K < len(sa):
            ans = max(ans, sa[i+2*K]-sa[i])
        else:
            break
      

    return ans


def main():
    N, K = read_int_n()
    S = read_str()
    rS = ''.join(['0' if c == '1' else '1' for c in S])
    print(max(slv(N, K, S), slv(N, K-1, rS)))

    # N = 20
    # K = random.randint(1, 10)
    # S = ''.join(random.choices('01', k=N))
    # rS = ''.join(['0' if c == '1' else '1' for c in S])
    # print(max(slv(N, K, S), slv(N, K-1, rS)))

if __name__ == '__main__':
    main()