Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)

    for i in range(M):
        A, B = map(int, input().split())
        uf.union(A, B)
    # print(uf.all_group_members())
    ans = max([len(m) for g, m in uf.all_group_members().items()])
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)

    for i in range(M):
        A, B = map(int, input().split())
        uf.union(A, B)
    # print(uf.all_group_members())
    # print(uf.parents)
    ans = -min(uf.parents)
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    minA = min(A)
    maxA = max(A)


    d = 2
    is_pairwise = True
    cnt = 0
    for a in A:
        if a % d == 0:
            cnt += 1
        if cnt == 2:
            is_pairwise = False
            break

    if is_pairwise:
        for d in range(3, maxA+1, 2):
            cnt = 0
            for a in A:
                if a % d == 0:
                    cnt += 1
                if cnt == 2:
                    is_pairwise = False
                    break
            if not is_pairwise:
                break
        
        if is_pairwise:
            print('pairwise coprime')
            return



    div_min_A = make_divisors(minA)
    div_min_A
    # print(div_min_A)

    s_max = int(A[-1] ** 0.5) + 1

    is_setwise = True
    # 最小値の約数（1以外）で割れる数が何個あるか調べ、
    # 2個以上あるなら
    for d in div_min_A[1:]:
        cnt = 0
        d_is_setwise_div = True
        for a in A:
            if a % d != 0:
                d_is_setwise_div = False
                break
        if d_is_setwise_div:
            is_setwise = False
            break
    
    if is_setwise:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()

Fixed submission:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

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

    all_prime = set()
    is_pairwise = True
    for a in A:
        facts = set(prime_factorize(a))
        if len(facts & all_prime) != 0:
            is_pairwise = False
            break

        all_prime |= facts

    if is_pairwise:
        print('pairwise coprime')
        return

    _gcd = A[0]
    is_setwise = False
    for a in A[1:]:
        _gcd = gcd(a, _gcd)
        if _gcd == 1:
            is_setwise = True
            break
    
    if is_setwise:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import collections

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

    c = collections.Counter(A)
    # 重複排除
    A.sort()
    dq = deque()
    before = 0
    for a in A:
        dq.append(a)

    ans = 0
    while dq:
        a = dq.popleft()
        if c[a] == 1:
            ans += 1
        dq2 = deque()
        while dq:
            a2 = dq.popleft()
            if a2 % a:
                dq2.append(a2)
        dq = dq2

    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
import collections

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

    _max = 10 ** 6 + 1

    c = collections.Counter(A)

    ok_flag = [True] * _max   
    uniq_A = list(c.keys())
    uniq_A.sort()
    ans = 0

    for a in uniq_A:
        if ok_flag[a]:
            if c[a] == 1:
                ans += 1

            for i in range((_max - 1) // a + 1):
                ok_flag[a*i] = False
    
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    dp = [[0] * (S + 1) for i in range(N + 1)]
    dp[0][0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp[i] = [2 * x for x in dp[i-1]]
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        for j in range(S + 1 - a):
            if dp[i-1][j] != 0:
                dp[i][j + a] += dp[i-1][j]
        
        # 大きくなりすぎないように逐次MODをとる
        for j in range(S + 1):
            dp[i][j] %= MOD

    # print(*dp, sep='\n')
    print(dp[N][S])

if __name__ == '__main__':
    main()

Fixed submission:
import numpy as np

def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    # dp = [[0] * (S + 1) for i in range(N + 1)]
    # dp[0][0] = 1
    
    dp = np.zeros(S + 1, np.int64)
    dp[0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp_next = 2 * dp
        
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        dp_next[a:] += dp[:-a] # dp[:-a] = dp[:len(dp)-a]       

        # 大きくなりすぎないように逐次MODをとる
        dp_next %= MOD
        
        dp = dp_next

    # print(*dp, sep='\n')
    print(dp[S])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):


def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    p = [-1] * n
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
            if d[v]+cost[v][j] < d[j]:
                p[j] = v
            
            d[j] = min(d[j], d[v]+cost[v][j])
    return d, p

def main():
    N, M = map(int, input().split())
    cost = [[float("inf") for i in range(N)] for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        cost[a-1][b-1] = 1
        cost[b-1][a-1] = 1
    
    d, p = dijkstra(0, N, M, cost)

    ans = [x + 1 for x in p[1:]]

    print('Yes')
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque

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

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

    dist = [-1] * N
    que = deque([0])
    dist[0] = 0
    parent = [-1] * N
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            parent[w] = v
            que.append(w)

    ans = [x + 1 for x in parent[1:]]

    print('Yes')
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))

    cnt = 0
    for i in range(N-2):
        for j in range(i + A[i] + 1, N):
            if A[i] + A[j] == j - i:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Fixed submission:
import collections
def main():
    N = int(input())
    A = list(map(int, input().split()))

    B = [a+i for i, a in enumerate(A)]
    C = [a-i for i, a in enumerate(A)]

    
    c = collections.Counter(C)

    ans = 0
    for b in B:
        ans += c.get(-b, 0)
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))

    cnt = 0
    for d in range(N):
        for i in range(N-d):
            if A[i] + A[i+d] == d:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Fixed submission:
