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:
import sys
# import bisect
# import math
# import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    # 入力の取得
    n, k = ip.IL()
    s = input() + "2"

    # 連続して並んでいる数と要素をリストにする
    zeros = []
    ones = []

    # 始まり（start）と要素数(cnt)
    cnt = 0
    start = 1

    for x in s:
        # 1から0に変わるところ
        if start == 1 and x != "1":
            ones += [cnt]
            cnt = 1
            start = 0
        # 0から1に変わるところ
        elif start == 0 and x != "0":
            zeros += [cnt]
            cnt = 1
            start = 1
        # 前と同じところ
        else:
            cnt += 1

    # 端が0のときは1で埋める
    if len(zeros) == len(ones):
        ones += [0]

    ones += [0]
    
    # 最初のケース
    ans = sum(ones[:k+1]) + sum(zeros[:k])
    n_ans = ans

    for i in r(len(zeros) - k):
        # 尺取り虫擬態探索法
        n_ans = n_ans + ones[k+1+i] + zeros[k+i] - ones[i] - zeros[i]
        ans = max(ans, n_ans)

    p(ans)


main()

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
s = input()
a = []
cnt = 0
now = s[0]
for ss in s:
    if ss == now:
        cnt += 1
    else:
        a.append(cnt)
        cnt = 1
        now = ss
a.append(cnt)

a = [0]*(1-int(s[0])) + a + [0]*(1-int(s[-1]))
la = len(a)
kk = 2*k+1
if la == 1 or la <= kk:
    print(n)
    exit()
    
ac = [0] + list(accumulate(a))
ans = -float('inf')
for i in range(kk, la+1, 2):
    ans = max(ans, ac[i] - ac[i-kk])
print(ans)

Submission status: Accepted

Solution code:
"""
map(int,input().split())

"""
N,K = map(int,input().split())
S = input()
s = []
for i in range(0,len(S)):
    s.append(S[i])


