Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
P = read_ints()


def ret_mean(X):
    return (X + 1) / 2




from numpy as np
P_mean = np.array([ret_mean(p) for p in P])
P_accum = np.zeros(N+1)
P_accum[1:] = P_mean.cumsum()

ans = 0
# print(P_accum)
for i in range(N - K + 1):
    j = i + K
    ans = max(ans, P_accum[j] - P_accum[i])
print(ans)


Fixed submission:
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
P = read_ints()


def ret_mean(X):
    return (X + 1) / 2


P_mean = [ret_mean(p) for p in P]

from itertools import accumulate
P_accum = [0] + list(accumulate(P_mean))

ans = 0
# print(P_accum)
for i in range(N - K + 1):
    j = i + K
    ans = max(ans, P_accum[j] - P_accum[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc153/tasks/abc153_e
# コイン問題の応用で解けそう
# ナップサック解法をあとでちゃんと確認

# INFで初期化したdpテーブルでコイン問題を解いて、ピッタリ勝てないときは最小コストにmin(B)を足す
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

dp = [INF] * (H + 1 + maxa)
dp[0] = 0

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)

# if dp[H] < INF:
#     print(dp[H])
#     exit()

print(min(dp[H:]))


Fixed submission:
# https://atcoder.jp/contests/abc153/tasks/abc153_e
# コイン問題の応用で解けそう
# ナップサック解法をあとでちゃんと確認

# INFで初期化したdpテーブルでコイン問題を解いて、ピッタリ勝てないときは最小コストにmin(B)を足す
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

dp = [INF] * (H + 1 + maxa)
dp[0] = 0

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)

# if dp[H] < INF:
#     print(dp[H])
#     exit()

print(min(dp[H:]))
Buggy python submission (verdict: Runtime Error):
print(['bust','win'][sum(map(int,input.split()))<22])

Fixed submission:
print(['bust','win'][sum(map(int,input().split()))<22])
Buggy python submission (verdict: Time Limit Exceeded):
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
S = read()[:-1]


def permutation_3to2(new3num: str):
    return (new3num[1:], new3num[0] + new3num[2])


passes = set()
set_2num = set()
passes.add(S[:3])
set_2num.add(S[:2])
tmp1, tmp2 = permutation_3to2(S[:3])
set_2num.add(tmp1)
set_2num.add(tmp2)
for c in S[3:]:
    for a, b in list(set_2num):
        tmp = a + b + c
        tmp1, tmp2 = permutation_3to2(tmp)
        set_2num.add(tmp1)
        set_2num.add(tmp2)
        passes.add(tmp)

print(len(passes))


Fixed submission:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
S = read()[:-1]


def permutation_3to2(new3num: str):
    return (new3num[1:], new3num[0] + new3num[2])


passes = set()
set_2num = set()
passes.add(S[:3])
set_2num.add(S[:2])
tmp1, tmp2 = permutation_3to2(S[:3])
set_2num.add(tmp1)
set_2num.add(tmp2)
for c in S[3:]:
    for a, b in list(set_2num):
        tmp = a + b + c
        tmp1, tmp2 = permutation_3to2(tmp)
        set_2num.add(tmp1)
        set_2num.add(tmp2)
        passes.add(tmp)

print(len(passes))
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc142/tasks/abc142_e
# このナップサックdpは面白い！
# 配るdpをイメージするとわかりやすい
# dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
# bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def as_bit(ls):
    # 開けられる宝箱をbitで示す
    ret = 0
    for l in ls:
        ret ^= 1 << (l - 1)
    return ret


from itertools import product
INF = 10**9
N, M = read_ints()
C = []
A = []
for _ in range(M):
    a, b = read_ints()
    A.append(a)
    c = read_ints()
    C.append(as_bit(c))

'''
dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。

更新則
dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i]) # i番目を取る
dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]) #i番目を取らない
∵配るDP。ナンプサックDPの重さの更新がbit演算に置き換わっただけ

初期条件&境界条件
dp[i][bit]=INF
dp[i][0]=0
'''

dp = [[INF] * (2 ** N) for _ in range(M + 1)]

for i in range(M + 1):
    dp[i][0] = 0