import collections
def main():
    N = int(input())
    A = list(map(int, input().split()))

    B = [a+i for i, a in enumerate(A)]
    C = [a-i for i, a in enumerate(A)]

    
    c = collections.Counter(C)

    ans = 0
    for b in B:
        ans += c.get(-b, 0)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):

itos = ["A", "B", "C"]

def swap(ABC, f, t):
    ABC[f] -= 1
    ABC[t] += 1
    return itos[t]


def main():
    N, A, B, C = map(int, input().split())
    S = [input() for i in range(N)]
    ABC = [A, B, C]
    StoP = {"AB": (0, 1), "BC": (1, 2), "AC": (0, 2)}
    itos = ["A", "B", "C"]
    L = []
    for i in range(N):
        x, y = StoP[S[i]]

        if ABC[x] == 0 and ABC[y] == 0:
            print("No")
            return
        if ABC[x] == 1 and ABC[y] == 1 and i < N - 1 and S[i] != S[i+1]:
            x2, y2 = StoP(S[i+1])
            if x in [x2, y2]:
                L.append(swap(ABC, y, x))
            else:
                L.append(swap(ABC, x, y))
        elif ABC[x] < ABC[y]:
            L.append(swap(ABC, y, x))
        else:
            L.append(swap(ABC, x, y))

    print("Yes")
    print(*L, sep='\n')
if __name__ == '__main__':
    main()

Fixed submission:

itos = ["A", "B", "C"]

def swap(ABC, f, t):
    ABC[f] -= 1
    ABC[t] += 1
    return itos[t]


def main():
    N, A, B, C = map(int, input().split())
    S = [input() for i in range(N)]
    ABC = [A, B, C]
    StoP = {"AB": (0, 1), "BC": (1, 2), "AC": (0, 2)}
    itos = ["A", "B", "C"]
    L = []
    for i in range(N):
        x, y = StoP[S[i]]

        if ABC[x] == 0 and ABC[y] == 0:
            print("No")
            return
        if ABC[x] == 1 and ABC[y] == 1 and i < N - 1 and S[i] != S[i+1]:
            x2, y2 = StoP[S[i+1]]
            if x in [x2, y2]:
                L.append(swap(ABC, y, x))
            else:
                L.append(swap(ABC, x, y))
        elif ABC[x] < ABC[y]:
            L.append(swap(ABC, y, x))
        else:
            L.append(swap(ABC, x, y))

    print("Yes")
    print(*L, sep='\n')
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

import collections

c = collections.Counter(A)

ans = []
for a in A:
  ans_a = 0
  for k, v in c.items():
    if k == a:
      ans_a += max(v - 1, 0) * max(v - 2, 0) // 2
    else:
      ans_a += v * max(v - 1, 0) // 2
  ans.append(ans_a)
print(*ans, sep='\n')




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

import collections

c = collections.Counter(A)

