Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


X, Y, A, B, C = list(map(int, sys.stdin.buffer.readline().split()))
P = list(map(int, sys.stdin.buffer.readline().split()))
Q = list(map(int, sys.stdin.buffer.readline().split()))
R = list(map(int, sys.stdin.buffer.readline().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

ps = sum(P[:X])
qs = sum(Q[:Y])
r_cum = cumsum(R)

x = X - 1
y = Y - 1

ans = ps + qs
# 何個着色するか
for cnt in range(1, min(X + Y, C) + 1):
    if x >= 0 and y >= 0 and P[x] < Q[y] or y < 0:
        ps -= P[x]
        x -= 1
    elif x >= 0 and y >= 0 and P[x] > Q[y] or x < 0:
        qs -= Q[y]
        y -= 1
    else:
        assert False
    s = r_cum[cnt - 1] + ps + qs
    ans = max(ans, s)
print(ans)


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


X, Y, A, B, C = list(map(int, sys.stdin.buffer.readline().split()))
P = list(map(int, sys.stdin.buffer.readline().split()))
Q = list(map(int, sys.stdin.buffer.readline().split()))
R = list(map(int, sys.stdin.buffer.readline().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

ps = sum(P[:X])
qs = sum(Q[:Y])
r_cum = cumsum(R)

x = X - 1
y = Y - 1

ans = ps + qs
# 何個着色するか
for cnt in range(1, min(X + Y, C) + 1):
    if x >= 0 and y >= 0 and P[x] < Q[y] or y < 0:
        ps -= P[x]
        x -= 1
    else:
        qs -= Q[y]
        y -= 1
    s = r_cum[cnt - 1] + ps + qs
    ans = max(ans, s)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))
    return ret


# A = []
# for _ in range(N):
#     import random
#     A.append(random.randint(1, 3))
# ans = test(A)
# print(ans)


# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 何個続くかを持つ
counts = []
n = None
cnt = 0
for a in A:
    if n != a:
        n = a
        cnt = 0
        counts.append((n, 0))
    cnt += 1
    counts[-1] = (n, cnt)

while len(counts) >= 2 or counts[0][1] > 1:
    counts = convert(counts)
print(counts[0][0])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))

    n = None
    count = 0
    filtered = []
    for a, cnt in ret:
        if a != n:
            n = a
            count = 0
            filtered.append((n, 0))
        count += cnt
        filtered[-1] = (n, count)
    return filtered

#
# A = []
# for _ in range(N):
#     import random
#
#     A.append(random.randint(0, 2))
# ans = test(A)
# print(ans)

# cnt2[n]: n! が 2 で何回割れるか
cnt2 = []
cnt = 0
for n in range(N + 10):
    while n >= 2 and n % 2 == 0:
        n //= 2
        cnt += 1
    cnt2.append(cnt)

# 0, 1, 2 だけにする
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
# 1が入ってるとき、2は0と同一視できる
if 1 in A:
    for i in range(len(A)):
        if A[i] == 2:
            A[i] = 0
mod = 2 if 1 in A else 4

ans = 0
n = len(A) - 1
for r in range(len(A)):
    cnt = cnt2[len(A) - 1] - cnt2[r] - cnt2[n - r]
    # cnt = math.factorial(n) // math.factorial(r) // math.factorial(n - r)
    if cnt == 0:
        ans += A[r]
        ans %= mod
    # print(n, r, cnt)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = list(map(int, list(sys.stdin.buffer.readline().decode().rstrip())))


def toint(l, r):
    return int(''.join(map(str, S[l:r])))


def test():
    ans = 0
    for l, r in itertools.combinations_with_replacement(range(N), r=2):
        s = toint(l, r + 1)
        ans += s % P == 0
    print(ans)


def solve25():
    ret = 0
    for d in range(N):
        if S[d] % P == 0:
            ret += d + 1
    return ret


# 10 mod P で割れない
if P in [2, 5]:
    ans = solve25()
    print(ans)
    exit()

# test()


def to_index(i, p):
    if i == 0:
        return p % P
    return (p - toint(1, i + 1)) * pow(pow(10, i, P), P - 2, P) % P


mod_counts = [0] * P
ans = 0
for i, c in enumerate(S):
    mod_counts[to_index(i, c)] += 1
    ans += mod_counts[to_index(i, 0)]
print(ans)


Fixed submission:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def toint(l, r):
    return int(''.join(map(str, S[l:r])))


def test():
    ans = 0
    for l, r in itertools.combinations_with_replacement(range(N), r=2):
        s = toint(l, r + 1)
        ans += s % P == 0
    print(ans)


def solve25():
    ret = 0
    for d in range(N):
        if S[d] % P == 0:
            ret += d + 1
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = list(map(int, list(sys.stdin.buffer.readline().decode().rstrip())))

# 10 mod P で割れない
if P in [2, 5]:
    ans = solve25()
    print(ans)
    exit()