for i, bit in product(range(M), range(2 ** N)):
    dp[i + 1][bit | C[i]] = min(dp[i + 1][bit | C[i]], dp[i][bit] + A[i])
    dp[i + 1][bit] = min(dp[i + 1][bit], dp[i][bit])

ans = dp[-1][-1]
print(ans if ans != INF else -1)


Fixed submission:
# https://atcoder.jp/contests/abc142/tasks/abc142_e
# このナップサックdpは面白い！
# 配るdpをイメージするとわかりやすい
# dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
# bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def as_bit(ls):
    # 開けられる宝箱をbitで示す
    ret = 0
    for l in ls:
        ret ^= 1 << (l - 1)
    return ret


from itertools import product
INF = 10**9
N, M = read_ints()
C = []
A = []
for _ in range(M):
    a, b = read_ints()
    A.append(a)
    c = read_ints()
    C.append(as_bit(c))

'''
dp[i][bit] ... [0,i)の鍵を考慮したときに状態bitであるための最小の費用
bitは開けられる宝箱を2進数で示している。5(101)だったら、0,2の宝箱が開けられる。

更新則
dp[i+1][bit|C[i]] = min(dp[i+1][bit|C[i]], dp[i][bit] + A[i]) # i番目を取る
dp[i+1][bit] = min(dp[i+1][bit], dp[i][bit]) #i番目を取らない
∵配るDP。ナンプサックDPの重さの更新がbit演算に置き換わっただけ

初期条件&境界条件
dp[i][bit]=INF
dp[i][0]=0
'''

dp = [[INF] * (2 ** N) for _ in range(M + 1)]

for i in range(M + 1):
    dp[i][0] = 0

for i, bit in product(range(M), range(2 ** N)):
    dp[i + 1][bit | C[i]] = min(dp[i + 1][bit | C[i]], dp[i][bit] + A[i])
    dp[i + 1][bit] = min(dp[i + 1][bit], dp[i][bit])

ans = dp[-1][-1]
print(ans if ans != INF else -1)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc141/tasks/abc141_e
# https://www.slideshare.net/hcpc_hokudai/ss-121539419
# これのほうがいいかな？ https://sen-comp.hatenablog.com/entry/2020/01/16/174230

# 結局これが一番わかりやすい https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05

# zアルゴリズムをやるらしい


def z_algorithm(S: str):
    '''SとS[i]の最長共通接頭辞長 Z[i] の配列を返す O(len(S))'''
    Z = [-1] * len(S)  # -1で初期化 (-1が出てきたらおかしい！)
    Z[0] = len(S)
    i = 1  # 現在求めたいZ[i]の位置
    j = 0  # S[i:i+j]の文字列は先頭と一致している
    while i < len(S):
        while (i + j < len(S) and S[j] == S[i + j]):
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue
        k = 1
        while (k < j and k + Z[k] < j):  # ならば再利用可能
            # ∵kからZ[k]後がjより小さいということは同一文字列の終了がjを突き抜けないことが保証されている
            # →Z[k]のほうが必ず早く終了するので値はZ[i+k]の値はZ[k]になる
            Z[i + k] = Z[k]
            k += 1
        i += k  # 次のiはまだ埋まっていないところまで移動
        j -= k  # jも無駄な探索を避けるために移動分だけの幅減少に留める
        # jの働き後半がはみ出すときは確定させないで次の探索で確定できるようにするというだけ
    return Z


N = int(input())
S = input()
# まずzアルゴリズムを任意の開始地点に用いる
# ほしいデータ構造
# S[i:]とS[j:]の最長共通接頭辞長行列 M[i][j]
# これのうち重複していないなかでの最大値が答え。
# つまりmax{M[i][j] | i+M[i][j]<=j}

# i,jはあくまで相対位置なのでMを実際に構成しなくてもiを一つずつずらしてjを調べるということでおk
ans = 0
for i in range(N):  # 開始位置
    Z = z_algorithm(S[i:])
    for j in range(N - i):
        if Z[j] <= j:
            ans = max(ans, Z[j])
print(ans)


