Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N = int(input())

    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)
    AA = sorted(A)
    m = AA[-1]
    m2 = AA[-2]
    maxIndex = [i for i, x in enumerate(A) if x == max(A)]
    
    for i in range(N):
        if i not in maxIndex or len(maxIndex) > 1:
            print(m)
        else:
            print(m2)


if __name__ == '__main__':
    main()

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N = int(input())

    A = []
    for _ in range(N):
        a = int(input())
        A.append(a)
    ii = A.index(max(A))
    m = max(A)
    A.pop(ii)
    m2 = max(A)
    
    for i in range(N):
        if i == ii:
            print(m2)
        else:
            print(m)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N, M = list(map(int, input().split()))

    L = []
    R = []
    id = list(range(N+1))
    id_set = set(id)
    for _ in range(M):
        if len(id) == 0:
            break
        l, r = list(map(int, input().split()))
        id_set = id_set & set(id[l:r+1])
    print(len(id_set))

if __name__ == '__main__':
    main()

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N, M = list(map(int, input().split()))

    L = []
    R = []
    id = list(range(N+1))
    for _ in range(M):
        l, r = list(map(int, input().split()))
        L.append(l)
        R.append(r)

    max_l = max(L)
    min_r = min(R)
    if min_r < max_l:
        print("0")
    else:
        print(min_r - max_l + 1)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    H = np.array(H)

    cost = np.array([100000] * N)
    cost[0] = 0
    for i in range(1, N):
        cost[i] = min(
            cost[max(i - K, 0): i] + abs(H[i] - H[max(i - K, 0): i]))
        # print(i, cost[i])
    print(cost[N - 1])


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    H = np.array(H)

    cost = np.array([100000] * N)
    cost[0] = 0
    for i in range(1, N):
        cost[i] = min(
            cost[max(i - K, 0): i] + abs(H[i] - H[max(i - K, 0): i]))
        # print(i, cost[i])
    print(cost[N - 1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import math

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

K = i_i()

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(math.gcd(a,b), c)

print(ans)


Fixed submission:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import math

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

K = i_i()

res = sum([math.gcd(math.gcd(a, b), c) for a in range(1,K+1) for b in range(1,K+1) for c in range(1,K+1)])
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
from functools import reduce
import itertools

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

def gcd_list(l):
    return reduce(gcd, l)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

K = i_i()

h = {}
ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            tmp = "".join([str(y) for y in sorted([a,b,c])])
            if h.get(tmp):
                ans += h[tmp]
            else:
                h[tmp] = gcd_list([a,b,c])
                ans += h[tmp]

print(ans)


Fixed submission:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import math

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

K = i_i()

res = sum([math.gcd(math.gcd(a, b), c) for a in range(1,K+1) for b in range(1,K+1) for c in range(1,K+1)])
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_i()
S = i_s()

ans = 0
for i in range(N):
    for j in range(i, N):
        if S[i] != S[j]:
            if S[i] == 'R' and S[j] == 'G':
                tmp = 'B'
            elif S[i] == 'R' and S[j] == 'B':
                tmp = 'G'
            elif S[i] == 'G' and S[j] == 'R':
                tmp = 'B'
            elif S[i] == 'B' and S[j] == 'R':
                tmp = 'G'
            else:
                tmp = 'R'
            
            if tmp in S[j:]:
                for k in range(j, N):
                    if S[k] == tmp and k - j != j - i:
                        ans += 1

print(ans)

Fixed submission:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_i()
S = i_s()

r = S.count('R')
g = S.count('G')
b = S.count('B')

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = j + j - i
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            cnt += 1

print((r * g * b) - cnt)
Buggy python submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

X, Y, A, B, C = i_l()
p = i_l()
q = i_l()
r = i_l()

p = sorted(p, reverse=True)
q = sorted(q, reverse=True)
r = sorted(r, reverse=True)

p_i = 0
q_i = 0
r_i = 0

ans1 = 0
for i in range(X):
    if p[i] > r[r_i] or r_i > C-1:
        ans1 += p[i]
    else:
        ans1 += r[r_i]
        r_i += 1
for i in range(Y):
    if q[i] > r[r_i] or r_i > C-1:
        ans1 += q[i]
    else:
        ans1 += r[r_i]
        r_i += 1


ans2 = 0
r_i = 0
for i in range(X):
    if p[i] > r[r_i] or r_i > C-1:
        ans2 += p[i]
    else:
        ans2 += r[r_i]
        r_i += 1
for i in range(Y):
    if q[i] > r[r_i] or r_i > C-1:
        ans2 += q[i]
    else:
        ans2 += r[r_i]
        r_i += 1

ans3 = 0
if X + Y <= C:
    ans3 = sum(r[:(X+Y)])

print(max(ans1, ans2, ans3))

Fixed submission:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

X, Y, A, B, C = i_l()
p = i_l()
q = i_l()
r = i_l()

p = sorted(p, reverse=True)
q = sorted(q, reverse=True)
r = sorted(r, reverse=True)

p = p[:X]
q = q[:Y]
arr = sorted((p + q + r), reverse=True)

print(sum(arr[:(X+Y)]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import fractions
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N, M = map(int, input().split())
a = [int(x) for x in input().split()]

ans = 0
half_lcm = lcm_list(a) // 2

a = set(a)
for i in range(half_lcm, M+1, half_lcm):
    if all(int((i / x * 2)) & 1 for x in set(a)):
        ans += 1

print(ans)

Fixed submission:
import sys
# import fractions
import math
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
stdin = sys.stdin

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

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

def lcm_list(l):
    return reduce(lcm, l, 1)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
a = i_l()
half_lcm = lcm_list(a) // 2

for i in a:
    if half_lcm // (i // 2) % 2 == 0:
        print(0)
        exit()

print(((M // half_lcm) + 1) // 2)

Buggy python submission (verdict: Runtime Error):
import sys
import fractions
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N, M = map(int, input().split())
a = [int(x) for x in input().split()]

ans = 0
half_lcm = lcm_list(a) // 2

a = set(a)
for i in range(half_lcm, M+1, half_lcm):
    if all(int((i / x * 2)) & 1 for x in a):
        ans += 1

print(ans)

Fixed submission:
import sys
# import fractions
import math
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
stdin = sys.stdin

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

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

def lcm_list(l):
    return reduce(lcm, l, 1)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
a = i_l()
half_lcm = lcm_list(a) // 2

for i in a:
    if half_lcm // (i // 2) % 2 == 0:
        print(0)
        exit()

print(((M // half_lcm) + 1) // 2)
Buggy python submission (verdict: Runtime Error):
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

A, B = map(int, input().split())
print(int(A * B / math.gcd(A, B)))


Fixed submission:
import sys
import fractions
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

A, B = map(int, input().split())
print(int(A * B / fractions.gcd(A, B)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = sum(A)
    a = []
    b = []
    for i in range(len(A)):
        if s % 2 != 0:
            if sum(a) >= (s // 2) - 1 or i == N-1:
                b.append(A[i])
            else:
                a.append(A[i])
        else:
            if sum(a) >= (s // 2) or i == N-1:
                b.append(A[i])
            else:
                a.append(A[i])
    ans1 = abs(sum(a)-sum(b))
    ans2 = abs(sum(a[:-1])-sum(b+[a[-1]]))
    print(min(ans1, ans2))


if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = sum(A)
    a = 0
    b = 0
    tmp = []
    for i in range(len(A)):
        if s % 2 != 0:
            if a >= (s // 2) - 1 or i == N-1:
                b += A[i]
            else:
                a += A[i]
                tmp.append(A[i])
        else:
            if a >= (s // 2) or i == N-1:
                b += A[i]
            else:
                a += A[i]
                tmp.append(A[i])
    ans1 = abs(a-b)
    ans2 = abs((a-tmp[-1]) - (b+tmp[-1]))
    print(min(ans1, ans2))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    n = int(input())
    l = map(int, input().split())
    t = list(itertools.combinations(l,3))
    cnt = 0
    for a, b, c in t:
        if a<b+c and b<c+a and c<a+b:
            cnt += 1
    print(cnt)




if __name__ == '__main__':
        main()


Fixed submission:
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    ans = 0
    for a in range(n-2):
        for b in range(a+1, n-1):
            ans += bisect.bisect_left(l, l[a]+l[b]) - b - 1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]


arr = []
for i in range(1, n+1):
    arr.append(a.count(i))


for x in arr:
    if k - q + x > 0:
        print("Yes")
    else:
        print("No")


Fixed submission:
from collections import defaultdict
d = defaultdict(int)

n, k, q = map(int, input().split())


for _ in range(q):
    d[int(input())] += 1

for x in range(1, n+1):
    if k - q + d[x] > 0:
        print("Yes")
    else:
        print("No")

Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

d = [k] * n
for i in a:
    tmp = d[i-1]
    d = [x-1 for x in d]
    d[i-1] = tmp

for x in d:
    if x > 0:
        print("Yes")
    else:
        print("No")


Fixed submission:
from collections import defaultdict
d = defaultdict(int)

n, k, q = map(int, input().split())


for _ in range(q):
    d[int(input())] += 1

for x in range(1, n+1):
    if k - q + d[x] > 0:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
n = int(input())


a = list(range(1, n))

print(sum(a))


Fixed submission:
n = int(input())


a = (1+n-1)*(n-1)//2
print(a)

Buggy python submission (verdict: Runtime Error):
n = int(input())

a = list(range(1, n+1))
b = a[1:]+[1]
ans = 0

for i in range(n):
    ans += a[i] % b[i]

print(ans)


Fixed submission:
n = int(input())


a = (1+n-1)*(n-1)//2
print(a)

Buggy python submission (verdict: Runtime Error):
n = int(input())

a = list(range(1, n+1))
b = a[1:]+[1]
ans = 0

for i in range(n):
    ans += a[i] % b[i]

print(ans)


Fixed submission:
n = int(input())


a = (1+n-1)*(n-1)//2
print(a)

Buggy python submission (verdict: Runtime Error):
n = int(input())

a = list(range(1, n+1))
# b = sorted(a, reverse=True)

b = list(range(2, n+1))+[1]
ans = 0

for i in range(n):
    ans += a[i] % b[i]

print(ans)


Fixed submission:
n = int(input())


a = (1+n-1)*(n-1)//2
print(a)
Buggy python submission (verdict: Runtime Error):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*-~n

    def sum(self, i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
a = list(map(int, input().split()))

k = k % (10 ** 9 + 7)
bit = Bit(n * k)
cnt = 0
for i, t in enumerate(a * k):
    bit.add(t, 1)
    cnt += i+1-bit.sum(t)


print((cnt % (10 ** 9 + 7)))


Fixed submission:
MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt1 = 0
for i in range(len(a)-1):
    for j in range(i, len(a)):
        if a[i] > a[j]:
            cnt1 += 1

a2 = a * 2
cnt2 = 0
for i in range(len(a)):
    for j in range(len(a), len(a2)):
        if a2[i] > a2[j]:
            cnt2 += 1

print((cnt1 * k + cnt2 * k * (k-1) // 2) % MOD)

Buggy python submission (verdict: Runtime Error):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*-~n

    def sum(self, i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
a = list(map(int, input().split()))

bit = Bit(n)
cnt = 0
for i, t in enumerate(a):
    bit.add(t, 1)
    cnt += i+1-bit.sum(t)
    cnt = cnt % (10 ** 9 + 7)


print(cnt * sum(range(1, k+1)) % (10 ** 9 + 7))


Fixed submission:
MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt1 = 0
for i in range(len(a)-1):
    for j in range(i, len(a)):
        if a[i] > a[j]:
            cnt1 += 1

a2 = a * 2
cnt2 = 0
for i in range(len(a)):
    for j in range(len(a), len(a2)):
        if a2[i] > a2[j]:
            cnt2 += 1

print((cnt1 * k + cnt2 * k * (k-1) // 2) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n = int(input())
# s = [set(input()) for _ in range(n)]
s = sorted([sorted(input()) for _ in range(n)])

# print(s)

ans = 0
cnt = 0
for i in range(n-1):
    if i == n-2 and s[i] == s[i+1]:
        cnt += 1
        ans += len(list(itertools.combinations(range(cnt+1), 2)))
    if s[i] == s[i+1]:
        cnt += 1
    else:
        ans += len(list(itertools.combinations(range(cnt+1), 2)))
        cnt = 0
print(ans)


Fixed submission:
def nCr(n, r):
    r = min(r, n-r)

    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator


n = int(input())
s = sorted([sorted(input()) for _ in range(n)])


ans = 0
cnt = 0
for i in range(n-1):
    if i == n-2 and s[i] == s[i+1]:
        cnt += 1
        ans += nCr(cnt+1, 2)
        print(ans)
        exit()
    if s[i] == s[i+1]:
        cnt += 1
    else:
        if cnt > 0:
            ans += nCr(cnt+1, 2)
            cnt = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int, input().split())

n = max(a, b)

for i in range(n):
    if abs(a-i) == abs(i-b):
        print(i)
        exit()

print('IMPOSSIBLE')


Fixed submission:
a, b = map(int, input().split())

n = (a+b) % 2
if n == 0:
    print((a+b) // 2)
else:
    print('IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int(input()) for x in range(n)]

copied_arr = a.copy()
max1 = max(a)
copied_arr.remove(max1)
max2 = max(copied_arr)

for x in a:
    if x == max1:
        print(max2)
    else:
        print(max1)


Fixed submission:
n = int(input())
a = [int(input()) for x in range(n)]

copied_arr = a.copy()
max1 = max(a)
copied_arr.remove(max1)
max2 = max(copied_arr)

for x in a:
    if x == max1:
        print(max2)
    else:
        print(max1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

arr = [0] * (n+1)
arr[0] = 1
for i in range(1, n+1):
    if i in a:
        arr[i] = 0
    else:
        arr[i] = (arr[i-1] + arr[i-2]) % 1000000007

print(arr[-1])


Fixed submission:
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

MOD = 1000000007

dp = [0] * (N + 1)
dp[0] = 1

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, N + 1):
    if i in a:
        continue
    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD

print(dp[N])

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

MOD = 1000000007

dp = [0] * (N + 1)
dp[0] = 1

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, N + 1):
    print(f"i: {i}, dp: {dp}")

    if i in a:
        continue
    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD
print(f"i: {i}, dp: {dp}")

print(dp[N])


Fixed submission:
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

MOD = 1000000007

dp = [0] * (N + 1)
dp[0] = 1

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

for i in range(2, N + 1):
    if i in a:
        continue
    dp[i] = dp[i - 1] + dp[i - 2]
    dp[i] %= MOD

print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
l = list([input().split() for _ in range(q)])

for i in l:
    l = int(i[0])
    r = int(i[1])
    print(s[l-1:r].count('AC'))


Fixed submission:
N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i: i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
l = list([list(map(int, input().split())) for _ in range(q)])

for i in l:
    l = i[0]
    r = i[1]
    print(s[l-1:r].count('AC'))


Fixed submission:
N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)

for i in range(N):
    t[i+1] = t[i] + (1 if S[i: i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
l = len(s)
i = 0
while True:
    if len(s)-1 <= i:
        break
    if s[i] == '0' and s[i+1] == '1' or s[i] == '1' and s[i+1] == '0':
        del s[i:i+2]
        i = 0
    else:
        i += 1

print(l-len(s))


Fixed submission:
s = list(input())
print(min(s.count('0'), s.count('1'))*2)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i in range(1, N):
    dp[i] = min(abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i))

print(dp[-1])


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i))
    
    print(dp[-1])
main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


def ans(n, w):
    dp = [0] * (w+1)
    for _ in range(n):
        wi, vi = map(int, input().split())
        for i in range(wi, w+1):
            if dp[i-wi] < dp[i] + vi:
                dp[i-wi] = dp[i] + vi
    return dp[0]


N, W = map(int, input().split())
print(ans(N, W))


Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(w, W+1):
            j = dp[i]
            if dp[i-w] < j + v:
                dp[i-w] = j + v

    print(max(dp))


main()


Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(w, W+1):
        j = dp[i]
        if j == -1:
            continue
        if dp[i-w] < j + v:
            dp[i-w] = j + v

print(max(dp))


Fixed submission:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])