Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*n
dp[0]=0

for i in range(1,k):
  dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,i+1)])

for i in range(k,n):
  dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,k+1)])


print(dp[n-1])

Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(min(K,i)):
      dp[i]=min(dp[i],dp[i-num-1]+abs(h[i]-h[i-num-1]))
 
print(dp[N-1])

Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])

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

dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      dp[i]=min(dp[i],dp[i-num-1]+abs(h[i]-h[i-num-1]))
 
print(dp[N-1])

Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])

Fixed submission:
N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()

len_s=len(s)
len_t=len(t)

# dp[len(s)][len(t)]
# dp表をつくる
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(1,len_s+1):
  for j in range(1,len_t+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i][j-1],dp[i-1][j])
#print(dp)

rev = ""
#復元する
i = len_s
j = len_t
while (i>=1 and j>=1):
  if dp[i][j] == dp[i][j-1]:
    j -=1
  elif dp[i][j] == dp[i-1][j]:
    i -=1
  else:
    rev = t[j-1] + rev
    i -=1
    j -=1

print(rev)

Fixed submission:
s = input()
t = input()

len_s=len(s)
len_t=len(t)

# dp[len(s)][len(t)]
# dp表をつくる
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(1,len_s+1):
  for j in range(1,len_t+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i][j-1],dp[i-1][j])
#print(dp)

#復元する
rev = ""
i = len_s
j = len_t
while (i>=1 and j>=1):
  if dp[i][j] == dp[i][j-1]:
    j -=1
  elif dp[i][j] == dp[i-1][j]:
    i -=1
  else:
    rev = t[j-1] + rev
    i -=1
    j -=1

print(rev)
Buggy python submission (verdict: Runtime Error):
H,W = map(int,input().split())
a = [list(input()) for i in range(H)]

dp=[[0]*(W) for i in range(H)]

for i in range(H):
  if a[i][0]==".":
    dp[i][0]=1

for j in range(W):
  if a[0][i]==".":
    dp[0][i]=1

for i in range(1,H):
  for j in range(1,W):
    if a[i][j]==".":
      dp[i][j]=dp[i-1][j]+dp[i][j-1]

print(dp[H-1][W-1])

Fixed submission:
H,W = map(int,input().split())
a = [list(input()) for i in range(H)]

dp=[[0]*(W) for i in range(H)]

flagH = 0
flagW = 0

for i in range(H):
  if a[i][0]=="." and flagH==0:
    dp[i][0]=1
  else:
    dp[i][0]=0
    flagH=1

for j in range(W):
  if a[0][j]=="." and flagW==0:
    dp[0][j]=1
  else:
    dp[0][j]=0
    flagW=1

for i in range(1,H):
  for j in range(1,W):
    if a[i][j]==".":
      dp[i][j]=dp[i-1][j]+dp[i][j-1]