Nums = []
now = 1
cnt = 0
for i in range(0,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
ans = 0
W = []

wsm = 0
for i in range(0,len(Nums)):
    wsm = Nums[i] + wsm
    W.append(wsm)

W.append(wsm)
W.append(wsm)

for i in range(0,len(Nums),2):
    tmp = 0
    left = i
    if left == 0:
        left = 1
    right = min(i + Add , len(Nums))
    if left-1<=0:
        tmp = W[right-1]
    else:
        tmp = W[right-1] - W[left-1]
    #print(tmp,left,right)
    ans = max(tmp,ans)
if  N == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

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

# 1-0-1-0-1の形式で集計する
count=0
now=1
num_list=[]
for c_i in s:
    if c_i == now:
        count+=1
    else:
        num_list.append(count)
        count=1
        now=1-now
num_list.append(count)

# 最後が0のグループだと都合が悪い
if len(num_list)%2==0:
    num_list.append(0)

# 累積和を使って部分列の合計の最大値を求める
max_len=0
now_sum=0
left=0
right=0

for i in range(0,len(num_list),2):
    nextleft=i
    nextright=min(len(num_list),i+2*k+1)

    while left<nextleft:
        now_sum-=num_list[left]
        left+=1
    while right<nextright:
        now_sum+=num_list[right]
        right+=1
    max_len=max(max_len,now_sum)
    
print(max_len)

Submission status: Accepted

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

l, accum = len(s), []
i = 0
while i < l:
    ch = s[i]
    count = 0
    while i < l and s[i] == ch:
        count += 1
        i += 1
    accum.append(count)

l = len(accum)
for i in range(1, l): accum[i] += accum[i-1]

mx = accum[min(2*k - (1-int(s[0])), l-1)]
i = 1
while l > 1:
    idx = min(2*k - (1-int(s[0])) + 2*i, l-1)
    mx = max(accum[idx] - accum[2*(i-1)+int(s[0])], mx)
    if idx >= l-1: break
    i += 1
print(mx)

Submission status: Accepted

Solution code:
import sys
# import bisect
# import math
# import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    n, k = ip.IL()
    s = input() + "2"

    zeros = []
    ones = []
    cnt = 0
    start = 1
    for x in s:
        if start == 1 and x != "1":
            ones += [cnt]
            cnt = 1
            start = 0
        elif start == 0 and x != "0":
            zeros += [cnt]
            cnt = 1
            start = 1
        else:
            cnt += 1

    if len(zeros) == len(ones):
        ones += [0]

    ones += [0]

    ans = sum(ones[:k+1]) + sum(zeros[:k])
    n_ans = ans

    for i in r(len(zeros) - k):
        n_ans = n_ans + ones[k+1+i] + zeros[k+i] - ones[i] - zeros[i]
        ans = max(ans, n_ans)

    p(ans)


main()

Submission status: Accepted

Solution code:
"""
方針:累積和(0初期化配列のやりかた), 最後が0終わりのケア, 累積和の範囲
"""

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

# まず'1'の塊, '0'の塊をカウントしていく
L = [0]
tmp = '1'
for i in range(N):
    if tmp != S[i]:
        L.append(1)
    else:
        L[-1] += 1
    tmp = S[i]
# こうすることでLのカウントは必ず'1'の文字を数え上げた値からスタートする
# 最初が'0'ならLは[0('1'は存在していないから0), 0を数えあげた値, hogehoge]って進んでいく

# 最後が'0'のときをケアする必要がある
if tmp == '0':
    L.append(0)  # 最後が'0'であり'1'が存在しない、つまり0を追加する
# Lが完成した

# print(len(L)), Lは絶対に奇数個になっている。'1'カウントスタート, '1'カウントエンド

# 最速で終わらせる方法の判定
M = len(L)
if int(M/2) <= K:
    print(N)
    exit()

X = [0 for _ in range(M+1)]

for i in range(M):
    X[i+1] = X[i] + L[i]
# Xが完成した

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

print(ans)

Submission status: Accepted

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

left = 0
right = 0
ans = 0
remain = K
if S[0] == "0":
    remain -= 1

while left < N:
    while right < N and remain >= 0:
        if S[right] == "1" and right + 1 < N and S[right + 1] == "0":
            remain -= 1
        right += 1
    ans = max(ans, right - left)
    if left == right:
        right += 1
    else:
        if S[left] == "0" and left + 1 < N and  S[left + 1] == "1":
            remain += 1
    left += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
# import bisect
# import math
# import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    n, k = ip.IL()
    s = input()

    zeros = []
    ones = [0]
    prev = "1"
    for x in s:
        if x == "1":
            if prev == "0":
                ones += [1]
            else:
                ones[-1] += 1
        else:
            if prev == "1":
                zeros += [1]
            else:
                zeros[-1] += 1
        prev = x
    ones += [0]

    tmp = sum(zeros[0:k]) + sum(ones[0:k+1])

    ans = tmp
    for i in r(0, len(zeros) - k):
        tmp += zeros[i+k] - zeros[i] + ones[i+k+1] - ones[i]
        ans = max(tmp, ans)

    p(ans)


main()

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
s = input()
change = []
leng = len(s)
flag = ''
ans = 0
w = 2*k+1

if s[0] == '0':
  change.append(0)
  
for i in range(leng):
  if s[i] != flag:
    flag = s[i]
    change.append(i)

change.append(leng)

if s[-1] == '0':
  change.append(leng)
leng = len(change)

if leng <= w:
  print(n)
  exit()

for i in range(0,leng-w,2):
  ans = max(ans,change[i+w]-change[i])
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
 
N, K = map(int, input().split())
S = input()
S = [int(s) for s in S]
 
nums = list()
now = 1
count_tmp = 0
for i in range(N):
    if S[i] == now:
        count_tmp += 1
    else:
        nums.append(count_tmp)
        now = 1 - now
        count_tmp = 1
if count_tmp > 0:
    nums.append(count_tmp)
if len(nums) % 2 == 0:
    nums.append(0)
 
sums = list(accumulate([0] + nums))
 
max_add = 2 * K
ans = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(i + max_add, len(nums) - 1)
    tmp = sums[right + 1] - sums[left]
    ans = max(tmp, ans)
print(ans)

Submission status: Accepted

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

ones = [0]
zeros = []
flag = '1'
for s in S:
    if s == '1':
        if flag == '1':
            ones[-1] += 1
        else:
            ones.append(1)
    else:
        if flag == '1':
            zeros.append(1)
        else:
            zeros[-1] += 1
    flag = s
ones.append(0)

tmp = sum(ones[0 : K + 1]) + sum(zeros[0 : K])
ans = tmp
for i in range(len(zeros) - (K + 1) + 1):
    tmp = tmp + ones[i + K + 1] - ones[i] + zeros[i + K] - zeros[i]
    ans = max(ans, tmp)
    
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
S = input()
 
zeros = []
ones = [0]
# Sが0始まりの時は、それを挟むための1が必要なので、予め入れておく
# 1始まりの時は、これに+= 1するので問題なし
 
prev = '1'
for c in S:
    if c == '1':
        if prev == '0':
            ones.append(1)
        else:
            ones[-1] += 1
    else: #c == '0'
        if prev == '1':
            zeros.append(1)
        else:
            zeros[-1] += 1
    prev = c
ones.append(0)
# Sが0終わりの時は、それを挟むための1が必要なので、最後に付け加えておく
# 1終わりの時は不要だが、maxをとるので0を入れておいても影響はない

tmp = sum(zeros[0:K]) + sum(ones[0:K+1])
#　初期値として、最初の区間の和を計算しておけば、
# あとは先頭と最後尾を+-するだけで累積和を求められる
ans = tmp
for i in range(0,len(zeros)-K):
    tmp += zeros[i+K] - zeros[i] + ones[i+K+1] - ones[i]
    ans = max(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def Solve():
    N,K=na()
    S=input()
    l=[]
    N=len(S)
    #print(len(S))
    if(S[0]=="0"):
        #print("00")
        l.append(0)
    t=S[0]
    ct=1
    #print("aa")
    #print(S)
    #print(S[0],S[1],S[2])
    for b in S[1:]:
        #print(b)
        if(t!=b):
            l.append(ct)
            ct=1
            t=b
        else:
            ct+=1
    #print("bb")
    l.append(ct)
    len_l=len(l)
    if(len_l//2 <= K):
        return sum(l)
    ans = res = sum(l[:2*K+1])
    
    if(len_l%2==0):
        l.append(0)
        len_l+=1
    g = K * 2 + 1
    for i in range(K*2+1,len_l-1,2):
        ans -= l[i-g] + l[i-g+1]
        ans += l[i] + l[1+i]
        if(res<ans):
            res=ans
    #print(S)
    #print(l)
    #print(len_l)
    return res

print(Solve())

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
 
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = str(input().strip())
    S += 'x'
 
    A = []
    S0 = S[0]
    cnt = 0
    for s in S:
        if S0 == s:
            cnt += 1
        else:
            A.append(cnt)
            cnt = 1
            S0 = s
 
 
    n = len(A) // 2
    if len(A) % 2 == 1 and S[0] == '0':
        n += 1
 
    if n <= K:
        return sum(A)
 
    if S[0] == '0':
        A = [0] + A
    if S[-2] == '0':
        A = A + [0]
    A = [0] + list(accumulate(A))
 
    ans = 0
    for i in range(0, len(A) - 2*K, 2):
        ans = max(ans, A[i + 2*K + 1] - A[i])
 
    return ans
 
 
if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

for i in range(len(S)):
	if i==0:
		if S[0]=="0":
			line.append(0)
		line.append(1)
	else:
		if S[i-1]!=S[i]:
			line.append(1)
		else:
			line[-1]+=1
c=0
for i in range(len(line)):

	if i==0:
		if i+2*K+1<=len(line):
			s=sum(line[i:2*K+1])
			c=s
		else:
			s=sum(line[i:])
			c=s
	elif i%2==0:
		if i+2*K+1<=len(line):
			s=s-line[i-2]-line[i-1]+line[i+2*K-1]+line[i+2*K]
			c=max(c,s)
		else:
			c=max(c,sum(line[i:]))
			break
print(c)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
S = input()
S = [int(s) for s in S]

# 0, 1 が連続して何回出現するかカウント
# はじめを必ず 1 はじめにしてしまう？
# 端は全て 0 の個数でまとめてしまう
nums = list()
now = 1
count_tmp = 0
for i in range(N):
    if S[i] == now:
        count_tmp += 1
    else:
        nums.append(count_tmp)
        now = 1 - now
        count_tmp = 1
if count_tmp > 0:
    nums.append(count_tmp)
# 何がなんでも 1 0 1 0 1 で終わらせたい
# 始まりは 1 始まりになってるので、0 終わりの場合は len(nums) が偶数となる
if len(nums) % 2 == 0:
    nums.append(0)

# nums の累積和
# nums 内の i から j までの和を sums[j] - sums[i] で表したいので [0] を先頭に足す
sums = list(accumulate([0] + nums))

# 1 0 1 0 .... 1 で終わっているので、 0 の個数を表す部分のみ見ればよい
max_add = 2 * K  # 最大で追加して取れる区間
ans = 0
for i in range(0, len(nums), 2):
    left = i
    right = min(i + max_add, len(nums) - 1)
    # nums の left から right までの和
    tmp = sums[right + 1] - sums[left]
    ans = max(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())
S = str(input())

L = [0]

tmp = "1"

seq = 0
for i in range(n):
    if tmp != S[i]:
        L.append(1)
    else:  # 文字が連続してたらインクリメントする
        L[-1] += 1
    tmp = S[i]
if tmp == '0':
    L.append(0)  # この0の意味は、最後の文字が'0'で終わっている=それに続く'1'の個数が0という意味

M = len(L)
if math.ceil(M/2) <= k:
    # '0'が連続している箇所はMの半分(切り上げ)だけ。それより多くの回数の魔法が使えるなら全てを'1'に変えられる
    print(n)
    exit()
X = [0 for i in range(M+1)]
for i in range(M):
    X[i+1] = L[i]+X[i]  # 累積和

ans = 0
for i in range(0, M-k*2, 2):
    ans = max(ans, X[i+k*2+1]-X[i])
print(ans)

"""
最初が0か1かで奇数番目を使うか偶数番目を使うか変わる
"""

"""
if k >= len(combined):
    print(len(S))
    exit()
初めて書いた時もこんなこと書いてる。

"""

Submission status: Accepted

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

left = 0
right = 0
ans = 0
remain = K
S += "?"
if S[0] == "0":
    remain -= 1

while left < N:
    while right < N and remain >= 0:
        if S[right] == "1" and S[right + 1] == "0":
            remain -= 1
        right += 1
    ans = max(ans, right - left)
    if left == right:
        right += 1
    else:
        if S[left] == "0" and S[left + 1] == "1":
            remain += 1
    left += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def Solve():
    N,K=na()
    S=[int(d) for d in input()]
    l=[]
    N=len(S)
    if(S[0]==0):
        l.append(0)
    b=S[0]
    ct=1
    for i in S[1:]:
        if(b!=i):
            l.append(ct)
            ct=1
            b=i
        else:
            ct+=1
    l.append(ct)
    len_l=len(l)
    if(len_l//2 <= K):
        return sum(l)
    ans = res = sum(l[:2*K+1])
    
    if(len_l%2==0):
        l.append(0)
        len_l+=1
    g = K * 2 + 1
    for i in range(K*2+1,len_l-1,2):
        ans -= l[i-g] + l[i-g+1]
        ans += l[i] + l[1+i]
        if(res<ans):
            res=ans
    #print(S)
    #print(l)
    #print(len_l)
    return res

print(Solve())

Submission status: Accepted

Solution code:
import numpy as np

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

ones = [len(x) for x in s.replace('0', ' ').split()]
zeros = [len(x) for x in s.replace('1', ' ').split()]

if s[0]=='0':
  ones = [0] + ones
if s[-1]=='0':
  ones = ones + [0]
  
ones = np.array(ones)
zeros = np.array(zeros)

if k >= len(zeros):
  result = n
else: 
  result = [
    np.sum(ones[i:i+k+1]) + np.sum(zeros[i:i+k])
    for i in range(len(zeros)-k+1)]
  result = max(result)

print(result)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
S = input()
binary = []
one = []
zero = []
tmp_z = 0
tmp_o = 0
zeroflag = (S[0]=="0")
saigozero = (S[-1]=="0")
for i,s in enumerate(S):
    if s=="0":
        tmp_z += 1
        if not zeroflag:
            one.append(tmp_o)
            tmp_o=0
            zeroflag=True
    if s =="1":
        tmp_o+=1
        if zeroflag:
            zero.append(tmp_z)
            tmp_z=0
            zeroflag=False
if tmp_z!=0:
    zero.append(tmp_z)
if tmp_o!=0:
    one.append(tmp_o)

zeroflag = (S[0]=="0")
saigozero = (S[-1]=="0")

if zeroflag:
    one = [1] + one
if saigozero:
    one.append(1)
    
one_sum = [0]*(len(one)+1)
zero_sum = [0]*(len(zero)+1)
for i in range(len(one)):
    one_sum[i+1] = one_sum[i]+one[i]
for i in range(len(zero)):
    zero_sum[i+1]=zero_sum[i]+zero[i]
    


if len(zero)<=k:
    print(len(S))
else:
    ans = 0
    
    for i in range(len(zero)-k + 1):
        if zeroflag and i==0:
#             tmp = sum(zero[i:i+k])+sum(one[i:i+k+1]) -1
            tmp = zero_sum[i+k]-zero_sum[i]+one_sum[i+k+1]-one_sum[i]-1
        elif saigozero and i==len(zero)-k:
            tmp = zero_sum[i+k]-zero_sum[i]+one_sum[i+k+1]-one_sum[i]-1
        else:
            tmp = zero_sum[i+k]-zero_sum[i]+one_sum[i+k+1]-one_sum[i]
        ans = max(ans,tmp)
    print(ans)

Submission status: Accepted

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

X = [] #直立 0
Y = [0] #逆立ち 1

prev = '1'
for c in S:
    if c == '1':
        if prev == '0':
            Y.append(1)
        else:
            Y[-1] += 1
    else: #c == '0'
        if prev == '1':
            X.append(1)
        else:
            X[-1] += 1
    prev = c
Y.append(0)

tmp = sum(X[0:K]) + sum(Y[0:K+1])
ans = tmp
for i in range(0,len(X)-K):
    tmp += X[i+K] - X[i] + Y[i+K+1] - Y[i]
    ans = max(tmp,ans)

print(ans)