# test()

powers = []
p = 1
for _ in range(N):
    powers.append(p)
    p = p * 10 % P
# int(S[1:1]), int(S[1:2]), int(S[1:3]), ...
s_additions = [0]
s = 0
for i in range(1, N):
    s = (s * 10 + S[i]) % P
    s_additions.append(s)
invs = mod_invs(max=P - 1, mod=P)


def to_index(i, p):
    # もともと x だったのが、i 番目で p になっているときの x を返す
    if i == 0:
        return p % P
    return (p - s_additions[i]) * invs[powers[i]] % P


mod_counts = [0] * P
ans = 0
for i, c in enumerate(S):
    mod_counts[to_index(i, c)] += 1
    ans += mod_counts[to_index(i, 0)]
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

ans = (N+1) // 2
print(ans
     )

Fixed submission:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
print((N +1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

# ピッタリ払う
dp0 = [INF] * (N + 1)
# 1 多く払う
dp1 = [INF] * (N + 1)

dp0[0] = 0
dp1[0] = 1
for i, c in enumerate(S):
    dp0[i + 1] = min(dp0[i] + int(c), dp1[i] + 10 - int(c))
    dp1[i + 1] = min(dp0[i] + int(c) + 1, dp1[i] + 10 - int(c) - 1)
# print(dp0)
# print(dp1)
print(dp0[-1])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = sys.stdin.buffer.readline().decode().rstrip()

S = []
T = []
for c in N:
    S.append(int(c))
    T.append(9 - int(c))
T[-1] += 1
i = len(T) - 1
while T[i] == 10:
    T[i] = 0
    T[i - 1] += 1
    i -= 1

N = len(S)

# maekaramiteku
# dp[i][j]: i まで見て最小の答え、反転してるかどうか
dp = [[IINF, IINF] for _ in range(N + 1)]
dp[0][0] = 0
dp[0][0] = 0
for i in range(N):
    # 1 使って反転できる
    dp[i + 1][0] = min(dp[i][0] + S[i], dp[i][1] + 1 + S[i])
    dp[i + 1][1] = min(dp[i][1] + T[i], dp[i][0] + 1 + T[i])

print(min(dp[-1]))
Buggy python submission (verdict: Runtime Error):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N , K = list(map(int, sys.stdin.buffer.readline().split()))
P = list(map(int, sys.stdin.buffer.readline().split()))

P = np.array(P, dtype=float)
E = (P + 1) / 2
cs = E.cumsum()


ans = (cs[K:] - cs[:-K]).max()
ans = max(ans, cs[K - 1])
print(ans)


Fixed submission:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
P = list(map(int, sys.stdin.buffer.readline().split()))

P = np.array(P, dtype=float)
E = (P + 1) / 2
cs = E.cumsum()

ans = cs[K - 1]
if K < N:
    ans = max(ans, (cs[K:] - cs[:-K]).max())
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


R1, C1, R2, C2 = list(map(int, sys.stdin.buffer.readline().split()))


# 解説
# ある要素に注目して残りを選ぶ数を数えると分かる
# ncr(n, r) == ncr(n-1,r) + (n-1,r-1)
# nhr(n, r) == sum([nhr(n-1,k) for k in range(r)])

# g(r, c) を f(i, j) (0<=i<=r, 0<=j<=c) の総和とすると
# g(R2, C2) - g(R1-1, C2) - g(R2, C1-1) + g(R1-1, C1-1)

def f(n, r):
    return comb(n + r, r, exact=True)


# @debug
def g(r, c):
    # ret = 0
    # for i in range(1, c + 2):
    #     ret += f(r, i)
    #     ret %= MOD

    # f(r,k) (k=[1,c+1]) の和
    return f(r + 1, c + 1) - f(r, 0)


ans = g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)
ans %= MOD
print(ans)


Fixed submission:
import os
import sys


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


R1, C1, R2, C2 = list(map(int, sys.stdin.buffer.readline().split()))

comb = Combination(max=10 ** 6 * 2 + 100, mod=MOD)


# 解説
# ある要素に注目して残りを選ぶ数を数えると分かる
# ncr(n, r) == ncr(n-1,r) + (n-1,r-1)
# nhr(n, r) == sum([nhr(n-1,k) for k in range(r)])

# g(r, c) を f(i, j) (0<=i<=r, 0<=j<=c) の総和とすると
# g(R2, C2) - g(R1-1, C2) - g(R2, C1-1) + g(R1-1, C1-1)

def f(n, r):
    return comb.ncr(n + r, r)


# @debug
def g(r, c):
    ret = 0
    for i in range(1, c + 2):
        ret += f(r, i)
        ret %= MOD
    return ret


ans = g(R2, C2) - g(R1 - 1, C2) - g(R2, C1 - 1) + g(R1 - 1, C1 - 1)
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, N = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

# dp[h]: 体力を h にするのに必要な魔力の合計の最小値
dp = [INF] * (H + 1)
dp[H] = 0
for a, b in AB:
    for h in reversed(range(H + 1)):
        dp[max(0, h - a)] = min(dp[h] + b, dp[max(0, h - a)])
print(dp[0])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, N = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

# dp[h]: 体力を h にするのに必要な魔力の合計の最小値
dp = [INF] * (H + 1)
dp[H] = 0
for a, b in AB:
    for h in reversed(range(H + 1)):
        dp[max(0, h - a)] = min(dp[h] + b, dp[max(0, h - a)])
print(dp[0])
Buggy python submission (verdict: Runtime Error):
import os
import sys

import numpy as np
from scipy.sparse.csgraph._shortest_path import floyd_warshall

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


def to_i(h, w):
    return h * W + w


N = H * W
graph = [[0] * N for _ in range(N)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            if 0 <= h - 1 < H and S[h - 1][w] == '.':
                graph[to_i(h - 1, w)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h - 1, w)] = 1
            if 0 <= h + 1 < H and S[h + 1][w] == '.':
                graph[to_i(h + 1, w)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h + 1, w)] = 1
            if 0 <= w - 1 < W and S[h][w - 1] == '.':
                graph[to_i(h, w - 1)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h, w - 1)] = 1
            if 0 <= w + 1 < H and S[h][w + 1] == '.':
                graph[to_i(h, w + 1)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h, w + 1)] = 1
