Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
lst = list(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7

if 0 in lst:
    a, b = 0, 1
if 1 in lst:
    a, b = 1, 0
else:
    a, b = 1, 1

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in lst:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Fixed submission:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
skip = set(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in skip else 0
b = 1 if not 1 in skip else 0

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in skip:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
lst = list(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7

if 0 in lst:
    a, b = 0, 1
if 1 in lst:
    a, b = 1, 0
else:
    a, b = 1, 1

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in lst:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Fixed submission:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
skip = set(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in skip else 0
b = 1 if not 1 in skip else 0

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in skip:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
lst = list(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7

if 0 in lst:
    ans = [0, 1] + [0] * (n - 1)
if 1 in lst:
    ans = [1, 0] + [0] * (n - 1)
else:
    ans = [1, 1] + [0] * (n - 1)

for i in range(2, n + 1):
    if i in lst:
        ans[i] = 0
    else:
        ans[i] = (ans[i - 2] + ans[i - 1]) % MOD
print(ans[-1])

Fixed submission:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
skip = set(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in skip else 0
b = 1 if not 1 in skip else 0

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in skip:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
a, b = list(map(int, input().rstrip().split()))
ans = {i for i in range(a, b + 1)}
for _ in range(m - 1):
    a, b = list(map(int, input().rstrip().split()))
    ans = ans & {i for i in range(a, b + 1)}
print(len(ans))

Fixed submission:
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
ans = 0
l, r = lst[0][0], lst[0][1]
for i in lst[1:]:
    l = max(l, i[0])
    r = min(r, i[1])
for i in range(1, n + 1):
    if l <= i <= r:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
a, b = list(map(int, input().rstrip().split()))
ans = {i for i in range(a, b + 1)}
for _ in range(m - 1):
    a, b = list(map(int, input().rstrip().split()))
    ans = ans & {i for i in range(a, b + 1)}
print(len(ans))

Fixed submission:
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
ans = 0
l, r = lst[0][0], lst[0][1]
for i in lst[1:]:
    l = max(l, i[0])
    r = min(r, i[1])
for i in range(1, n + 1):
    if l <= i <= r:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
gates = [{j for j in range(i[0], i[1] + 1)} for i in lst]
ans = gates[0]
for i in gates[1:]:
    ans = ans & i
print(len(ans))

Fixed submission:
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
ans = 0
l, r = lst[0][0], lst[0][1]
for i in lst[1:]:
    l = max(l, i[0])
    r = min(r, i[1])
for i in range(1, n + 1):
    if l <= i <= r:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
gates = [{j for j in range(i[0], i[1] + 1)} for i in lst]
ans = gates[0]
for i in gates[1:]:
    ans = ans & i
print(len(ans))

Fixed submission:
# ABC127C - Prison
n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
ans = 0
l, r = lst[0][0], lst[0][1]
for i in lst[1:]:
    l = max(l, i[0])
    r = min(r, i[1])
for i in range(1, n + 1):
    if l <= i <= r:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
# ABC126B - YYMM or MMYY
s = input()
x, y = int(s[:2]), int(s[2:])
if x = 0 or y = 0:
    print("NA")
elif 1 <= x <= 12 and 1 <= y <= 12:
    print("AMBIGUOUS")
elif 1 <= x <= 12 and y <= 31:
    print("MMYY")
elif x <= 31 and 1 <= y <= 12:
    print("YYMM")
else:
    print("NA")

Fixed submission:
# ABC126B - YYMM or MMYY
s = input()
x, y = int(s[:2]), int(s[2:])
if 1 <= x <= 12:
    if 1 <= y <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 1 <= y <= 12:
        print("YYMM")
    else:
        print("NA")
Buggy python submission (verdict: Runtime Error):
# ABC126D - Even Relation
def dfs(v: int, p: int) -> None:
    for u, w in T[v]:
        if u != p:
            D[u] = D[v] + w
            dfs(u, v)


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [0] * (N + 1)  # D[i] := distance from vertex 1 (root)
    dfs(1, -1)
    ans = [i % 2 for i in D[1:]]  # same parity of distance -> same group
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Fixed submission:
# ABC126D - Even Relation
import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v: int, p: int) -> None:
    for u, w in T[v]:
        if u != p:
            D[u] = D[v] + w
            dfs(u, v)


def main():
    global T, D
    N, *A = map(int, open(0).read().split())
    T = [[] for _ in range(N + 1)]
    for i in range(0, (N - 1) * 3, 3):
        v, u, w = A[i : i + 3]
        T[v] += [(u, w)]
        T[u] += [(v, w)]
    D = [0] * (N + 1)  # D[i] := distance from vertex 1 (root)
    dfs(1, -1)
    ans = [i % 2 for i in D[1:]]  # same parity of distance -> same group
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# div2019B - RGB Boxes
r, g, b, n = list(map(int, input().rstrip().split()))
x = n // min(r, g, b) + 1
cnt = 0
for i in range(x):
    for j in range(x):
        if (n - (i * r + j * g)) >= 0 and (n - (i * r + j * g)) % b == 0:
            cnt += 1
print(cnt)

Fixed submission:
# div2019B - RGB Boxes
r, g, b, n = list(map(int, input().rstrip().split()))
x = n // min(r, g, b) + 1
cnt = 0
for i in range(x):
    for j in range(x):
        if (n - (i * r + j * g)) >= 0 and (n - (i * r + j * g)) % b == 0:
            cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
# div2019C - AB Substrings
from itertools import permutations


def main():
    N = int(input())
    S = tuple(input().rstrip() for _ in range(N))
    ans = 0
    for perm in permutations(S, N):
        x = "".join(perm)
        ans = max(ans, x.count("AB"))
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
# div2019C - AB Substrings
def main():
    N, *S = open(0).read().split()
    ans, ab, start_b, end_a = 0, 0, 0, 0
    for s in S:
        if s[0] == "B" and s[-1] == "A":
            ab += 1
        elif s[0] == "B":
            start_b += 1
        elif s[-1] == "A":
            end_a += 1
        ans += s.count("AB")
    if start_b + end_a == 0:
        ans += max(0, ab - 1)
    else:
        ans += ab + min(start_b, end_a)
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# div2019C - AB Substrings
from itertools import permutations


def main():
    N = int(input())
    S = tuple(input().rstrip() for _ in range(N))
    ans = 0
    for perm in permutations(S, N):
        x = "".join(perm)
        ans = max(ans, x.count("AB"))
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
# div2019C - AB Substrings
def main():
    N, *S = open(0).read().split()
    ans, ab, start_b, end_a = 0, 0, 0, 0
    for s in S:
        if s[0] == "B" and s[-1] == "A":
            ab += 1
        elif s[0] == "B":
            start_b += 1
        elif s[-1] == "A":
            end_a += 1
        ans += s.count("AB")
    if start_b + end_a == 0:
        ans += max(0, ab - 1)
    else:
        ans += ab + min(start_b, end_a)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
# div2019D - DivRem Number
def divisors(n: int) -> set:
    # Compute divisors of a number.
    divs = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            div.add(i)
            div.add(n // i)
    return divs


def main():
    N = int(input())
    divs = divisors(N)
    ans = 0
    for m in divs:
        if m == 1:
            continue
        m -= 1
        if N // m == N % m:
            ans += m
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
# div2019D - DivRem Number
# cf. ARC026B - 完全数
def divisors(n: int) -> set:
    """
    Compute divisors of a number.
    
    Args: n (int): an integer to be evaluated.
    Returns: div (set): set of divisors
    """
    div = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            div.add(i)
            div.add(n // i)
    return div


def main():
    N = int(input())
    divs = divisors(N)
    divs.discard(1)
    ans = 0
    for m in divs:
        m -= 1
        if N // m == N % m:
            ans += m
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
# TPBC201B - *e**** ********e* *e****e* ****e**
n = int(input())
s = list(input())
k = int(input())

for i in range(n):
    if s[i] != s[k]:
        s[i] = '*'
print(''.join(s))

Fixed submission:
# TPBC201B - *e**** ********e* *e****e* ****e**
n = int(input())
s = list(input())
k = int(input())

for i in range(n):
    if s[i] != s[k - 1]:
        s[i] = "*"
print("".join(s))
Buggy python submission (verdict: Time Limit Exceeded):
# TPBC201C - Stones
n = int(input())
s = input()
if len(set(s)) == 1:
    print(0)
else:
    ans = n
    for i in range(len(s)):
        ans = min(ans, s[:i].count("#") + s[i:].count("."))
    print(ans)

Fixed submission:
# TPBC201C - Stones
n = int(input())
s = input()
ans = 0
blk = 0
for i in s:
    if i == "#":
        blk += 1
    else:
        if blk > 0:
            ans += 1
            blk -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# TPBC201C - Stones
n = int(input())
s = input()
if len(set(s)) == 1:
    print(0)
else:
    ans = n
    for i in range(len(s)):
        ans = min(ans, s[:i].count("#") + s[i:].count("."))
    print(ans)

Fixed submission:
# TPBC201C - Stones
n = int(input())
s = input()
ans = 0
blk = 0
for i in s:
    if i == "#":
        blk += 1
    else:
        if blk > 0:
            ans += 1
            blk -= 1
print(ans)

Buggy python submission (verdict: Runtime Error):
# TPBC201C - Stones
n = int(input())
s = list(input())
ans = 0
if len(set(s)) == 1:
    print(ans)
else:
    while s[0] == ".":
        s.pop(0)
    while s[-1] == "#":
        s.pop()
    lst = "".join(s).split(".#")
    for i in range(len(lst)):
        if i == 0:
            ans += min(lst[i].count("#"), lst[i].count(".") + 1)
        elif i == len(lst) - 1:
            ans += min(lst[i].count("#") + 1, lst[i].count("."))
        else:
            ans += min(lst[i].count("#") + 1, lst[i].count(".") + 1)
    print(ans)

Fixed submission:
# TPBC201C - Stones
n = int(input())
s = input()
ans = 0
blk = 0
for i in s:
    if i == "#":
        blk += 1
    else:
        if blk > 0:
            ans += 1
            blk -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC123
cnd = list(map(int, [input().rstrip() for _ in range(6)]))
n = cnd[0]
arr = [n] + [0] * 6
ans = 0
while arr[5] != n:
    for i in range(5, 0, -1):
        if arr[i - 1] == 0:
            continue
        move = min(arr[i - 1], cnd[i])
        arr[i] += move
        arr[i - 1] -= move
    ans += 1
print(ans)

Fixed submission:
# ABC123C - Five Transportations
from math import ceil
cnd = list(map(int, [input().rstrip() for _ in range(6)]))
print(ceil(cnd[0] / min(cnd[1:])) + 4)
Buggy python submission (verdict: Runtime Error):
# ABC122A - Double Helix
# a-t, c-g
data = {'a': 't', 't': 'a', 'c': 'g', 'g': 'c'}

print(data[input()])

Fixed submission:
# ABC122A - Double Helix
# a-t, c-g
data = {"A": "T", "T": "A", "C": "G", "G": "C"}

print(data[input()])
Buggy python submission (verdict: Time Limit Exceeded):
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n - 1)
for i in range(n - 1):
    if s[i : i + 2] == "AC":
        cnt[i] += 1
for i, j in arr:
    print(cnt[i - 1 : j - 1].count(1))

Fixed submission:
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        cnt[i + 1] = cnt[i] + 1
    else:
        cnt[i + 1] = cnt[i]
for i, j in arr:
    print(cnt[j - 1] - cnt[i - 1])

Buggy python submission (verdict: Time Limit Exceeded):
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n - 1)
for c, (i, j) in enumerate(zip(s, s[1:])):
    if i + j == "AC":
        cnt[c] += 1
for i, j in arr:
    print(cnt[i - 1 : j - 1].count(1))

Fixed submission:
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        cnt[i + 1] = cnt[i] + 1
    else:
        cnt[i + 1] = cnt[i]
for i, j in arr:
    print(cnt[j - 1] - cnt[i - 1])

Buggy python submission (verdict: Time Limit Exceeded):
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = []
for i, j in zip(s, s[1:]):
    if i + j == "AC":
        cnt += [1]
    else:
        cnt += [0]
for i, j in arr:
    print(cnt[i - 1 : j - 1].count(1))

Fixed submission:
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        cnt[i + 1] = cnt[i] + 1
    else:
        cnt[i + 1] = cnt[i]
for i, j in arr:
    print(cnt[j - 1] - cnt[i - 1])

Buggy python submission (verdict: Time Limit Exceeded):
# ABC122C - GeT AC
n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
for i, j in arr:
    cnt = 0
    for k, l in zip(s[i - 1 : j - 1], s[i:]):
        if k + l == "AC":
            cnt += 1
    print(cnt)

Fixed submission:
# ABC122C - GeT AC
import sys
input = sys.stdin.readline

n, q = list(map(int, input().rstrip().split()))
s = input().rstrip()
arr = [list(map(int, input().rstrip().split())) for _ in range(q)]
cnt = [0] * (n + 1)
for i in range(n):
    if s[i : i + 2] == "AC":
        cnt[i + 1] = cnt[i] + 1
    else:
        cnt[i + 1] = cnt[i]
for i, j in arr:
    print(cnt[j - 1] - cnt[i - 1])
Buggy python submission (verdict: Time Limit Exceeded):
# ABC121D - XOR World
def main():
    a, b = list(map(int, input().rstrip().split()))
    ans = a
    for i in range(a + 1, b + 1):
        ans ^= i
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
# ABC121D - XOR World
def main():
    a, b = list(map(int, input().rstrip().split()))
    c = a if a % 2 == 0 else a + 1
    n = b - c + 1
    pairs = n // 2
    if n % 2 == 0:
        ans = pairs % 2
        ans ^= 0 if c == a else a
        print(ans)
    else:
        ans = (pairs % 2) ^ b
        ans ^= 0 if c == a else a
        print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
# ABC119B - Digital Gifts
def main():
    _, XU = open(0).read().split()
    ans, RATE = 0, 380000
    for x, u in zip(*[iter(XU)] * 2):
        x = float(x)
        ans += x if u == "JPY" else x * RATE
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
# ABC119B - Digital Gifts
n = int(input())
lst = [input().rstrip().split() for _ in range(n)]
total = 0

for i in range(n):
    if lst[i][1] == 'JPY':
        total += int(lst[i][0])
    else:
        total += 380000 * float(lst[i][0])
        
print(total)

Buggy python submission (verdict: Runtime Error):
# ABC119B - Digital Gifts
def main():
    _, XU = open(0).read().split()
    ans, RATE = 0, 380000
    for x, u in zip(*[iter(XU)] * 2):
        x = float(x)
        total += x if u == "JPY" else x * RATE
    print(total)


if __name__ == "__main__":
    main()

Fixed submission:
# ABC119B - Digital Gifts
n = int(input())
lst = [input().rstrip().split() for _ in range(n)]
total = 0

for i in range(n):
    if lst[i][1] == 'JPY':
        total += int(lst[i][0])
    else:
        total += 380000 * float(lst[i][0])
        
print(total)
Buggy python submission (verdict: Runtime Error):
# yahoo-procon2019-qualC - When I hit my pocket...
import sys
sys.setrecursionlimit(10 ** 9)


def hit(k, c, m):
    if k == 0:
        return c
    ret = []
    ret += [hit(k - 1, c + 1, m)]
    if c >= A:
        ret += [hit(k - 1, c - A, m + 1)]
    if m > 0:
        ret += [hit(k - 1, c + B, 0)]
    return max(ret)


K, A, B = list(map(int, input().rstrip().split()))
print(hit(K, 1, 0))

Fixed submission:
# yahoo-procon2019-qualC - When I hit my pocket...
def main():
    k, a, b = list(map(int, input().rstrip().split()))
    if b - a <= 2 or k < a - 1:
        print(k + 1)
        return

    ans, k = a, k - (a - 1)
    if k % 2 == 1:
        k -= 1
        ans += 1
    ans += (b - a) * k // 2
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
# keyence2019C - Exam and Wizard
def main():
    N, *AB = map(int, open(0).read().split())
    ans, shortage, pos = 0, 0, []
    for i, j in zip(AB[:N], B[N:]):
        x = i - j
        if x >= 0:
            pos.append(x)
        else:
            ans += 1
            shortage += x
    for i in sorted(pos, reverse=1):
        if shortage >= 0:
            break
        ans += 1
        shortage += i
    flg = shortage >= 0
    print(ans if flg else -1)  # -1: shoratage still remains


if __name__ == "__main__":
    main()

Fixed submission:
# keyence2019C - Exam and Wizard
def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))
    dif = sorted(i - j for i, j in zip(A, B))
    ans, shortage = 0, 0
    for i in dif:
        if i < 0:
            ans += 1
            shortage += i
        else:
            break
    for i in dif[::-1]:
        if shortage >= 0:
            print(ans)
            return
        ans += 1
        shortage += i
    print(-1)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# B - Frog 2
def main():
    N, K, *H = map(int, open(0).read().split())
    H = [0] + H + [0] * K
    dp = [1 << 30] * (N + K + 1)
    dp[1] = 0
    for i, a in enumerate(H[1:N + 1], 1):
        for j, b in enumerate(H[i + 1:i + K + 1], i + 1):
            dp[j] = min(dp[j], dp[i] + abs(a - b))
    print(dp[N])


if __name__ == "__main__":
    main()


Fixed submission:
# EduDPB - Frog 2
import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])

Buggy python submission (verdict: Time Limit Exceeded):
# dpB - Frog 2
# 貰うDP
def main():
    n, k = tuple(map(int, input().rstrip().split()))
    A = tuple(map(int, input().rstrip().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        for j in range(1, k + 1):
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + abs(A[i] - A[i - j]))
    print(dp[-1])


if __name__ == "__main__":
    main()

Fixed submission:
# EduDPB - Frog 2
import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])

Buggy python submission (verdict: Time Limit Exceeded):
# EduDPB - Frog 2
n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])

Fixed submission:
# EduDPB - Frog 2
import sys
input = sys.stdin.readline

n, k = list(map(int, input().rstrip().split()))
lst = list(map(int, input().rstrip().split()))
ans = [0] + [float("inf")] * (n - 1)
for i in range(n):
    for j in range(1, k + 1):
        if i + j >= n:
            break
        ans[i + j] = min(ans[i + j], ans[i] + abs(lst[i] - lst[i + j]))
print(ans[-1])