print(dp[H-1][W-1]%1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = list(map(float,input().split()))

#dp[投げたコイン枚数][表のコイン枚数] 
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = dp[i-1][0]*(1-p[i-1])
  dp[i][i] = dp[i-1][i-1]*p[i-1]
  for j in range(1,i):
    dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
print(sum(dp[n][(n+1)//2:]))

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

#dp[投げたコイン枚数][表のコイン枚数] 
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = dp[i-1][0]*(1-p[i-1])
  dp[i][i] = dp[i-1][i-1]*p[i-1]
  for j in range(1,i):
    dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
print(sum(dp[n][(n+1)//2:]))

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

dp = [[0]*(N+1) for i in range(N+1)]

dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1,N):
  dp[i][0] = dp[i-1][0]*(1-p[i])
  for j in range(1,i+2):
    dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i]
    
ans=0
A=int((N+1)/2)

for j in range(A,N+1):
   ans += dp[N-1][j]
    
print(ans)

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

#dp[投げたコイン枚数][表のコイン枚数] 
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = dp[i-1][0]*(1-p[i-1])
  dp[i][i] = dp[i-1][i-1]*p[i-1]
  for j in range(1,i):
    dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
print(sum(dp[n][(n+1)//2:]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[-1]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

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

#dp[l][r] = [l, r)区間のスライムを
dp = [[float("inf")]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != float("inf"):
        return dp[l][r]
    else:
        res = float("inf")
        if (r - l) == 1:
            dp[l][r] = 0
            return dp[l][r]
        for k in range(l, r):
            if k == l or k == r:
                continue
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])

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

#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[-1]*(n+1) for i in range(n+1)]
for i in range(n):
    dp[i][i] = 0

#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0]*(n+1)
for i in range(n):
    cost[i+1] = cost[i] + a[i]

#メモ化再帰でdp[0][n]求める
def dfs(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            #dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k) + dfs(k, r) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]

dfs(0, n)
print(dp[0][n])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
MOD = 10**9 + 7

tree = [[] for i in range(n)]
for i in range(n-1):
    x, y = info[i]
    x -= 1
    y -= 1
    tree[x].append(y)
    tree[y].append(x)

def solve(pos):
    b = 1
    w = 1
    flag = False
    for next_pos in tree[pos]:
        if not visited[next_pos]:
            visited[next_pos] = True
            flag = True
            tmp_b, tmp_w = solve(next_pos)
            w *= (tmp_b + tmp_w)
            b *= tmp_w
            w %= MOD
            b %= MOD
    if not flag:
        black[pos] = 1
        white[pos] = 1
        return (black[pos], white[pos])
    else:
        black[pos] = b
        white[pos] = w
        return (black[pos], white[pos])

black = [0]*n
white = [0]*n
visited = [False]*n
visited[0] = True
print(sum(solve(0)) % MOD)

Fixed submission:
import sys


sys.setrecursionlimit(100000)
MOD = 10**9 + 7
n = int(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    tmp1, tmp2 = map(int, input().split())
    tree[tmp1 - 1].append(tmp2 - 1) 
    tree[tmp2 - 1].append(tmp1 - 1)
visited = [False]*n

def dfs(i):
    visited[i] = True
    if all([visited[j] for j in tree[i]]):
        return 1, 1  #黒の通り数, 白の通り数
    else:
        ans1 = 1
        ans2 = 1
        for j in tree[i]:
            if not visited[j]:
                tmp1, tmp2 = dfs(j)
                ans1 *= tmp2
                ans2 *= (tmp1 + tmp2)
                ans1 %= MOD
                ans2 %= MOD
        return ans1, ans2  #黒の通り数, 白の通り数

print(sum(dfs(0)) % MOD)

Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7
n = int(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    tmp1, tmp2 = map(int, input().split())
    tree[tmp1 - 1].append(tmp2 - 1) 
    tree[tmp2 - 1].append(tmp1 - 1)
visited = [False]*n

def dfs(i):
    visited[i] = True
    if all([visited[j] for j in tree[i]]):
        return 1, 1  #黒の通り数, 白の通り数
    else:
        ans1 = 1
        ans2 = 1
        for j in tree[i]:
            if not visited[j]:
                tmp1, tmp2 = dfs(j)
                ans1 *= tmp2
                ans2 *= (tmp1 + tmp2)
                ans1 %= MOD
                ans2 %= MOD
        return ans1, ans2  #黒の通り数, 白の通り数

print(sum(dfs(0)) % MOD)

Fixed submission:
import sys


sys.setrecursionlimit(100000)
MOD = 10**9 + 7
n = int(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    tmp1, tmp2 = map(int, input().split())
    tree[tmp1 - 1].append(tmp2 - 1) 
    tree[tmp2 - 1].append(tmp1 - 1)
visited = [False]*n

def dfs(i):
    visited[i] = True
    if all([visited[j] for j in tree[i]]):
        return 1, 1  #黒の通り数, 白の通り数
    else:
        ans1 = 1
        ans2 = 1
        for j in tree[i]:
            if not visited[j]:
                tmp1, tmp2 = dfs(j)
                ans1 *= tmp2
                ans2 *= (tmp1 + tmp2)
                ans1 %= MOD
                ans2 %= MOD
        return ans1, ans2  #黒の通り数, 白の通り数

print(sum(dfs(0)) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
dp = [list(map(int, input().split())) for i in range(n)]
MOD = 10**9 + 7

def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
    return C

#A**n
def pow(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n  = n // 2
    return B

ans_matrix = pow(dp, k, MOD)
ans = 0
for i in range(n):
    ans += sum(ans_matrix[i])
    ans %= MOD
print(ans)

Fixed submission:
n, k = map(int, input().split())
dp = [list(map(int, input().split())) for i in range(n)]
MOD = 10**9 + 7

def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
    return C

#A**n
def pow(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n  = n // 2
    return B

ans_matrix = pow(dp, k, MOD)
ans = 0
for i in range(n):
    ans += sum(ans_matrix[i])
    ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
N, H, W = map(int,input().split())

count =0

for num in range(N):
  A, B = map(int,inp().split())
  if H >=A and W>=B:
    count +=1
print(count)


Fixed submission:
N, H, W = map(int,input().split())
 
count =0
 
for num in range(N):
  A, B = map(int,input().split())
  if A >=H and B >= W:
    count +=1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int,input().split())
 
output=1
 
if P==1:
  outtput=1
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

Fixed submission:
N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

Buggy python submission (verdict: Runtime Error):
N, P = map(int,input().split())
 
output=1
 
if P==1:
  
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

Fixed submission:
N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int,input().split())
 
output=1
 
for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

Fixed submission:
N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int,input().split())
 
output=1
 
for num in range(2,round(P**(1/N))+1):
  for i in range(100):
    if P%(num**N) == 0:
      P = P/(num**N)
      output = num*output
    else:
      break
 
print(output)

Fixed submission:
N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

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

output=1

for num in range(2,round(P**(1/N))+1):
  for i in range(10000):
    if P%(num**N) == 0:
      P = P/(num**N)
      output = num*output
    else:
      break

print(output)



Fixed submission:
N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)
Buggy python submission (verdict: Runtime Error):
import bisect


h, w, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

set_ = set()
tate = [[] for i in range(w + 1)]
for i, j in info:
    tate[j].append(i)
    set_.add((i, j))
for j in range(w + 1):
    tate[j].append(h + 1)

i, j = 1, 1
ans = 10 ** 18
while True:
    if i == w + 1:
        break
    ind = bisect.bisect_right(tate[j], i)
    ans = min(ans, tate[j][ind] - 1)

    i += 1
    if (i, j + 1) in set_ or j == w:
        pass
    else:
        j += 1

print(ans)

Fixed submission:
from operator import itemgetter
import bisect


h, w, n = map(int, input().split())
info = [tuple(map(int, input().split())) for i in range(n)]

memo = set()
for i, j in info:
    memo.add(i * 10**6 + j)

pos = [[] for _ in range(w + 1)]
info = sorted(info, key = itemgetter(0))
for i, j in info:
    pos[j].append(i)

ans = 10**18
pos_i, pos_j = 1, 1
ind = bisect.bisect_right(pos[pos_j], pos_i)
try:
    ans = min(pos[pos_j][ind] - 1, ans)
except:
    pass

while True:
    if (pos_i + 1) * 10**6 + pos_j in memo or pos_i == h:
        ans = min(ans, pos_i)
        break
    pos_i += 1

    if pos_i * 10**6 + (pos_j + 1) in memo or pos_j == w:
        continue
    else:
        pos_j += 1
    ind = bisect.bisect_right(pos[pos_j], pos_i)
    try:
        ans = min(pos[pos_j][ind] - 1, ans)
    except:
        pass
print(ans)

Buggy python submission (verdict: Runtime Error):
from operator import itemgetter
import bisect


h, w, n = map(int, input().split())
info = [tuple(map(int, input().split())) for i in range(n)]

memo = set()
for i, j in info:
    memo.add(i*10**6 + j)

pos = [[] for _ in range(w + 1)]
info = sorted(info, key = itemgetter(1))
for i, j in info:
    pos[j].append(i)

ans = 10**9
pos_i, pos_j = 1, 1
while True:
    if (pos_i + 1)*10**6 + pos_j in memo:
        break
    if pos_i == h:
        ans = min(ans, h)
        break
    pos_i += 1

    if pos_i*10**6 + pos_j + 1 in memo:
        continue
    else:
        pos_j += 1
    ind = bisect.bisect_right(pos[pos_j], pos_i)
    try:
        ans = min(pos[pos_j][ind] - 1, ans)
    except:
        pass
print(ans)

Fixed submission:
from operator import itemgetter
import bisect


h, w, n = map(int, input().split())
info = [tuple(map(int, input().split())) for i in range(n)]

memo = set()
for i, j in info:
    memo.add(i * 10**6 + j)

pos = [[] for _ in range(w + 1)]
info = sorted(info, key = itemgetter(0))
for i, j in info:
    pos[j].append(i)

ans = 10**18
pos_i, pos_j = 1, 1
ind = bisect.bisect_right(pos[pos_j], pos_i)
try:
    ans = min(pos[pos_j][ind] - 1, ans)
except:
    pass

while True:
    if (pos_i + 1) * 10**6 + pos_j in memo or pos_i == h:
        ans = min(ans, pos_i)
        break
    pos_i += 1

    if pos_i * 10**6 + (pos_j + 1) in memo or pos_j == w:
        continue
    else:
        pos_j += 1
    ind = bisect.bisect_right(pos[pos_j], pos_i)
    try:
        ans = min(pos[pos_j][ind] - 1, ans)
    except:
        pass
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k =map(int,input().split())
h =[0]*n

for i in range(n):
  h[i]= int(input())

sort_h = sorted(h)
diff=10**9

for times in range(n-k+1):
  maxh=0
  minh=10**9
  for i in range(times,k+times):
    if sort_h[i] > maxh:
      maxh= sort_h[i]
    if sort_h[i] < minh:
      minh=sort_h[i]

  if diff > maxh-minh:
    diff = maxh-minh

print(diff)

Fixed submission:
n,k =map(int,input().split())
h =[0]*n

for i in range(n):
  h[i]= int(input())

sort_h = sorted(h)
diffmin=10**9

for times in range(n-k+1):

  diff = sort_h[k+times-1]-sort_h[times]
  if diffmin > diff:
    diffmin=diff

print(diffmin)
Buggy python submission (verdict: Runtime Error):
h,w,k = map(int,input().split())

a=[[0]*w for i in range(h+1)]

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print(a[h][k-1]%1000000007)



Fixed submission:
h,w,k = map(int,input().split())

a=[[0]*w for i in range(h+1)]

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if w==1:
      a[i][j]=a[i-1][j]
    elif j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print(a[h][k-1]%1000000007)

Buggy python submission (verdict: Time Limit Exceeded):
h,w,k = map(int,input().split())

honsu=w


a = 0
def amida(h,w):
  global a
  if h == 0 and w == k:
    return 1
  if h ==0:
    return 0
  if not(1<=w<=honsu):
    return 0
  com1 = fib(honsu-w+1)*fib(w-1)*amida(h-1,w-1)
  com2 = fib(honsu-w+1)*fib(w)*amida(h-1,w) 
  com3 = fib(honsu-w)*fib(w)*amida(h-1,w+1)   
  
  return com1+com2+com3
  
fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

print(amida(h,1)%1000000007)

Fixed submission:
h,w,k = map(int,input().split())

a=[[0]*w for i in range(h+1)]

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if w==1:
      a[i][j]=a[i-1][j]
    elif j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print(a[h][k-1]%1000000007)
Buggy python submission (verdict: Runtime Error):
n = int(input())
 
#zahyo[i][j], iはi番目の地点、j=0はx座標、j=1はy座標、j=2は高さhを表す
zahyo = [list(map(int,input().split())) for i in range(n)] 
flag = 0
for cx in range(101):
  for cy in range(101):
    if flag == 0:
      for i in range(0,n):
        if zahyo[0][2]>0:
          H0 = abs(cx-zahyo[i][0])+abs(cy-zahyo[i][1])+zahyo[i][2]
          break
      for i in range(1,n):
        H = abs(cx-zahyo[i][0])+abs(cy-zahyo[i][1])+zahyo[i][2]  
        if H != H0:
          break
      if H == H0 and H != 0:
        print(cx,cy,H0)
        flag = 1
    else:
      break

Fixed submission:
n = int(input())
 
#zahyo[i][j], iはi番目の地点、j=0はx座標、j=1はy座標、j=2は高さhを表す
zahyo = [list(map(int,input().split())) for i in range(n)] 
 
for cx in range(101):
  for cy in range(101):
    flag =0
    for i in range(n):
      if zahyo[i][2]>0:
        H0 = abs(cx-zahyo[i][0])+abs(cy-zahyo[i][1])+zahyo[i][2]
        break
    for i in range(n):
      if zahyo[i][2] != max(0, H0-abs(cx-zahyo[i][0])-abs(cy-zahyo[i][1])):  
        flag=1
        break
    if flag==0:
      print(cx,cy,H0)
      exit()
Buggy python submission (verdict: Time Limit Exceeded):
n,m =map(int,input().split())

maxnum = m//n

for i in range(maxnum,0,-1):
  if m%i==0:
    print(i)
    break
  

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

maxnum = m//n

for i in range(maxnum,0,-1):
  if m%i==0:
    print(i)
    break