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

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(pl) - np.searchsorted(pl, x / ml)).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, x / ml)).sum()
        n -= np.count_nonzero(ml ** 2 <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl ** 2 <= x)
        assert n % 2 == 0
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right


def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i - 1 for i in range(len(zl))])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:

import numpy as np


# 解がマイナスのとき
def solve1(k, ml, pl):
    left, right = -(10 ** 18) - 1, 0
    while right - left > 1:
        x = (left + right) // 2
        n = (len(pl) - np.searchsorted(pl, x // ml + (x % ml != 0))).sum()
        if k <= n:
            right = x
        else:
            left = x
    return right


# 解がプラスのとき
def solve2(k, ml, pl):
    left, right = 0, 10 ** 18
    while right - left > 1:
        x = (left + right) // 2
        n = 0
        n += (len(ml) - np.searchsorted(ml, x // ml + (x % ml != 0))).sum()
        n -= np.count_nonzero(ml ** 2 <= x)
        n += (np.searchsorted(pl, x // pl, side="right")).sum()
        n -= np.count_nonzero(pl ** 2 <= x)
        assert n % 2 == 0
        n //= 2
        if k <= n:
            right = x
        else:
            left = x
    return right


def main():
    N, K = list(map(int, input().split()))
    A = np.array(input().split(), dtype=int)
    A.sort()
    ml = A[A < 0]
    pl = A[A > 0]
    zl = A[A == 0]
    mn = len(ml) * len(pl)
    zn = sum([N - i - 1 for i in range(len(zl))])
    if K <= mn:
        ans = solve1(K, ml, pl)
    elif K <= mn + zn:
        ans = 0
    else:
        ans = solve2(K - mn - zn, ml, pl)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
LI = lambda: list(map(int, input().split()))

N = int(input())
AB = [LI() for _ in range(N - 1)]

link = [[] for _ in range(N)]
children = [[] for _ in range(N)]
w = [1] * N
visit = [False] * N

MOD = 10 ** 9 + 7


def create_link():
    for a, b in AB:
        link[a - 1].append(b - 1)
        link[b - 1].append(a - 1)


def dfs(s):
    visit[s] = True
    for t in link[s]:
        if visit[t]:
            continue
        children[s].append(t)
        dfs(t)
        w[s] += w[t]


def modinv(x):
    return pow(x, MOD - 2, MOD)


def main():
    create_link()
    dfs(0)
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(N):
        p2[i + 1] = 2 * p2[i] % MOD
    
    x = 0
    for i in range(N):
        s = p2[N - w[i]]
        for j in children[i]:
            s = (s + p2[w[j]] - 1) % MOD
        x = (x + p2[N - 1] - s) % MOD
    y = p2[N]

    ans = x * modinv(y) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

N = int(input())
AB = [LI() for _ in range(N - 1)]

link = [[] for _ in range(N)]
children = [[] for _ in range(N)]
w = [1] * N
visit = [False] * N

MOD = 10 ** 9 + 7


def create_link():
    for a, b in AB:
        link[a - 1].append(b - 1)
        link[b - 1].append(a - 1)


def dfs(s):
    visit[s] = True
    for t in link[s]:
        if visit[t]:
            continue
        children[s].append(t)
        dfs(t)
        w[s] += w[t]


def modinv(x):
    return pow(x, MOD - 2, MOD)


def main():
    create_link()
    dfs(0)
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(N):
        p2[i + 1] = 2 * p2[i] % MOD
    
    x = 0
    for i in range(N):
        s = p2[N - w[i]]
        for j in children[i]:
            s = (s + p2[w[j]] - 1) % MOD
        x = (x + p2[N - 1] - s) % MOD
    y = p2[N]

    ans = x * modinv(y) % MOD
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
LI = lambda: list(map(int, input().split()))

N, X, D = LI()


def sumeq(n):
    return n * (n + 1) // 2


def main():
    d = {}
    for i in range(N + 1):
        a = i * X + sumeq(i - 1) * D
        b = sumeq(N - 1) - sumeq(N - i - 1) - sumeq(i - 1)
        v = (a - a % D) // D
        if a % D in d:
            d[a % D].append((v, b))
        else:
            d[a % D] = [(v, b)]
    
    ans = 0
    for w in d.values():
        w.sort()
        ans += w[0][1] + 1
        x = w[0][0] + w[0][1]
        n = len(w)
        for i in range(1, n):
            r = w[i][0] + w[i][1]
            if x < w[i][0]:
                ans += w[i][1] + 1
            elif x < r:
                ans += r - x
            x = max(x, r)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
LI = lambda: list(map(int, input().split()))

N, X, D = LI()


def sumeq(n):
    return n * (n + 1) // 2


def main():
    if D == 0:
        if X == 0:
            ans = 1
        else:
            ans = N + 1
        print(ans)
        return
    
    d = {}
    for i in range(N + 1):
        a = i * X + sumeq(i - 1) * D
        b = sumeq(N - 1) - sumeq(N - i - 1) - sumeq(i - 1)
        v = (a - a % D) // D
        if a % D in d:
            d[a % D].append((v, b))
        else:
            d[a % D] = [(v, b)]
    
    ans = 0
    for w in d.values():
        w.sort()
        ans += w[0][1] + 1
        x = w[0][0] + w[0][1]
        n = len(w)
        for i in range(1, n):
            r = w[i][0] + w[i][1]
            if x < w[i][0]:
                ans += w[i][1] + 1
            elif x < r:
                ans += r - x
            x = max(x, r)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
LI = lambda: list(map(int, input().split()))

N, K = LI()
H = LI()

INF = 10 ** 15


def main():
    h = [0] + H
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            v = INF
            for k in range(i):
                x = max(0, h[i] - h[k])
                v = min(v, dp[k][j - 1] + x)
            dp[i][j] = v

    ans = min([dp[i][N - K] for i in range(N - K, N + 1)])
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
LI = lambda: list(map(int, input().split()))

N, K = LI()
H = LI()

INF = 10 ** 15


def main():
    h = [0] + H
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            v = INF
            for k in range(i):
                x = max(0, h[i] - h[k])
                v = min(v, dp[k][j - 1] + x)
            dp[i][j] = v

    ans = min([dp[i][N - K] for i in range(N - K, N + 1)])
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from scipy.special import comb

N = int(input())
S = [input() for _ in range(N)]

d = {}
for s in S:
    s = "".join(sorted(s))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1
ans = 0
for v in d.values():
    if v > 1:
        ans += comb(v, 2)
print(ans)        

Fixed submission:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


N = int(input())
S = [input() for _ in range(N)]

d = {}
for s in S:
    s = "".join(sorted(s))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1
ans = 0
for v in d.values():
    if v > 1:
        ans += cmb(v, 2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
BA = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    BA.append((b, a))

ans = 0
MAX = 10 ** 5 + 1
schedule = [i for i in range(M + 1)]
BA.sort(reverse=True)
x = None
for b, a in BA:
    if a < M:
        if schedule[a] == MAX:
            x = min(schedule[a+1:])
            if x == MAX:
                continue
        else:
            x = a
    elif a == M and schedule[a] != MAX:
        x = a
    else:
        continue
    schedule[x] = MAX
    ans += b
print(ans)

Fixed submission:
class Node:
    
    def __init__(self, i):
        self.end = i + 1
        self.days = {i}


N, M = list(map(int, input().split()))
BA = []
for i in range(N):
    a, b = list(map(int, input().split()))
    BA.append((b, a))

ans = 0
schedule = {}


def concat(node1, node2, x):
    if len(node1.days) < len(node2.days):
        node1, node2 = node2, node1
    else:
        node1.end = node2.end
    node1.days |= node2.days
    for i in node2.days:
        schedule[i] = node1
    schedule[x] = node1
    node1.days.add(x)

BA.sort(reverse=True)
for b, a in BA:
    if a <= M:
        if a in schedule:
            w = schedule[a]
            x = w.end
            if x <= M:
                ans += b
                if x + 1 in schedule:
                    concat(w, schedule[x + 1], x)
                else:
                    schedule[x] = w
                    w.days.add(x)
                    w.end += 1
        else:
            ans += b
            if a + 1 in schedule:
                w = schedule[a + 1]
                if a - 1 in schedule:
                    concat(schedule[a - 1], w, a)
                else:
                    schedule[a] = w
                    w.days.add(a)
            elif a - 1 in schedule:
                w = schedule[a - 1]
                schedule[a] = w
                w.days.add(a)
                w.end += 1
            else:
                schedule[a] = Node(a)
print(ans)
Buggy python submission (verdict: Runtime Error):
A[:].remove(mx1)

Fixed submission:
N  = int(input())
A = [int(input()) for _ in range(N)]

mx1 = max(A)
A_ = A[:]
A_.remove(mx1)
mx2 = max(A_)
for a in A:
    if a == mx1:
        print(mx2)
    else:
        print(mx1)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N + 1)
half = int(N / 2)
b[half:] = A[half - 1:]
for i in range(N, 0, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b):
    if b_ == 1:
        print(i, end=" ")

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N + 1)
half = N // 2
b[half + 1:] = A[half:]
for i in range(half, 1, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b[:]):
    if b_ == 1:
        print(i, end=" ")

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N + 1)
half = int(N / 2)
b[half:] = A[half - 1:]
for i in range(N, 0, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b):
    if b_ == 1:
        print(i, end=" ")

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

b = [0] * (N + 1)
half = N // 2
b[half + 1:] = A[half:]
for i in range(half, 1, -1):
    s = sum([b[j] for j in range(i * 2, N + 1, i)]) % 2
    if s != A[i - 1]:
        b[i] = 1
s = sum(b)
if s % 2 != A[0]:
    b[1] = 1
    s += 1
print(s)
for i, b_ in enumerate(b[:]):
    if b_ == 1:
        print(i, end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = int(input())
c = [a]
c_len = 1
for i in range(1, n):
    a = int(input())
    for j in range(c_len):
        if c[j] < a:
            c[j] = a
            break
    else:
        c.append(a)
        c_len += 1
print(c_len)


Fixed submission:
N = int(input())
a = int(input())
l = [a]
d = {a: 1}
ans = 1
for _ in range(1, N):
    a = int(input())
    if a in d:
        d[a] += 1
        if l[-1] == a:
            ans += 1
        else:
            i = l.index(a) + 1
            v = l[i]
            if d[v] == 1:
                del d[v]
                l.remove(v)
            else:
                d[v] -= 1
    else:
        v = l[0]
        if v < a:
            if d[v] == 1:
                del d[v]
                l[0] = a
            else:
                d[v] -= 1
                l.insert(0, a)
        elif l[-1] > a:
            l.append(a)
            ans += 1
        else:
            left, right = 0, len(l) - 1
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                del d[v]
                l[right] = a
            else:
                d[v] -= 1
                l.insert(right, a)
        d[a] = 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

import numpy as np

a = np.zeros((N, N))
for i in range(N-1):
    a[i][i] = 1
    a[i][i+1] = 1
a[-1][-1] = 1
a[-1][0] = 1
b = np.array(A) * 2
X = np.linalg.solve(a, b)
X = map(int, X)
print(" ".join(map(str, X)))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = [None] * N
x[0] = sum(A) - 2 * sum([a for a in A[1::2]])
for i in range(N-1):
    x[i+1] = 2 * A[i] - x[i]
print(" ".join(map(str, x)))

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

import numpy as np

a = np.zeros((N, N))
for i in range(N):
    a[i][i] = 1
    if i + 1 == N:
        a[i][0] = 1
    else:
        a[i][i+1] = 1
b = np.array(A)
X = np.linalg.solve(a, b) * 2
X = map(int, X)
print(" ".join(map(str, X)))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

x = [None] * N
x[0] = sum(A) - 2 * sum([a for a in A[1::2]])
for i in range(N-1):
    x[i+1] = 2 * A[i] - x[i]
print(" ".join(map(str, x)))
Buggy python submission (verdict: Runtime Error):

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)

Fixed submission:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if A % C == 0:
    c = A
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if A % D == 0:
    d = A
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if A % cd_lcm == 0:
    cdl = A
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)

Buggy python submission (verdict: Runtime Error):
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)

Fixed submission:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

A, B, C, D = tuple(map(int, input().split()))

s = -1
c = C * (A // C + 1)
if A % C == 0:
    c = A
if c <= B:
    s += (B - c) // C + 1
        
d = D * (A // D + 1)
if A % D == 0:
    d = A
if d <= B:
    s += (B - d) // D + 1
    
cd_lcm = lcm(C, D)
cdl = cd_lcm * (A // cd_lcm + 1)
if A % cd_lcm == 0:
    cdl = A
if cdl <= B:
    s -= (B - cdl) // cd_lcm + 1

print(B - A - s)
Buggy python submission (verdict: Runtime Error):
LI = lambda: list(map(int, input().split()))

N, X = LI()
L = LI()


def main():
    ans = X // L
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
LI = lambda: list(map(int, input().split()))

N, X = LI()
L = LI()


def main():
    ans = 1
    d = 0
    for l in L:
        d += l
        if d > X:
            break
        ans += 1
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            dp[i][j] %= MOD
            if S[i - 1] == T[j - 1]:
                x = 1 + dp[i - 1][j - 1]
                dp[i][j] = (dp[i][j] + x) % MOD
    
    ans = (dp[-1][-1] + 1) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            dp[i][j] %= MOD
            if S[i - 1] == T[j - 1]:
                x = 1 + dp[i - 1][j - 1]
                dp[i][j] = (dp[i][j] + x) % MOD
    
    ans = (dp[-1][-1] + 1) % MOD
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
x = input()
(N, K) = (int(x[0]), int(x[2]))
max_distribution = N - K
if K == 1:
    max_distribution = 0
print(max_distribution)

Fixed submission:
(N, K) = list(map(int, input().split()))
max_distribution = N - K
if K == 1:
    max_distribution = 0
print(max_distribution)
Buggy python submission (verdict: Runtime Error):
x = input()
(N, K) = (int(x[0]), int(x[2]))
max_distribution = N - K
if K == 1:
    max_distribution = 0
print(max_distribution)

Fixed submission:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
if N == 1:
    print(1)
else:
    d_list = [(i[0] - j[0], i[1] - j[1]) for i in xy for j in xy if i != j]
    items = list(set(d_list))
    s = 1
    for item in items:
        c = d_list.count(item)
        if c > s:
            s = c
    print(N - s)
Buggy python submission (verdict: Runtime Error):
def successive_subtraction(N, A, i=1, l=[]):
    mx = max(A)
    mn = min(A)
    if i == N - 1:
        print(mx - mn)
        return l
    l.append((mn, mx))
    A.remove(mn)
    A.remove(mx)
    A.append(mn - mx)
    return successive_subtraction(N, A, i + 1, l)

N = int(input())
A = list(map(int, input().split()))
l = successive_subtraction(N, A)
for v in l:
    print(v[0], v[1])

Fixed submission:
def successive_subtraction(N, A, i=1, l=[]):
    mx = max(A)
    mn = min(A)
    if i == N - 1:
        print(mx - mn)
        return l
    l.append((mn, mx))
    A.remove(mn)
    A.remove(mx)
    A.append(mn - mx)
    return successive_subtraction(N, A, i + 1, l)

N = int(input())
A = [int(e) for e in input().split()]
A.sort()
l = []
for i in range(N - 2):
    (a, b, c) = (A[0], A[1], A[-1])
    if b < 0:
        l.append((c, a))
        A[-1] = c - a
    else:
        l.append((a, b))
        A[1] = a - b
    A.pop(0)
print(A[1] - A[0])
l.append((A[1], A[0]))
for v in l:
    print(v[0], v[1])
Buggy python submission (verdict: Runtime Error):
import heapq

N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = []

x1, k1, l1, lim1 = 0, K, [], N
if lim1 > K:
    lim1 = K
lim1 += 1
for i in range(lim1):
    ans.append(sum(l1[min(k1, x1):]))
    x2, k2, l2, lim2 = x1, k1, l1[:], N - i
    if lim2 > k2:
        lim2 = k2 + 1
    for vr in V[:-lim2:-1]:
        k2 -= 1
        heapq.heappush(l2, vr)
        if vr <= 0:
            x2 += 1
        ans.append(sum(l2[min(k2, x2):]))
    vl = V[i]
    k1 -= 1
    heapq.heappush(l1, vl)
    if vl <= 0:
        x1 += 1
print(max(ans))

Fixed submission:
from bisect import insort_right as ir

N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
ans = [0]

def right(x, k, l, lim):
    if lim > k:
        lim = k
    for vr in V[::-1][:lim]:
        k -= 1
        ir(l, vr)
        if vr <= 0:
            x += 1
        ans.append(sum(l[min(k, x):]))    

x1, k1, l1, lim1 = 0, K, [], N
if lim1 > K:
    lim1 = K
right(0, K, [], N - 1)
for vl in V[:lim1]:
    k1 -= 1
    ir(l1, vl)
    if vl <= 0:
        x1 += 1
    ans.append(sum(l1[min(k1, x1):]))
    x2, k2, l2, lim2 = x1, k1, l1[:], N + k1 - K
    right(x2, k2, l2, lim2)
ans.append(sum(l1[min(k1, x1):]))
print(max(ans))
Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
L, R = [], []
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

ans = min(R) - max(L) + 1
if ans < 0:
    ans = 0
print(ans)

Fixed submission:
N, M = list(map(int, input().split()))
L, R = [None] * M, [None] * M
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

l = max(L)
r = min(R)
ans = r - l + 1
if ans < 0:
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
LR = []
for _ in range(M):
    L, R = list(map(int, input().split()))
    LR.append({i for i in range(L, R + 1)})

x = LR[0]
for y in LR:
    x &= y
print(len(x))

Fixed submission:
N, M = list(map(int, input().split()))
L, R = [None] * M, [None] * M
for i in range(M):
    L[i], R[i] = list(map(int, input().split()))

l = max(L)
r = min(R)
ans = r - l + 1
if ans < 0:
    ans = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
H = LI()

INF = 10 ** 10


def main():
    dp = [INF] * N
    dp[0] = 0
    for i in range(1, N):
        n = min(K + 1, i + 1)
        for j in range(1, n):
            dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, K = LI()
H = LI()

INF = 10 ** 10


def main():
    dp = [INF] * N
    dp[0] = 0
    for i in range(1, N):
        n = min(K + 1, i + 1)
        for j in range(1, n):
            dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()