Fixed submission:
# https://atcoder.jp/contests/abc141/tasks/abc141_e
# https://www.slideshare.net/hcpc_hokudai/ss-121539419
# これのほうがいいかな？ https://sen-comp.hatenablog.com/entry/2020/01/16/174230

# 結局これが一番わかりやすい https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05

# zアルゴリズムをやるらしい


def z_algorithm(S: str):
    '''SとS[i]の最長共通接頭辞長 Z[i] の配列を返す O(len(S))'''
    Z = [-1] * len(S)  # -1で初期化 (-1が出てきたらおかしい！)
    Z[0] = len(S)
    i = 1  # 現在求めたいZ[i]の位置
    j = 0  # S[i:i+j]の文字列は先頭と一致している
    while i < len(S):
        while (i + j < len(S) and S[j] == S[i + j]):
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue
        k = 1
        while (k < j and k + Z[k] < j):  # ならば再利用可能
            # ∵kからZ[k]後がjより小さいということは同一文字列の終了がjを突き抜けないことが保証されている
            # →Z[k]のほうが必ず早く終了するので値はZ[i+k]の値はZ[k]になる
            Z[i + k] = Z[k]
            k += 1
        i += k  # 次のiはまだ埋まっていないところまで移動
        j -= k  # jも無駄な探索を避けるために移動分だけの幅減少に留める
        # jの働き後半がはみ出すときは確定させないで次の探索で確定できるようにするというだけ
    return Z


N = int(input())
S = input()
# まずzアルゴリズムを任意の開始地点に用いる
# ほしいデータ構造
# S[i:]とS[j:]の最長共通接頭辞長行列 M[i][j]
# これのうち重複していないなかでの最大値が答え。
# つまりmax{M[i][j] | i+M[i][j]<=j}

# i,jはあくまで相対位置なのでMを実際に構成しなくてもiを一つずつずらしてjを調べるということでおk
ans = 0
for i in range(N):  # 開始位置
    Z = z_algorithm(S[i:])
    for j in range(N - i):
        if Z[j] <= j:
            ans = max(ans, Z[j])
print(ans)
Buggy python submission (verdict: Runtime Error):
L, R = list(map(int, input().split()))
MOD = 2019
from itertools import product
ans = 2019
for i, j in product(range(L, R + 1), range(L, R + 1)):
    if i >= j:
        continue
    ans = min(ans, (i * j) % MOD)
    if ans == 0:
        break
print(ans)

Fixed submission:
# https://atcoder.jp/contests/abc133/tasks/abc133_c
# MODって掛け算でも分解できなかったっけ？って気づけばO(n)となり終わり?
# いや、O(n)だと2*10**9なのでpythonだと間に合わない！
# mod 2019 の計算結果は2019ごとに繰り返すことに気がつくと一気に計算が少なくなる

MOD = 2019  # これなにげに3の倍数だからいつも見たいなMODの演算が通用しない笑
L, R = list(map(int, input().split()))
# このコーナーケースに注意
if (R - L) >= MOD:
    print(0)
    exit()

# Lをなるべく0に近づける
L %= 2019
# RをなるべくLに近づけてみる
R %= 2019
if R <= L:
    R += MOD

ans = 2019
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        ans = min(ans, (i * j) % MOD)
print(ans)

Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc133/tasks/abc133_c
# MODって掛け算でも分解できなかったっけ？って気づけばO(n)となり終わり?
# いや、O(n)だと2*10**9なのでpythonだと間に合わない！
# mod 2019 の計算結果は2019ごとに繰り返すことに気がつくと一気に計算が少なくなる

MOD = 2019
L, R = list(map(int, input().split()))
if (R - L + 1) >= MOD:
    print(0)

baisuu = L // MOD
L = L - baisuu * MOD
R = R - baisuu * MOD

# print(L, R, baisuu)
att = []
for i in range(L, R + 1):
    att.append(i % 2019)
att.sort()
print(att[0] * att[1])
# https://atcoder.jp/contests/abc133/tasks/abc133_c
# MODって掛け算でも分解できなかったっけ？って気づけばO(n)となり終わり?
# いや、O(n)だと2*10**9なのでpythonだと間に合わない！
# mod 2019 の計算結果は2019ごとに繰り返すことに気がつくと一気に計算が少なくなる