dist = floyd_warshall(graph, directed=False)
dist[dist == np.inf] = 0
print(int(dist.max()))


Fixed submission:
import os
import sys

import numpy as np
from scipy.sparse.csgraph._shortest_path import floyd_warshall

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W = list(map(int, sys.stdin.buffer.readline().split()))
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]


def to_i(h, w):
    return h * W + w


N = H * W
graph = [[0] * N for _ in range(N)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            if 0 <= h - 1 < H and S[h - 1][w] == '.':
                graph[to_i(h - 1, w)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h - 1, w)] = 1
            if 0 <= h + 1 < H and S[h + 1][w] == '.':
                graph[to_i(h + 1, w)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h + 1, w)] = 1
            if 0 <= w - 1 < W and S[h][w - 1] == '.':
                graph[to_i(h, w - 1)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h, w - 1)] = 1
            if 0 <= w + 1 < W and S[h][w + 1] == '.':
                graph[to_i(h, w + 1)][to_i(h, w)] = 1
                graph[to_i(h, w)][to_i(h, w + 1)] = 1
dist = floyd_warshall(graph, directed=False)
dist[dist == np.inf] = 0
print(int(dist.max()))
Buggy python submission (verdict: Time Limit Exceeded):
import os
import os
import sys
from collections import deque, defaultdict

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A = np.array(A, dtype=int) % K

if K == 1:
    print(0)
    exit()
if K == 2:
    ans = (A % 2 == 1).sum()
    print(ans)
    exit()

def test():
    ans = 0
    for i, a in enumerate(A):
        if a % K == 1:
            ans += 1
        j = 1
        while i - j >= 0 and j + 1 < K:
            if (sum(A[i - j: i]) + a) % K == j + 1:
                ans += 1
            j += 1
    print(ans)


# 和-長さ を覚える
counts = defaultdict(int)
hist = deque()
offset = 0
ans = 0
for i, a in enumerate(A):
    if a % K == 1:
        ans += 1
    ans += counts[(K - a + 1 - offset) % K]
    offset += a - 1
    offset %= K
    counts[(a - 1 - offset) % K] += 1
    if len(hist) >= K - 2:
        counts[hist.popleft()] -= 1
    hist.append((a - 1 - offset) % K)
    # print(ans, counts, offset)
print(ans)
# test()


Fixed submission:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

if K == 1:
    print(0)
    exit()
if K == 2:
    ans = sum([1 for a in A if a % 2 == 1], 0)
    # ans = (A % 2 == 1).sum()
    print(ans)
    exit()


def test():
    ans = 0
    for i, a in enumerate(A):
        if a % K == 1:
            ans += 1
        j = 1
        while i - j >= 0 and j + 1 < K:
            if (sum(A[i - j: i]) + a) % K == j + 1:
                ans += 1
            j += 1
    print(ans)


# 和-長さ を覚える
counts = defaultdict(int)
hist = [-1] * N
offset = 0
ans = 0
for i, a in enumerate(A):
    a %= K
    if a == 1:
        ans += 1
    ans += counts[(K - a + 1 - offset) % K]
    offset += a - 1
    offset %= K
    counts[(a - 1 - offset) % K] += 1

    if i - K + 2 >= 0:
        counts[hist[i - K + 2]] -= 1
    hist[i] = (a - 1 - offset) % K
print(ans)
Buggy python submission (verdict: Runtime Error):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# 後ろから貪欲
ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# 後ろから貪欲
ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M and l >= 0:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])