Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
d = {}
for i in A:
    if i in d.keys():
        d[i] += 1
    else:
        d[i] = 1
whole_ans = sum(map(lambda x: x*(x-1)//2, d.values()))
for i in A:
    d_ = d.copy()
    d_[i] -= 1
    dif = (d_[i]*(d_[i]-1) - d[i]*(d[i]-1)) // 2
    part_ans = whole_ans + dif
    print(part_ans)

Fixed submission:
N = int(input())
A = list(map(lambda x: int(x)-1, input().split()))
d = [0] * N
for i in A:
    d[i] += 1
s = sum(map(lambda x: x*(x-1)//2, d))
for i in A:
    print(s + (1 - d[i]))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
d = {}
# まず全体における答えを求める
for i in A:
    if i in d.keys():
        d[i] += 1
    else:
        d[i] = 1
whole_ans = sum(map(lambda x: x*(x-1)//2, d.values()))
# 差分更新
for i in A:
    d_ = d.copy()
    d_[i] -= 1
    dif = (d_[i]*(d_[i]-1) - d[i]*(d[i]-1)) // 2
    part_ans = whole_ans + dif
    print(part_ans)

Fixed submission:
N = int(input())
A = list(map(lambda x: int(x)-1, input().split()))
d = [0] * N
for i in A:
    d[i] += 1
s = sum(map(lambda x: x*(x-1)//2, d))
for i in A:
    print(s + (1 - d[i]))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
for i in range(len(A)):
    count = 0
    d = {}
    A_ = A[:]
    A_.pop(i)
    A_.sort()
    for j in range(len(A_)-1):
        if A_[j] == A_[j+1]:
            count += 1
        elif A_[j] != A_[j+1]:
            count += 1
            d[A_[j]] = (count*(count-1))//2
            count = 0
    count += 1
    d[A_[j+1]] = (count*(count-1))//2
    print(sum(d.values()))

Fixed submission:
N = int(input())
A = list(map(lambda x: int(x)-1, input().split()))
d = [0] * N
for i in A:
    d[i] += 1
s = sum(map(lambda x: x*(x-1)//2, d))
for i in A:
    print(s + (1 - d[i]))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque
    s = deque(input())
    q = int(input())
    for i in range(q):
        l = input().split()
        if int(l[0]) == 1:
            s.reverse()
        else:
            if int(l[1]) == 1:
                s.appendleft(l[2])
            else:
                s.append(l[2])
    print("".join(s))

if __name__ == "__main__":
    main()

Fixed submission:
from collections import deque
s = deque(input().split())
q = int(input())
rev = False
for _ in range(q):
    qu = input()
    if qu == "1":
        rev = not rev
    else:
        _, f, c = qu.split()
        if (f != "1") == rev:
            s.appendleft(c)
        else:
            s.append(c)

s = "".join(s)
if rev:
    s = reversed(s)
print("".join(s))
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
if n == 1:
    for i in range(10):
        tmp = str(i)
        flag = True
    for j in range(m):
        if tmp[arr[j][0]-1] != str(arr[j][1]):
            flag = False
    if flag:
        print(i)
        break
    else:
        print(-1)
else:
    for i in range(10**(n-1),10**n):
        tmp = str(i)
        flag = True
    for j in range(m):
        if tmp[arr[j][0]-1] != str(arr[j][1]):
            flag = False
    if flag:
        print(i)
        break
    else:
        print(-1)

Fixed submission:
n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
if n == 1:
    for i in range(10):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
else:
    for i in range(10**(n-1),10**n):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
d = dict()
for i in range(m):
    s, c = map(int, input().split())
    if s==1 and c==0:
        print("-1")
        exit()
    if s in d.keys() and d[s] != c:
        print("-1")
        exit()
    d[s] = c
if d[2] == 0 and 1 not in d.keys():
    print("-1")
    exit()
target = 0
for s, c in d.items():
    target += 10**(n-s)*c
print(target)

Fixed submission:
n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
if n == 1:
    for i in range(10):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
else:
    for i in range(10**(n-1),10**n):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def expect(x):
    return sum(list(range(1,x+1)))/x
input = sys.stdin.readline
n, k = map(int, input().split())
p = list(map(int, input().split()))
table = []
for i in range(n-k+1):
    w = 0
    for j in range(k):
        w += expect(p[i+j])
    table.append(w)
print(max(table))

Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
p = list(map(int, input().split()))
p = [(1+i)/2 for i in p]
# 累積和の配列sを作成する
s = [0] * (n+1)
for i in range(1,n+1):
    s[i] = s[i-1] + p[i-1]
max = -1 * float("inf")
for i in range(n-k+1):
    sum = s[k+i] - s[i]
    if max <= sum:
        max = sum
print(max)

Buggy python submission (verdict: Time Limit Exceeded):
def expect(x):
    return sum(list(range(1,x+1)))/x
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    table = []
    for i in range(n-k+1):
        w = 0
        for j in range(k):
            w += expect(p[i+j])
        table.append(w)
    print(max(table))
if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
p = list(map(int, input().split()))
p = [(1+i)/2 for i in p]
# 累積和の配列sを作成する
s = [0] * (n+1)
for i in range(1,n+1):
    s[i] = s[i-1] + p[i-1]
max = -1 * float("inf")
for i in range(n-k+1):
    sum = s[k+i] - s[i]
    if max <= sum:
        max = sum
print(max)

Buggy python submission (verdict: Time Limit Exceeded):
def expect(x):
    return sum(list(range(1,x+1)))/x
n, k = map(int, input().split())
p = list(map(int, input().split()))
table = []
for i in range(n-k+1):
    w = 0
    for j in range(k):
        w += expect(p[i+j])
    table.append(w)

print(max(table))

Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
p = list(map(int, input().split()))
p = [(1+i)/2 for i in p]
# 累積和の配列sを作成する
s = [0] * (n+1)
for i in range(1,n+1):
    s[i] = s[i-1] + p[i-1]
max = -1 * float("inf")
for i in range(n-k+1):
    sum = s[k+i] - s[i]
    if max <= sum:
        max = sum
print(max)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int,input().split())
pS = [tuple(input().split()) for _ in range(m)]
pena = 0
correct = 0
d = {}
for p, s in pS:
    if p in d.keys():
        d[p].append(s)
    else:
        d[p] = [s]
for key, values in d.items():
    cnt = 0
    for i in values:
        if i == "WA":
            cnt += 1
        else:
            correct += 1
            pena += cnt
            break
print(correct, pena)

Fixed submission:
n, m = map(int,input().split())
pS = [input().split() for _ in range(m)]
correct = 0
flag = [False] * n
pena = [0] * n
sum = 0
for p, s in pS:
    p = int(p)
    if flag[p-1] == True:
        continue
    else:
        if s == "WA":
            pena[p-1] += 1
        elif s == "AC":
            sum += pena[p-1]
            correct += 1
            flag[p-1] = True
print(correct, sum)
Buggy python submission (verdict: Runtime Error):
def dfs(h, w): # startからの距離の最大値をreturnする
    res = -1
    dist = [[-1] * W for _ in range(H)]
    stack = []
    dist[h][w] = 0
    stack.append([h, w])
    while stack:
        h, w = stack.pop()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if s[nh][nw] == "#":
                continue
            if dist[nh][nw] == -1:
                dist[nh][nw] = dist[h][w] + 1
                stack.append([nh, nw])
            if dist[nh][nw] != -1:
                if dist[nh][nw] > (dist[h][w]+1):
                    dist[nh][nw] = dist[h][w] + 1
                    stack.append([nh, nw])
    for i in range(H):
        if res <= max(visited[i]):
            res = max(visited[i])
    return res

H, W = map(int, input().split())
s = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
m = -1
dist = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = dfs(i, j)
            if m <= dist:
                m = dist
print(m)

Fixed submission:
def dfs(h, w): 
    m = -1
    visited = [[-1] * W for _ in range(H)]
    stack = []
    visited[h][w] = 0
    stack.append([h, w])
    while stack:
        h, w = stack.pop()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if s[nh][nw] == "." and visited[nh][nw] == -1:
                visited[nh][nw] = visited[h][w] + 1
                stack.append([nh, nw])
            if s[nh][nw] == "." and visited[nh][nw] != -1:
                if visited[nh][nw] > (visited[h][w]+1):
                    visited[nh][nw] = visited[h][w] + 1
                    stack.append([nh, nw])
    for i in range(H):
        if m <= max(visited[i]):
            m = max(visited[i])
    return m

H, W = map(int, input().split())
s = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
m = -1
dist = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = dfs(i, j)
            if m <= dist:
                m = dist
print(m)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
s = set([a,b])
s_ = set(range(1,4))
print((s_ - s)[0])

Fixed submission:
a = int(input())
b = int(input())
for i in range(1,4):
  if i != a and i != b:
    print(i)
Buggy python submission (verdict: Runtime Error):
from math import gcd
a, b = map(int, input().split())
print((a*b)//gcd(a,b))

Fixed submission:
from fractions import gcd
a, b = map(int, input().split())
print((a*b)//gcd(a,b))
Buggy python submission (verdict: Runtime Error):
# nCk(mod p)の計算
from math import factorial
X, Y = map(int, input().split())
MOD = 10**9+7
MAX = 10**6+1

 # a!のテーブルfact
fact = [0] * MAX
# (a!)^-1のテーブルfinv
finv = [0] * MAX

def comb_init():
    # a!と(a!)^-1のテーブルを作る
    # 累積積のイメージ
    fact[0] = fact[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fact[i] = i * fact[i-1] % MOD
        finv[i] = pow(i, -1, MOD) * finv[i-1] % MOD

def comb(n, r):
    return fact[n] * (finv[n-r] * finv[r] % MOD) % MOD    


if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    if not num >= min(p, q) >= 0:
        print(0)
        exit()
    comb_init()
    print(comb(num, min(p, q)))

Fixed submission:
# nCk(mod p)の計算
from math import factorial
X, Y = map(int, input().split())
MOD = 10**9+7
MAX = 10**6+1

 # a!のテーブルfact
fact = [0] * MAX
# (a!)^-1のテーブルfinv
finv = [0] * MAX

def comb_init():
    # a!と(a!)^-1のテーブルを作る
    # 累積積のイメージ
    fact[0] = fact[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fact[i] = i * fact[i-1] % MOD
        finv[i] = pow(i, MOD-2, MOD) * finv[i-1] % MOD

def comb(n, r):
    return fact[n] * (finv[n-r] * finv[r] % MOD) % MOD    

n = (X+Y)//3
r = X-n
if not 0 <= r <= n:
    print(0)
    exit()

if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    comb_init()
    print(comb(num, p))

Buggy python submission (verdict: Runtime Error):
from functools import reduce
X, Y = map(int, input().split())
mod = 10**9+7

def comb(n, r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    print(comb(num, p))


Fixed submission:
# nCk(mod p)の計算
from math import factorial
X, Y = map(int, input().split())
MOD = 10**9+7
MAX = 10**6+1

 # a!のテーブルfact
fact = [0] * MAX
# (a!)^-1のテーブルfinv
finv = [0] * MAX

def comb_init():
    # a!と(a!)^-1のテーブルを作る
    # 累積積のイメージ
    fact[0] = fact[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fact[i] = i * fact[i-1] % MOD
        finv[i] = pow(i, MOD-2, MOD) * finv[i-1] % MOD

def comb(n, r):
    return fact[n] * (finv[n-r] * finv[r] % MOD) % MOD    

n = (X+Y)//3
r = X-n
if not 0 <= r <= n:
    print(0)
    exit()

if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    comb_init()
    print(comb(num, p))
Buggy python submission (verdict: Runtime Error):
N=int(input())
B=list(map(int,input().split()))
A=[]
A.append(B[0])
A.append(B[0])
num=0
for i in B:
    if i==B[0]:
        num+=1
        continue
    elif A[num]<=B[num]:
        A.append(B[num])
        num+=1
    else:
        A[num]=B[num]
        A.append(B[num])
        num+=1

max_sum=0
for i in A:
    max_sum+=i
print(max_sum)



Fixed submission:
N=int(input())
B=list(map(int,input().split()))
A=[]
A.append(B[0])
A.append(B[0])
num=0
for i in B:
    if num==0:        
        num+=1
    elif A[num]<=B[num]:
        A.append(B[num])
        num+=1
    elif A[num]>B[num]:
        A[num]=B[num]
        A.append(B[num])
        num+=1

max_sum=0
for i in A:
    max_sum+=i
print(max_sum)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
S = input()

h = 0
for i in range(len(S)-1):
  if s[i] == S[i+1]:
    h += 1
h += 2*K
print(min(N-1, h))


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

h = 0
for i in range(len(S)-1):
  if S[i] == S[i+1]:
    h += 1
h += 2*K
print(min(N-1, h))
Buggy python submission (verdict: Runtime Error):
s = input()
cand = []
ans = [0] * len(s)

# RLの位置を把握
for i in range(len(s)-1):
    if s[i] == "R" and s[i+1] == "L":
        cand.append(i)
for j in range(len(cand)):
    if j == 0:
        lst_l = s[:cand[j]]
        lst_r = s[cand[j]+2:cand[j+1]]
    elif j == len(cand)-1:
        lst_l = s[cand[j-1]+2:cand[j]]
        lst_r = s[cand[j]+2:]
    else:
        lst_l = s[cand[j-1]+2:cand[j]]
        lst_r = s[cand[j]+2:cand[j+1]] 
    num_R = len([i for i in lst_l if i == "R"])
    num_L = len([i for i in lst_r if i == "L"])
    num = num_R + num_L
    j = cand[j]
    if num % 2 == 0:
        ans[j:j+2] = [num//2+1, num//2+1]
    else:
        if num_R == 0 or num_L == 0:
            if num_R == 0:
                ans[j:j+2] = [num_L-(num_L//2)+1, num_L//2+1]
            else:
                ans[j:j+2] = [num_R//2+1, num_R-(num_R//2)+1]
        else:
            ans[j:j+2] = [num_R+1, num_L+1]
print(*ans)

Fixed submission:
S = input()
seq = [1]
pos = []
for i,(a,b) in enumerate(zip(S,S[1:])):
    if a+b == 'RL':
        pos.append(i)
    if a==b:
        seq[-1] += 1
    else:
        seq.append(1)

ans = [0] * len(S)
for r,l,p in zip(seq[::2],seq[1::2],pos):
    ans[p] = ans[p+1] = (r+l)//2
    if (r+l)%2:
        if r > l:
            ans[p] += 1
        else:
            ans[p+1] += 1
        if max(r,l)%2==0:
            ans[p],ans[p+1] = ans[p+1],ans[p]
print(*ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
S = input()
t = defaultdict(int)
for i in s:
  t[i] += 1
if len(t.keys()) == 2:
  for i in t.values():
    if i != 2:
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")

Fixed submission:
from collections import defaultdict
S = input()
t = defaultdict(int)
for i in S:
  t[i] += 1
if len(t.keys()) == 2:
  for i in t.values():
    if i != 2:
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
S = input()
t = defaultdict(int)
for i in s:
  t[i] += 1
if len(t.keys()) == 2:
  for i in t.values():
    if i != 2:
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")

Fixed submission:
from collections import defaultdict
S = input()
t = defaultdict(int)
for i in S:
  t[i] += 1
if len(t.keys()) == 2:
  for i in t.values():
    if i != 2:
      print("No")
      break
  else:
    print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1
fact = [1] * MAX

for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

def comb_init():
    fact[0], fact[1] = 1, 1
    for i in range(2, MAX):
        fact[i] = fact[i-1] * i

def comb(n, r):
    return (fact[n]%MOD) * pow(fact[r], -1, MOD) * pow(fact[n-r], -1, MOD) 

def f(k):
    idx = k // 2
    num = 0
    for i in range(1, idx+1):
        num += comb(k-i, i)
        num %= MOD
    return num+1

comb_init()
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    ans *= f(between)
    ans %= MOD
print(ans)

Fixed submission:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1

fib = [0] * MAX
fib[0], fib[1] = 1, 2
for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

for i in range(2, MAX):
    fib[i] = fib[i-1] + fib[i-2]
    
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    if not between:
        continue
    ans *= fib[between-1]
    ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):


def main():
	N,M=map(int,input().split())
	like=[0]*M
	for _ in range(N):
    	K,*A=map(int,input().split())
    	for num in A:
        	like[num-1]+=1
print(like.count(N))

if __name__=='__main__':
    main()




     


Fixed submission:
N,M=map(int,input().split())
set_list=[]
sets=set()
for i in range(N):
    s=input().split()
    s.pop(0)
    set_list.append(set(s))
for set in set_list:
    if len(sets)==0:
        sets=set
    else:
        sets=sets.intersection(set)
print(len(sets))
Buggy python submission (verdict: Runtime Error):
def main():
    import math
    n = int(input())
    h = list(map(int, input().split()))
    # dpテーブル作成,スタート地点のdpテーブルの値は0にする
    dp =[math.inf] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min([dp[i], dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    h = list(map(int, input().split()))
    # dpテーブル作成,スタート地点のdpテーブルの値は0にする
    dp =[10**5] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min([dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    import math
    n = int(input())
    h = list(map(int, input().split()))
    # dpテーブル作成,スタート地点のdpテーブルの値は0にする
    dp =[math.inf] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min([dp[i], dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    h = list(map(int, input().split()))
    # dpテーブル作成,スタート地点のdpテーブルの値は0にする
    dp =[10**5] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min([dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import math
def main():
    n = int(input())
    h = list(map(int, input().split()))
    # dpテーブル作成,スタート地点のdpテーブルの値は0にする
    dp =[math.inf] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min([dp[i], dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n = int(input())
    h = list(map(int, input().split()))
    # dpテーブル作成,スタート地点のdpテーブルの値は0にする
    dp =[10**5] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min([dp[i-1]+abs(h[i-1]-h[i]), dp[i-2]+abs(h[i-2]-h[i])])
    print(dp[n-1])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    h = list(map(int, input().rstrip().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()