sum_all = sum([v * max(v - 1, 0) // 2 for k, v in c.items()])

ans = []
for a in A:
  b = c[a]
  ans_a = sum_all - (b * max(b - 1, 0) // 2) + (max(b - 1, 0) * max(b - 2, 0) // 2)
  ans.append(ans_a)
print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

start = 0
cnt = 0
for i in range(1, N+1):
  try:
    start = a[start:].index(i)
  except:
    break
  else:
    cnt += 1

if cnt == 0:
  print(-1)
else:
  print(N - cnt)

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

start = 0
cnt = 0
for i in range(1, N+1):
  try:
    start = a.index(i, start)
  except:
    break
  else:
    cnt += 1

if cnt == 0:
  print(-1)
else:
  print(N - cnt)

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

start = 0
cnt = 0
for i in range(1, N+1):
  try:
    start = a[start:].index(i)
  except:
    break
  else:
    cnt += 1

if cnt == 0:
  print(-1)
else:
  print(N - cnt)

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

start = 0
cnt = 0
for i in range(1, N+1):
  try:
    start = a.index(i, start)
  except:
    break
  else:
    cnt += 1

if cnt == 0:
  print(-1)
else:
  print(N - cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = map(int, input().split())
MOD = 10**9 + 7

# p[n]: 最下位ビットからnビット目が1になっている数字の個数
p=[0] * 60
for a in A:
  for i in range(60):
    p[i] += (a>>i)&1

#print(p)
ans = 0
for i in range(60):
  # nビット目同士を足したときの合計
  sn = (N-p[i]) * p[i]
  ans = (ans + (sn << i)) % MOD

print(ans)

Fixed submission:
N = int(input())
A = map(int, input().split())
MOD = 10**9 + 7

# p[n]: 最下位ビットからnビット目が1になっている数字の個数
p=[0] * 60
for a in A:
  for i in range(60):
    p[i] += (a>>i)&1

#print(p)
ans = 0
for i in range(60):
  # nビット目同士を足したときの合計
  sn = (N-p[i]) * p[i]
  ans = (ans + (sn << i)) % MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

A, B = map(int, input().split())
gcd_AB = gcd(A, B)
if gcd_AB == 1:
  print(1)
  exit(0)
if gcd_AB == 2:
  print(2)
  exit(0)

so_list = []
for i in range(3, gcd_AB, 2):
  if A%i !=0 or B%i !=0:
    continue
  flag=True
  for s in so_list:
    if i%s == 0:
      flag=False
      break
  if flag:
    so_list.append(i)

if A%2 ==0 or B%2 ==0:
  so_list.insert(0,2)
#print(so_list)
print(len(so_list) + 1)


Fixed submission:
import math
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
    
A, B = map(int, input().split())
gcd_AB = gcd(A, B)
# 素因数分解
p_list = prime_factorize(gcd_AB)
#print(p_list)
print(len(set(p_list))+1)

Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

A, B = map(int, input().split())
gcd_AB = gcd(A, B)
dA=[x for x in range(1, gcd_AB) if A%x == 0]
dB=[x for x in range(1, gcd_AB) if B%x == 0]
cd=[x for x in dA if x in dB]
cd.append(gcd_AB)
#print(A, B, gcd_AB)
#print(dA)
#print(dB)
#print(cd)
so_list = []
for i in cd[1:]:
  ok=True
  for s in so_list:
    if i % s == 0:
      ok=False
      break
  if ok:
    so_list.append(i)

print(len(so_list) + 1)


Fixed submission:
import math
def gcd(x, y):
  if y == 0:
     return x
  else:
     return gcd(y, x % y)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
    
A, B = map(int, input().split())
gcd_AB = gcd(A, B)
# 素因数分解
p_list = prime_factorize(gcd_AB)
#print(p_list)
print(len(set(p_list))+1)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M = map(int, input().split())
a = list(map(int, input().split()))
A = np.array(a)

for i in range(M):
  x = A.argmax()
  if A[x] == 0:
    break
  A[x] >>= 1

print(sum(A))



Fixed submission:
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

for i in range(M):
  if A[N-1] == 0:
    break
  A[N-1] >>= 1
  A = sorted(A)
  
print(sum(A))

Fixed submission:
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

for i in range(M):
  A[N-1] >>= 1
  A = sorted(A)
print(sum(A))

Fixed submission:
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read

N, K, *h = map(int, read().split())
# print(N, K, h)

# コスト無限大で初期化
INF = float("inf")
dp = [ INF ] * N
dp[0] = 0

for i in range(1, N):
  # i番目の梯子までの最小移動コストは、
  # 「i-1番目までの移動コスト」+「i-1番目からi番目への移動コスト」
  # もしくは、
  # 「i-2番目までの移動コスト」+「i-2番目からi番目への移動コスト」
  # ...
  # もしくは、
  # 「i-K番目までの移動コスト」+「i-K番目からi番目への移動コスト」
  # のうち、最も小さいものが、最小移動コストになる
  
  # jをi-Kからi-1まで変化させながら、最小の組み合わせを探す
  # ただし、jが負の値にならないよう注意
  j_min = max(0, i-K)
  dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(j_min, i))
  # print(dp)

print(dp[N-1])

Fixed submission:
import numpy as np
import sys
N, K = map(int,input().split())
h = np.fromstring(input(), dtype=np.int64, sep=' ')

# コスト無限大で初期化
INF = 10**10
dp = np.array([INF]*N)
dp[0] = 0
for i in range(1, N):
  # i番目の梯子までの最小移動コストは、
  # 「i-1番目までの移動コスト」+「i-1番目からi番目への移動コスト」
  # もしくは、
  # 「i-2番目までの移動コスト」+「i-2番目からi番目への移動コスト」
  # ...
  # もしくは、
  # 「i-K番目までの移動コスト」+「i-K番目からi番目への移動コスト」
  # のうち、最も小さいものが、最小移動コストになる
  
  # jをi-Kからi-1まで変化させながら、最小の組み合わせを探す
  # ただし、jが負の値にならないよう注意
  j_min = max(0, i-K)
  dp[i] = np.min(dp[j_min: i] + np.abs(h[i] - h[j_min: i]))

print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read

N, K, *h = map(int, read().split())
# print(N, K, h)

def chmin(l, i, v):
  if l[i] > v:
    l[i] = v
    return True
  return False

def chmax(l, i, v):
  if l[i] < v:
    l[i] = v
    return True
  return False

# コスト無限大で初期化
INF = float("inf")
dp = [ INF ] * N
dp[0] = 0

for i in range(1, N):
  # i番目の梯子までの最小移動コストは、
  # 「i-1番目までの移動コスト」+「i-1番目からi番目への移動コスト」
  # もしくは、
  # 「i-2番目までの移動コスト」+「i-2番目からi番目への移動コスト」
  # ...
  # もしくは、
  # 「i-K番目までの移動コスト」+「i-K番目からi番目への移動コスト」
  # のうち、最も小さいものが、最小移動コストになる
  
  # jをi-Kからi-1まで変化させながら、最小の組み合わせを探す
  # ただし、jが負の値にならないよう注意
  for j in range(max(0, i-K), i):
    chmin(dp, i, dp[j] + abs(h[i] - h[j]))
  # print(dp)

print(dp[N-1])

Fixed submission:
import numpy as np
import sys
N, K = map(int,input().split())
h = np.fromstring(input(), dtype=np.int64, sep=' ')

# コスト無限大で初期化
INF = 10**10
dp = np.array([INF]*N)
dp[0] = 0
for i in range(1, N):
  # i番目の梯子までの最小移動コストは、
  # 「i-1番目までの移動コスト」+「i-1番目からi番目への移動コスト」
  # もしくは、
  # 「i-2番目までの移動コスト」+「i-2番目からi番目への移動コスト」
  # ...
  # もしくは、
  # 「i-K番目までの移動コスト」+「i-K番目からi番目への移動コスト」
  # のうち、最も小さいものが、最小移動コストになる
  
  # jをi-Kからi-1まで変化させながら、最小の組み合わせを探す
  # ただし、jが負の値にならないよう注意
  j_min = max(0, i-K)
  dp[i] = np.min(dp[j_min: i] + np.abs(h[i] - h[j_min: i]))

print(dp[N-1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=n%100
b=a%10
if b==3:
  print("bon")
if b==2 || b==4 || b==5 || b==7 || b==9:
  print("hon")
if b==0 || b==1 || b==6 || b==8:
  print ("pon")

Fixed submission:
n=int(input())
a=n%100
b=a%10
if b==3:
  print("bon")
if b==2 or b==4 or b==5 or b==7 or b==9:
  print("hon")
if b==0 or b==1 or b==6 or b==8:
  print ("pon")
Buggy python submission (verdict: Time Limit Exceeded):
import math


def make_divisors(n):
    d = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i != 0:
            continue
        if i * i == n:
            d += 1
        else:
            d += 2
    return d


def f(n):
    return sum(make_divisors(n - i) for i in range(1, n))


def f2(n):
    d = 0
    c = 0
    for i in range(1, n):
        e = 0
        if i * i == n:
            e -= 1
        elif n % i == 0:
            e -= 1
        e += n // i
        d += e

    return d

def main():
    print(f(int(input())))


if __name__ == '__main__':
    main()


Fixed submission:
import math


def f2(n):
    d = 0
    c = 0
    for i in range(1, n):
        e = 0
        if i * i == n:
            e -= 1
        elif n % i == 0:
            e -= 1
        e += n // i
        d += e

    return d

def main():
    print(f2(int(input())))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import math

def make_divisors(n):
    d = 0
    i = 1
    d2 = True
    m = int(math.sqrt(n))
    for i in reversed(range(1, m + 1)):
        if n % i != 0:
            continue
        if i * i == n:
            d += 1
        else:
            d += 2
    return d


def f(n):
    count = 0
    for i in range(1, n):
        count += make_divisors(n - i)
    return count


def main():
    print(f(int(input())))


if __name__ == '__main__':
    main()


Fixed submission:
import math


def f2(n):
    d = 0
    c = 0
    for i in range(1, n):
        e = 0
        if i * i == n:
            e -= 1
        elif n % i == 0:
            e -= 1
        e += n // i
        d += e

    return d

def main():
    print(f2(int(input())))


if __name__ == '__main__':
    main()