MOD = 2019
L, R = list(map(int, input().split()))
if (R - L + 1) >= MOD:
    print(0)

baisuu = L // MOD
L = L - baisuu * MOD
R = R - baisuu * MOD

# print(L, R, baisuu)
att = []
for i in range(L, R + 1):
    att.append(i % 2019)
att.sort()
print(att[0] * att[1])


Fixed submission:
# https://atcoder.jp/contests/abc133/tasks/abc133_c
# MODって掛け算でも分解できなかったっけ？って気づけばO(n)となり終わり?
# いや、O(n)だと2*10**9なのでpythonだと間に合わない！
# mod 2019 の計算結果は2019ごとに繰り返すことに気がつくと一気に計算が少なくなる

MOD = 2019  # これなにげに3の倍数だからいつも見たいなMODの演算が通用しない笑
L, R = list(map(int, input().split()))
# このコーナーケースに注意
if (R - L) >= MOD:
    print(0)
    exit()

# Lをなるべく0に近づける
L %= 2019
# RをなるべくLに近づけてみる
R %= 2019
if R <= L:
    R += MOD

ans = 2019
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        ans = min(ans, (i * j) % MOD)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
D = list(map(int, input().split())).sort()
print(D[N // 2] - D[(N // 2) - 1])


Fixed submission:
N = int(input())
D = sorted(list(map(int, input().split())))
print(D[N // 2] - D[(N // 2) - 1])
Buggy python submission (verdict: Runtime Error):
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()

from math import log2

ans = 0.0
p_dice = 1 / N


def get_trial(i):
    # iは最初に出たサイコロの目
    ret = 0
    tmp = i
    while tmp < K:
        tmp *= 2
        ret += 1

    return ret


for i in range(N):
    ans += (1 / 2)**get_trial(i+1)

print(p_dice*ans)


Fixed submission:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()

from math import log2

ans = 0.0
p_dice = 1 / N


def get_trial(i):
    # iは最初に出たサイコロの目
    ret = 0
    tmp = i
    while tmp < K:
        tmp *= 2
        ret += 1

    return ret


for i in range(N):
    ans += (1 / 2)**get_trial(i+1)

print(p_dice*ans)
Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = '1' + read()
sum_0 = [0]

for s_new, s_next in zip(S[:-2], S[1:-1]):
    # print(s_new, s_next)
    if s_new == '1' and s_next == '0':
        sum_0.append(sum_0[-1] + 1)
    else:
        sum_0.append(sum_0[-1])

S = S[1:-1]
# print(sum_0)

left = 0  # 左端初期値
ans = 1  # 解初期値
right = 1

# right-leftが答え
# sum_0[right]-sum0[left]がKを超えたらleftを進める
# print(sum_0)
# しゃくとり法で溶けそうでは？
for left in range(N-1):
    while (True):
        right += 1
        if sum_0[right + 1] - sum_0[left] > K:
            right -= 1
            break
        if right == N - 1:
            break
        # print(left, right, sum_0[right + 1] - sum_0[left])

    # print(left, right)
    ans = max(ans, right - left+1)  # 大きい方に更新
    # print(ans)

print(ans)


Fixed submission:
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
S = read()[:-1]


# 偶数番目に0の個数を格納するようなデータ構造を構築する
num_cnts = []
now = '1'  # 0から考慮する
cnt = 0
for s in S:
    if s == now:
        cnt += 1
    if s != now:  # もしいまカウントしている文字と異なったらカウントを格納して、カウントをリセットする。
        num_cnts.append(cnt)
        now = s
        cnt = 1
num_cnts.append(cnt)
# もしSが0で終わっていたら0個の1を付け足す
if S[-1] == '0':
    num_cnts.append(0)

assert len(num_cnts) % 2 == 1, '奇数個じゃない！'

# 累積和で実装
from itertools import accumulate
num_accums = [0]+list(accumulate(num_cnts))

# 最大長の探索
add = min(2*K+1, len(num_cnts))  # Kで指定するよりも短い場合はそっちに合わせる
ans = 1

# print(num_cnts)
for left in range(0, len(num_cnts) - add+1, 2):
    right = left + add
    ans = max(ans, num_accums[right] - num_accums[left])
    # print(left, right, ans)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.readline


def readln():
    return list(map(int, read().split()))


N, Q = readln()
S = input()

L = []
R = []
for _ in range(Q):
    a, b = readln()
    L.append(a-1)  # indexでアクセスできるように
    R.append(b)

import re

for l, r in zip(L, R):
    s = S[l:r]
    ans = 0
    for s1, s2 in zip(s[:-1], s[1:]):
        if s1 == 'A' and s2 == 'C':
            ans += 1
    print(ans)


Fixed submission:
import sys
read = sys.stdin.readline


def readln():
    return list(map(int, read().split()))


N, Q = readln()
S = input()

L = []
R = []
for _ in range(Q):
    a, b = readln()
    L.append(a-1)  # indexでアクセスできるように
    R.append(b-1)

AC_count = [0] * N  # Sのidxと対応、そこまでにACが何回出てきたか
cnt = 0

for i, (s1, s2) in enumerate(zip(S[:-1], S[1:])):
    if s1 == 'A' and s2 == 'C':
        cnt += 1

    AC_count[i+1] = cnt

for l, r in zip(L, R):
    print(AC_count[r]-AC_count[l])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.readline


def readln():
    return list(map(int, read().split()))


N, Q = readln()
S = input()

L = []
R = []
for _ in range(Q):
    a, b = readln()
    L.append(a-1)  # indexでアクセスできるように
    R.append(b)

import re

for l, r in zip(L, R):
    s = S[l:r]
    regex = re.compile('AC')
    print(len(regex.findall(s)))


Fixed submission:
import sys
read = sys.stdin.readline


def readln():
    return list(map(int, read().split()))


N, Q = readln()
S = input()

L = []
R = []
for _ in range(Q):
    a, b = readln()
    L.append(a-1)  # indexでアクセスできるように
    R.append(b-1)

AC_count = [0] * N  # Sのidxと対応、そこまでにACが何回出てきたか
cnt = 0

for i, (s1, s2) in enumerate(zip(S[:-1], S[1:])):
    if s1 == 'A' and s2 == 'C':
        cnt += 1

    AC_count[i+1] = cnt

for l, r in zip(L, R):
    print(AC_count[r]-AC_count[l])
Buggy python submission (verdict: Time Limit Exceeded):
def readln():
    return list(map(int, input().split()))


A, B = readln()

ans = []
for i in range(40):
    power = 1 << i  # i桁目について考える
    bit_count_of_1 = sum(1 for a in range(A, B + 1) if a & power != 0)
    if bit_count_of_1 % 2 == 1:
        ans.append(1)
    else:
        ans.append(0)

ans_print = 0
for i, a in enumerate(ans):
    ans_print += 2 ** i if a == 1 else 0

print(ans_print)


Fixed submission:
def readln():
    return list(map(int, input().split()))


A, B = readln()


A_isodd = []  # 奇数の桁は1
B_isodd = []  # 奇数の桁は1
# 1の偶奇
tmp = (A) % 4
if (tmp == 2)or(tmp == 3):
    A_isodd.append(1)
else:
    A_isodd.append(0)
tmp = (B+1) % 4
if (tmp == 2)or(tmp == 3):
    B_isodd.append(1)
else:
    B_isodd.append(0)


for i in range(1, 40):  # 各桁につい
    tmp = (A) % 2 ** (i + 1)
    if (tmp > 2 ** (i)) and (tmp % 2 == 1):
        A_isodd.append(1)
    else:
        A_isodd.append(0)
    tmp = (B + 1) % 2 ** (i + 1)
    if (tmp > 2 ** (i)) and (tmp % 2 == 1):
        B_isodd.append(1)
    else:
        B_isodd.append(0)

# print(A_isodd)
# print(B_isodd)

ans = []
for a, b in zip(A_isodd, B_isodd):
    if a == b:
        ans.append(0)
    else:
        ans.append(1)

ans_print = 0
for i, a in enumerate(ans):
    ans_print += 2 ** i if a == 1 else 0

print(ans_print)