Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
dams = list(map(int, input().split()))

mountSum = sum(dams)
result = []
for i in range(n):
    otSum = 0
    if i % 2 == 0:
        for j in range(i // 2):
            otSum += dams[j * 2] * 2
        for j in range(i // 2, n // 2):
            otSum += dams[j * 2 + 1] * 2
    else:
        for j in range(i // 2):
            otSum += dams[j*2 + 1] *2
        for j in range((i // 2) +1, (n //2) +1 ):
            otSum += dams[j * 2] * 2
    result.append(mountSum - otSum)

print(*result)



Fixed submission:
n = int(input())
dams = list(map(int, input().split()))

mountSum = sum(dams)
result = []
otSum = 0
for j in range(0, n // 2):
    otSum += dams[j * 2 + 1] * 2
result.append(mountSum - otSum)
for i in range(1, n-1):
    result.append(dams[i-1] * 2 - result[i-1])
result.append(dams[n-1]*2 - result[0])

print(*result)
Buggy python submission (verdict: Time Limit Exceeded):
def calcScore(d, g, scoreMap, index, score, solved):
    minSolved = 0
    for i in range(scoreMap[index][0] + 1):
        scoreNow = score + 100 * (index + 1) * i
        if i == scoreMap[index][0]:
            scoreNow += scoreMap[index][1]
        solvedNow = solved + i
        if scoreNow >= g:
            if minSolved == 0 or minSolved > solvedNow:
                return solvedNow
            else:
                return minSolved
        tmpSolved = 0
        if index < d - 1:
            tmpSolved = calcScore(d, g, scoreMap, index + 1, scoreNow, solvedNow)
            if minSolved == 0 or (minSolved > tmpSolved and tmpSolved != 0):
                minSolved = tmpSolved
    return minSolved


d, g = map(int, input().split())
scoreMap = [list(map(int, input().split())) for i in range(d)]

solved = calcScore(d, g, scoreMap, 0, 0, 0)

print(solved)

Fixed submission:
d, g = map(int, input().split())
scoreMap = [list(map(int, input().split())) for i in range(d)]

minimum = 0

for i in range(2**d):
    score = 0
    solved = 0
    for j in range(d):
        if (i >> j) & 1 == 1:
            score += scoreMap[j][0] * 100 * (j + 1) + scoreMap[j][1]
            solved += scoreMap[j][0]
    if score < g:
        for k in range(d)[::-1]:
            if (i >> k) & 1 == 0:
                if (g - score > scoreMap[k][0] * 100 * (k + 1)):
                    score += scoreMap[k][0] * 100 * (k + 1) + scoreMap[k][1]
                    solved += scoreMap[k][0]
                    if score > g:
                        break
                else:
                    solved += (g - score) // (100 * (k + 1))
                    if (g - score) % (100 * (k + 1)) != 0:
                        solved += 1
                    score = g
                    break
    if minimum == 0 or solved < minimum:
        minimum = solved

print(minimum)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
aiList = [int(input()) for i in range(n)]
count = 0
visited = [1]
now = 1
while True:
    count += 1
    nextNum = aiList[now - 1]
    if nextNum == 2:
        break
    if nextNum in visited:
        count = -1
        break
    visited.append(nextNum)
    now = nextNum
print(count)

Fixed submission:
n = int(input())
aiList = [int(input()) for i in range(n)]
count = 0
now = 1
while True:
    count += 1
    if count >= n:
        count = -1
        break
    nextNum = aiList[now - 1]
    if nextNum == 2:
        break
    now = nextNum
print(count)
Buggy python submission (verdict: Runtime Error):
str1 = input()
str2 = input()

dict = dict()
ans = "Yes"

for i in range(len(str1)):
    if(str1[i] in dict):
        if(dict[str[i]] != str2[i]):
            ans = "No"
    else:
        dict[str1[i]] = str2[i]

print(ans)


Fixed submission:
str1 = input()
str2 = input()

dict1 = dict()
ans = "Yes"

for i in range(len(str1)):
    if(str1[i] in dict1.keys()):
        if(dict1[str1[i]] != str2[i]):
            ans = "No"
    else:
        if(str2[i] in dict1.values()):
            ans = "No"
        dict1[str1[i]] = str2[i]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def str_to_map(str):
    Map = dict()
    for i in range(len(str)):
        c = str[i]
        if(c in Map):
            Map[c].add(i)
        else:
            Map[c] = {i}
    return Map


str1 = input()
str2 = input()

I1 = str_to_map(str1)
I2 = str_to_map(str2)

flag = True

for i in range(len(str1)):
    if(I1[str1[i]] != I2[str2[i]]):
        flag = False

if(flag):
    print("Yes")
else:
    print("No")


Fixed submission:
str1 = input()
str2 = input()

dict1 = dict()
ans = "Yes"

for i in range(len(str1)):
    if(str1[i] in dict1.keys()):
        if(dict1[str1[i]] != str2[i]):
            ans = "No"
    else:
        if(str2[i] in dict1.values()):
            ans = "No"
        dict1[str1[i]] = str2[i]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ar = list(map(int, input().split()))
res = 0
mod = 10 ** 9 + 7
for i in range(60):
    zero = 0
    one = 0
    for j in range(len(ar)):
        if ar[j] % 2 == 0:
            zero += 1
        else:
            one += 1
        ar[j] = ar[j] // 2
    curr = (zero * one * (1 << i)) % mod
    res = (res + curr) % mod
print(res)


Fixed submission:
n = int(input())
ar = list(map(int, input().split()))
res = 0
mod = 10 ** 9 + 7
for i in range(60):
    zero = 0
    one = 0
    for j in range(len(ar)):
        if ar[j] % 2 == 0:
            zero += 1
        else:
            one += 1
        ar[j] = ar[j] // 2
    curr = (zero * one * (1 << i)) % mod
    res = (res + curr) % mod
print(res)
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
index = 2
result = math.inf
while index * index <= n:
    if n % index == 0:
        curr = (n // index) - 1
        curr += (index - 1)
        result = min(curr, result)
    index += 1
if result == math.inf:
    result = n - 1
print(result)

Fixed submission:

n = int(input())
index = 2
result = 10**13
while index * index <= n:
    if n % index == 0:
        curr = (n // index) - 1
        curr += (index - 1)
        result = min(curr, result)
    index += 1
if result == 10**13:
    result = n - 1
print(result)
Buggy python submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())
h = x / (a * a)
if h == b / 2:
    answer = math.atan(a / b)
elif h < b / 2:
    answer = math.atan(2*h*a / (b * b))
else:
    answer = math.atan(a / (2 * (b - h)))
print(90 - answer / math.pi * 180)

Fixed submission:
import math
a, b, x = map(int, input().split())
h = x / (a * a)
if h == b / 2:
    answer = math.atan(a / b)
elif h < b / 2:
    answer = math.atan(2*h*a / (b * b))
else:
    if h == b:
        answer = math.pi / 2
    else:
        answer = math.atan(a / (2 * (b - h)))
print(90 - answer / math.pi * 180)
Buggy python submission (verdict: Runtime Error):
n, k, q = map(int, input().split())
ar = [k for i in range(n)]
for i in range(q):
  index = int(input())
  ar[index-1] += 1
for i in range(n):
  if ar[i] - q > 0:
    print("Yes")
  else:
    print("No")

Fixed submission:
def tap_dance(st):
  size = len(st)
  for i in range(size):
    if (i+1) % 2 == 0:
      if st[i] not in "LUD":
        return "No"
    else:
      if st[i] not in "RUD":
        return "No"
  return "Yes"
st = input()
print(tap_dance(st))
Buggy python submission (verdict: Runtime Error):
n, k, q = map(int, input().split())
ar = [k for i in range(n)]
for i in range(q):
  index = int(input())
  ar[index] += 1
for i in range(n):
  if ar[i] - q > 0:
    print("Yes")
  else:
    print("No")

Fixed submission:
n, k, q = map(int, input().split())
ar = [k for i in range(n)]
for i in range(q):
  index = int(input())
  ar[index-1] += 1
for i in range(n):
  if ar[i] - q > 0:
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
if 2 * n >= m:
    print(m // 2)
else:
    a = m - 2 * n
    b = a // 4
    print(n + b)

Fixed submission:
n = int(input())
pi = 1
for i in range(1, n + 1):
    pi = (pi * i) % 1000000007
print(pi)
Buggy python submission (verdict: Runtime Error):
[print(a*b//2)for a,b,_ in[[*map(int,input().split())]]]

Fixed submission:
[print(a*b//2) for a,b,_ in [sorted(map(int, input().split()))]]

Buggy python submission (verdict: Runtime Error):
[print(a*b/2)for a,b,_ in[[*map(int,input().split())]]]

Fixed submission:
[print(a*b//2) for a,b,_ in [sorted(map(int, input().split()))]]
Buggy python submission (verdict: Runtime Error):
print'A%sC'%'BRG'[input()/100+4>>4]

Fixed submission:
print('A'+'BRG'[int(input())//100+4>>4]+'C')
Buggy python submission (verdict: Runtime Error):

def isprime(x):
  if x < 2: return False
  for d in range(2, int(x**0.5)+1):
    if x % d == p: return False
  return True

isp = list(map(isprime, range(100001)))
w = [0]*100001
for i in range(100001):
  if i > 2 and isp[i] and isp[(i + 1)//2]:
    w[i] = 1

for i in range(1,100001):
  w[i] += w[i-1]

Q = int(input())
for i in range(Q):
  L,R = map(int, input().split())
  print(w[R] - w[L-1])

Fixed submission:
def isprime(x):
  if x < 2: return False
  for d in range(2, int(x**0.5)+1):
    if x % d == 0: return False
  return True

isp = list(map(isprime, range(100001)))
w = [0]*100001
for i in range(100001):
  if i > 2 and isp[i] and isp[(i + 1)//2]:
    w[i] = 1

for i in range(1,100001):
  w[i] += w[i-1]

Q = int(input())
for i in range(Q):
  L,R = map(int, input().split())
  print(w[R] - w[L-1])
Buggy python submission (verdict: Runtime Error):
from heapq import *
n,m=map(int,input().split())
l=list(map(int,input().split()))
arr=[list(map(int,input().split())) for i in range(m)]
arr.sort(key=lambda x:x[1],reverse=True)
l.sort()
i=0
j=0
while(i<n):
    flag=False
    x=arr[j][0]
    k=0
    while(i<n and x>0 and arr[j][1]>l[i]):
        if(not flag):
            k=j+1
        l[i]=arr[j][1]
        x-=1
        i+=1
        flag=True
    j=k
    if(flag):
        continue
    else:
        i+=1
print(sum(l))

Fixed submission:
from heapq import *
n,m=map(int,input().split())
l=list(map(int,input().split()))
arr=[list(map(int,input().split())) for i in range(m)]
arr.sort(key=lambda x:x[1],reverse=True)
l.sort()
i=0
j=0
while(i<n):
    if(l[i]>=arr[j][1]):
        break
    l[i]=arr[j][1]
    arr[j][0]-=1
    if(arr[j][0]==0):
        j+=1
    if(j>=m):
        break
    i+=1
    #print(j,l)
#print(l)
print(sum(l))
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=input()
k-=1
print(s[:k]+s[k:k+1].lower()+s[k+1])

Fixed submission:
n,k=map(int,input().split())
s=input()
k-=1
print(s[:k]+s[k:k+1].lower()+s[k+1:])
Buggy python submission (verdict: Runtime Error):
l=input()
if((int(l[:2])>0 or int(l[2:])>0) and int(l[:2])<=12 and int(l[2:])<=12):
    print('AMBIGUOUS')
elif((int(l[:2])>0 or int(l[2:])>0) and int(l[2:])<=12 and int(l[:2])>=13):
    print("YYMM")
elif((int(l[:2])>0 or int(l[2:])>0) and int(l[2:]>=13) and int(l[:2])<=12):
    print("MMYY")
else:
    print('NA')

Fixed submission:
s = input()
first = int(s[0:2])
second = int(s[2:4])
if 1 <= first <= 12 and 1 <= second <= 12:
    print('AMBIGUOUS')
elif 1 <= first <= 12:
    print('MMYY')
elif 1 <= second <= 12:
    print('YYMM')
else:
    print('NA')

Buggy python submission (verdict: Runtime Error):
l=input()
if(int(l[:2])>0 and int(l[2:])>0 and int(l[:2])<=12 and int(l[2:])<=12):
    print('AMBIGUOUS')
elif(int(l[:2])>0 and int(l[2:])>0 and int(l[2:])<=12 and int(l[:2])>=13):
    print("YYMM")
elif(int(l[:2])>0 and int(l[2:])>0 and int(l[2:]>=13) and int(l[:2])<=12):
    print("MMYY")
else:
    print('NA')

Fixed submission:
s = input()
first = int(s[0:2])
second = int(s[2:4])
if 1 <= first <= 12 and 1 <= second <= 12:
    print('AMBIGUOUS')
elif 1 <= first <= 12:
    print('MMYY')
elif 1 <= second <= 12:
    print('YYMM')
else:
    print('NA')

Buggy python submission (verdict: Runtime Error):
l=input()
if(int(l[:2])>0 and int(l[2:])>0 and int(l[:2])<=12 and int(l[2:])<=12):
    print('AMBIGUOUS')
elif(int(l[:2])>0 and int(l[2:])>0 and int(l[:2])<=12 and int(l[2:])>=13):
    print("YYMM")
elif(int(l[:2])>0 and int(l[2:])>0 and int(l[:2>=13]) and int(l[2:])<=12):
    print("MMYY")
else:
    print('NA')

Fixed submission:
s = input()
first = int(s[0:2])
second = int(s[2:4])
if 1 <= first <= 12 and 1 <= second <= 12:
    print('AMBIGUOUS')
elif 1 <= first <= 12:
    print('MMYY')
elif 1 <= second <= 12:
    print('YYMM')
else:
    print('NA')
Buggy python submission (verdict: Time Limit Exceeded):
l=list(input())
k=int(input())
m=[0]*len(l)
for i in range(len(l)):
    var=pow(int(l[i]),5*pow(10,15))
    if(i==0):
        m[i]+=var
    if(i>=1):
        m[i]+=(m[i-1]+var)
    if(k<=m[i]):
        print(l[i])
        exit()

Fixed submission:
l=list(input())
k=int(input())
m=[0]*len(l)
for i in range(len(l)):
    var=pow(int(l[i]),100)
    if(i==0):
        m[i]+=var
    if(i>=1):
        m[i]+=(m[i-1]+var)
    if(k<=m[i]):
        print(l[i])
        exit()
Buggy python submission (verdict: Runtime Error):
sys.setrecursionlimit(10000000)
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]<0:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(10000000)
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]>0:
        return dp[i]
    else:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))

Buggy python submission (verdict: Runtime Error):
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]<0:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(10000000)
def calc(dp,adj,i):
    if(len(adj[i])==0):
        dp[i]=0
    elif dp[i]>0:
        return dp[i]
    else:
        for j in adj[i]:
            dp[i]=max(dp[i],calc(dp,adj,j))
        dp[i]+=1
    return dp[i]
n,m=map(int,input().split())
adj=[]
for i in range(n+1):
    adj.append([])
for i in range (m):
    x,y=map(int,input().split())
    adj[x].append(y)
dp=[-1]*(n+1);
for i in range(1,n+1):
    calc(dp,adj,i)
print(max(dp))
Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))

if N >= K:
    print(N % K)
else:
    print(K % N)


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

print(min(N % K, K - (N % K)))
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

q = []
for i in range(1, 10):
    q.append(i)

for i in range(K):
    x = q.pop(0)
    if x % 10 != 0:
        q.append(10 * x - 1 + x % 10)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + 1 + x % 10)

print(x)


Fixed submission:
from collections import deque
K = int(input())

q = deque()
for i in range(1, 10):
    q.append(i)

for i in range(K):
    x = q.popleft()
    if x % 10 != 0:
        q.append(10 * x - 1 + x % 10)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + 1 + x % 10)

print(x)
Buggy python submission (verdict: Runtime Error):
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    a, b = list(map(int, input().split()))
    ab.append((a, b))
ab.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

import sys
sys.setrecursionlimit(1500)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h - a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))


Fixed submission:
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    a, b = list(map(int, input().split()))
    ab.append((a, b))
ab.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

import sys
sys.setrecursionlimit(100000000)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h - a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))

Buggy python submission (verdict: Runtime Error):
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    a, b = list(map(int, input().split()))
    ab.append((a, b))
ab.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h-a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))


Fixed submission:
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    a, b = list(map(int, input().split()))
    ab.append((a, b))
ab.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

import sys
sys.setrecursionlimit(100000000)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h - a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))
Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit_one_count = [0 for i in range(60)]
bit_zero_count = [0 for i in range(60)]
for i in range(n):
    bits = '{0:060b}'.format(a[i])
    for j in range(60):
        if bits[-1 -j] == '1':
            bit_one_count[j] += 1
        else:
            bit_zero_count[j] += 1

ans = 0
for j in range(60):
    ans += bit_one_count[j] * bit_zero_count[j] * 2 ** j
    ans %= MOD

print(ans)


Fixed submission:

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit_one_count = [0 for i in range(60)]
bit_zero_count = [0 for i in range(60)]
for i in range(n):
    bits = '{0:060b}'.format(a[i])
    for j in range(60):
        if bits[-1 -j] == '1':
            bit_one_count[j] += 1
        else:
            bit_zero_count[j] += 1

ans = 0
for j in range(60):
    ans += bit_one_count[j] * bit_zero_count[j] * 2 ** j
    ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += a[i] ^ a[j]
        ans %= MOD

print(ans)


Fixed submission:

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit_one_count = [0 for i in range(60)]
bit_zero_count = [0 for i in range(60)]
for i in range(n):
    bits = '{0:060b}'.format(a[i])
    for j in range(60):
        if bits[-1 -j] == '1':
            bit_one_count[j] += 1
        else:
            bit_zero_count[j] += 1

ans = 0
for j in range(60):
    ans += bit_one_count[j] * bit_zero_count[j] * 2 ** j
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

n, m = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(m):
    tx, ty, _tz = list(map(int, input().split()))
    edges[tx-1].append(ty-1) 
    edges[ty-1].append(tx-1) 
visited = [False] * n
ans = 0
for i in range(n):
    if not visited[i]:
        q = [i]
        visited[i] = True
        while q:
            u = q.pop(0)
            for v in edges[u]:
                if not visited[v]:
                    q.append(v)
                    visited[v] = True
        ans += 1
print(ans)


Fixed submission:

n, m = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(m):
    tx, ty, _tz = list(map(int, input().split()))
    edges[tx-1].append(ty-1) 
    edges[ty-1].append(tx-1) 
visited = [False] * n
ans = 0
for i in range(n):
    if not visited[i]:
        q = [i]
        visited[i] = True
        while q:
            u = q.pop(0)
            for v in edges[u]:
                if not visited[v]:
                    q.append(v)
                    visited[v] = True
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
h = list(map(int, input().split()))

INF = float('inf')
dp = [0]

for i in range(1, N):
    min_t = INF
    for j in range(1, K+1):
        if i - j < 0:
            continue
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp.append(min_t)

print(dp[N-1])


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

INF = float('inf')
dp = [0]

for i in range(1, N):
    min_t = INF
    for j in range(1, K+1):
        if i - j < 0:
            continue
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp.append(min_t)

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
h = list(map(int, input().split()))

INF = float('inf')
dp = [INF for _ in range(N)]

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

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

print(dp[N-1])


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

INF = float('inf')
dp = [0]

for i in range(1, N):
    min_t = INF
    for j in range(1, K+1):
        if i - j < 0:
            continue
        min_t = min(min_t, dp[i-j] + abs(h[i-j] - h[i]))
    dp.append(min_t)

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = list(map(int, input().split()))

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = 0
    flag = 0
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print(dp[W][0])


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

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = dp[i-1][0]
    flag = dp[i-1][1]
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print(dp[W][0])