Problem:


Score : 300 points

Problem Statement

In some other world, today is Christmas Eve.

There are N trees planted in Mr. Takaha's garden. The height of the i-th tree (1 \leq i \leq N) is h_i meters.

He decides to choose K trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the decorated trees should be as close to each other as possible.

More specifically, let the height of the tallest decorated tree be h_{max} meters, and the height of the shortest decorated tree be h_{min} meters. The smaller the value h_{max} - h_{min} is, the better. What is the minimum possible value of h_{max} - h_{min}?

Constraints

2 \leq K < N \leq 10^5

1 \leq h_i \leq 10^9

h_i is an integer.

Input

Input is given from Standard Input in the following format:

N K
h_1
h_2
:
h_N

Output

Print the minimum possible value of h_{max} - h_{min}.

Sample Input 1

5 3
10
15
11
14
12

Sample Output 1

2

If we decorate the first, third and fifth trees, h_{max} = 12, h_{min} = 10 so h_{max} - h_{min} = 2. This is optimal.

Sample Input 2

5 3
5
7
5
7
7

Sample Output 2

0

If we decorate the second, fourth and fifth trees, h_{max} = 7, h_{min} = 7 so h_{max} - h_{min} = 0. This is optimal.

There are not too many trees in these sample inputs, but note that there can be at most one hundred thousand trees (we just can't put a sample with a hundred thousand lines here).



Sample input:
5 3
10
15
11
14
12


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
f = [int(input()) for i in range(n)]
li = []
f.sort()
for i in range(n-k+1) :
    li.append(max(f[i:i+k])-min(f[i:i+k]))
print(min(li))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

trees = []

for _ in range(N):
    item = int(input())
    trees.insert(bisect.bisect_left(trees, item), item)    

curmin = 1 + 10**9

for i in range(N-K+1):
    curmin = min(curmin, trees[i+K-1] - trees[i])

print(curmin)

Submission status: Time Limit Exceeded

Solution code:
import sys

r=input().split()
n=int(r[0])
k=int(r[1])
h=sorted([int(x.strip()) for x in sys.stdin.readlines()])

d=[h[x+1]-h[x] for x in range(n-1)]

rui=[0]+[sum(d[:x+1]) for x in range(len(d))]

dd=[rui[x+k-1]-rui[x] for x in range(n-k+1)]
ans=min(dd)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    N = 5
    K = 3
    h = [10,15,11,14,12]
    # N = 5
    # K = 3
    # h = [5,7,5,7,7]

  h.sort()
  ans = 0
  
  for n in range(0,K-1):
    ans += (h[n+1] - h[n])
  
  max_i = len(h)-K+1
  for i in range(1,max_i):
    tmp = 0
    max_j =  range(i, i+K-1)
    for n in max_j:
      tmp += (h[n+1] - h[n])
    if ans > tmp:
      ans = tmp
    if ans == 0:
      print(ans)
      sys.exit()
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    N = 5
    K = 3
    h = [10,15,11,14,12]
    # N = 5
    # K = 3
    # h = [5,7,5,7,7]

  h.sort()
  ans = 0
  
  for n in range(0,K-1):
    ans += (h[n+1] - h[n])
  
  max_i = len(h)-K+1
  for i in range(1,max_i):
    tmp = 0
    max_j =  range(i, i+K-1)
    for n in max_j:
      tmp += (h[n+1] - h[n])
    if ans > tmp:
      ans = tmp
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    N = 5
    K = 3
    h = [10,15,11,14,12]
    # N = 5
    # K = 3
    # h = [5,7,5,7,7]

  h.sort()
  ans = 0
  for n in range(0,K-1):
    ans += (h[n+1] - h[n])
  
  max_i = len(h)-K+1
  for i in range(1,max_i):
    tmp = 0
    for n in range(i, i+K-1):
      tmp += (h[n+1] - h[n])
    if ans > tmp:
      ans = tmp
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    N = 5
    K = 3
    h = [10,15,11,14,12]
    # N = 5
    # K = 3
    # h = [5,7,5,7,7]

  h.sort()
  ans = 0
  for n in range(0,K-1):
    ans += (h[n+1] - h[n])
    
  for i in range(1,len(h)-K+1):
    tmp = 0
    for n in range(i, i+K-1):
      tmp += (h[n+1] - h[n])
    if ans > tmp:
      ans = tmp
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N,K = map(int, input().split())
    h = []
    for _ in range(N):
      h.append(int(input()))
  else:
    # N = 5
    # K = 3
    # h = [10,15,11,14,12]
    N = 5
    K = 3
    h = [5,7,5,7,7]

  h.sort()
  for i in range(0,len(h)-K+1):
    if i == 0:
      ans = 0
      for n in range(0,K-1):
        ans += (h[n+1] - h[n])
    else:
      tmp = 0
      for n in range(i, i+K-1):
        tmp += (h[n+1] - h[n])
      if ans > tmp:
        ans = tmp
  
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
ans = 10**10
for i in range(N - K + 1):
    temp = H[i:i+K]
    ans = min(ans, temp[-1] - temp[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
ans = 10**10
for i in range(N - K + 1):
    ans = min(ans, H[i:i+K][-1] - H[i:i+K][0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]
H = sorted(H)
cand = [H[i:i+K][-1] - H[i:i+K][0] for i in range(N - K + 1)]
print(min(cand))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split(' '))

H = [int(input()) for i in range(N)]
H.sort()
ans = float('inf')
for i in range(N-K+1):
  frag = H[i:i+K]
  ans = min(ans,frag[-1] - frag[0])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split(' '))

H = sorted(list(map(int,(input() for i in range(N)))))
ans = float('inf')
for i in range(N-K+1):
  frag = H[i:i+K]
  ans = min(ans,frag[-1] - frag[0])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
h_list = [int(input()) for i in range(N)]

h_list.sort()
best = 1000000000
for i in range(N - K + 1):
    diff = h_list[i:i+K][-1] - h_list[i:i+K][0]
    if diff < best:
        best = diff

print (best)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
h=[0]*N
s=[0]*K
d=[0]*(N-K+1)

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

for i in range(N-K+1):
  for j in range(K):
    s[j]=h[i+j]
  d[i]=s[K-1]-s[0]
  if d[i] == 0:
    print(0)
    exit()

print(min(d))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
h=[0]*N
s=[0]*K
d=[0]*(N-K+1)

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

for i in range(N-K+1):
  for j in range(K):
    s[j]=h[i+j]
  d[i]=s[K-1]-s[0]

print(min(d))

Submission status: Time Limit Exceeded

Solution code:
import heapq

mINF=-10**10

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

arr=[mINF]*N
for z in range(N):
  heapq.heapreplace(arr,int(input()))

arr2=[mINF]*K
for z in range(K):
  heapq.heapreplace(arr2,heapq.heappop(arr))

r=max(arr2)-min(arr2)

try:
  while True:
    heapq.heapreplace(arr2,heapq.heappop(arr))
    rb=max(arr2)-min(arr2)
    if rb<r:
      r=rb
except Exception:
  pass

print(r)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
H = [int(input()) for _ in range(N)]
ans = 0
H.sort()
for i in range(N-K+1):
    a = H[i:i+K]
    b = max(a)-min(a)
    if i == 0:
        ans = b
    elif ans > b:
        ans = b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
def c():
    n, k = map(int, input().split())
    h = []
    for i in range(n):
        h.append(int(input()))
    h.sort()
    d = collections.deque(maxlen = k)
    mins = []
    while len(d) < k:
        d.append(h.pop())
    while h:
        mins.append(max(d) - min(d))
        d.append(h.pop())
    mins.append(max(d) - min(d))
    print(min(mins))
c()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N):
  if i != 0:
    res.append(h[i]-h[i-1])
m=max(res)
for i in range(N-K+1):
  ans=0
  for j in range(K-1):
    ans+=res[j+i]
  if ans<m:
    m=ans
print(m)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N):
  if i != 0:
    res.append(h[i]-h[i-1])
m=10**10
for i in range(N-K+1):
  ans=0
  for j in range(K-1):
    ans+=res[j+i]
  if ans<m:
    m=ans
print(m)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
h = sorted(int(input()) for _ in range(N))

ans = 1e9+7
for i in range(N-K+1):
  x = h[i:i+K]
  ans = min(ans, x[-1]-x[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
#print(H)
H_diff = abs(H[1:]-H[:-1])
#print(H_diff)
best = np.sum(H_diff[0:K-1])
for i in range(0, len(H_diff)-K+2):
    #print(i)
    if np.sum(H_diff[i:i+K-1]) < best:
        #print(H_diff[i:i+K-1])
        best = np.sum(H_diff[i:i+K-1])
#print('best:{}'.format(best))
print(best)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
H_diff = abs(H[1:]-H[:-1])
best = (np.max(H) - np.min(H))*K
for i in range(0, len(H_diff)-K+2):
    if np.sum(H_diff[i:i+K-1]) < best:
        best = np.sum(H_diff[i:i+K-1])
print(best)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
H_diff = abs(H[1:]-H[:-1])
best = 10**9
for i in range(0, len(H_diff)-K+2):
    s = np.sum(H_diff[i:i+K-1])
    if s < best:
        best = s
print(best)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
#print(H)
H_diff = abs(H[1:]-H[:-1])
#print(H_diff)
best = (H[-1] - H[0])*K
for i in range(0, len(H_diff)-K+2):
    #print(i)
    if np.sum(H_diff[i:i+K-1]) < best:
        #print(H_diff[i:i+K-1])
        best = np.sum(H_diff[i:i+K-1])
#print('best:{}'.format(best))
print(best)

Submission status: Time Limit Exceeded

Solution code:
import scipy as sp

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

tree = sp.array([], dtype = "int")
for i in range(N):
    tree = sp.append(tree, int(input()))

tree.sort()

min_of_sub = 0
print(min(tree[N-K+i] - tree[i] for i in range(N-K+1)))

Submission status: Time Limit Exceeded

Solution code:
import scipy as sp

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

tree = sp.array([], dtype = "int")
for i in range(N):
    tree = sp.append(tree, int(input()))

tree.sort()

print(int(min(tree[K-1:]-tree[:N-K+1])))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
h=sorted(list(int(input()) for i in range(N)))
H=list()
for i in range(0,N-K+1):
    H.append(max(h[i:i+K])-min(h[i:i+K]))
print(min(H))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
def get_(h,k):
    for i in range(n-k+1):
        yield h[i:k+i]
a=list(get_(h,k))
ans=min(map(lambda x:max(x)-min(x),a))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
def get_(h,k):
    for i in range(n-k+1):
        yield h[i:k+i]
a=list(get_(h,k))
ans=10**9+1
for i in a:
    if max(i)-min(i)<ans:
        ans=max(i)-min(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def ans():
  N, K = map(int,input().split())
  H = sorted([int(input()) for _ in range(N)])
  res = 1e9+7
  for i in range(N-K+1):
    tmp = H[i:i+K]
    res = min(res, max(tmp)-min(tmp))
  print(res)
ans()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
com=list(itertools.combinations(h,k))
#a=10**9
gap=[]
for i in range(len(com)):
    b=abs(max(com[i])-min(com[i]))
    gap.append(b)

a=min(gap)    
print(a)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
com=list(itertools.combinations(h,k))
a=10**9
for i in range(len(com)):
    gap=abs(max(com[i])-min(com[i]))
    if gap<a:
        a=gap
print(a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split(" "))
H=[int(input()) for _ in range(N)]
H.sort()
tmax=10**9
for a in range(N-K+1):
    h=H[a:K+a]
    tmax=min(tmax,abs(h[-1]-h[0]))
print(tmax)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8

import copy
import numpy as np
import random

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

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

h.sort()
# print(h)
max_tree = []
min_tree = []
ans = 10**9
for i in range(n-k+1):
    ans = min(max(h[i:i+k])-min(h[i:i+k]),ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()

ans = 10 ** 9
for i in range(N-K+1):
    ans = min(ans, max(h[i:i+K])-min(h[i:i+K]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int, input().split())
h = []
sum = []
for i in range(N):
    h.append(int(input()))
h = np.array(h)
h = np.sort(h) # sorted; ascending
for i in range(N-K+1):
    sum = np.append(sum,h[i+K-1]-h[i])
print(int(min(sum)))

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
h = [int(input()) for _ in range(N)]

h_ = sorted(h)
minn = 999999999
for i in range(len(h) - K + 1):
    min_temp = max(h_[i:i+K]) - min(h_[i:i+K])
    if min_temp <= minn:
        minn = min_temp

print(minn)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
H = []
for i in range(N):
        h = int(input())
        H.append(h)

H.sort()
ans = []

for i in range(N-K+1):
        dif = max(H[i:i+K]) - min(H[i:i+K])
        ans.append(dif)
        
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
hlist = []
for i in range(n):
    hlist.append(int(input()))
hlist.sort()
h = []
for j in range(n-k+1):
    h.append(max(hlist[j:j+k])-min(hlist[j:j+k]))
print(min(h))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
h = [int(input()) for i in range(n)]

h.sort()
ans = max(h)
for i in range(n-k+1):
  hi = h[i:i+k]
  ans = min(ans, max(hi) - min(hi))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = input().split(" ")
N = int(N)
K = int(K)

hList = []
for i in range(0,N):
    hList.append(int(input()))

hList.sort()
tousa = []

for i in range(0,N-1):
    tousa.append(abs(hList[i] - hList[i+1]))

sumList = []

for i in range(0,N-K+1):
    sm = 0
    for j in range(0,K-1):
        sm = tousa[i+j] + sm
    sumList.append(sm)

sumList.sort()
print(sumList[0])

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
H=[]
for i in range(N):
  H.append(int(input()))

H.sort()

ans=10**9
for i in range(N-K+1):
  ans = min(ans, max(H[i:i+K]) - min(H[i:i+K]))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# C
N, K = map(int, input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())
h.sort()
result = 1e10
for i in range(N-K+1):
    h_list = h[i:i+K]
    result = min(result, max(h_list) - min(h_list))
print(result)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
h = []
for i in range(n):
  h.append(int(input()))
h.sort()
g = float('inf')
for i in range(n-k+1):
  g = min(g, h[i:i+k][-1] - h[i:i+k][0])
print(g)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
h = []
for i in range(n):
  h.append(int(input()))
h.sort()
g = float('inf')
for i in range(n-k+1):
  g = min(g, max(h[i:i+k]) - min(h[i:i+k]))
print(g)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
h = []
for i in range(n):
  h.append(int(input()))
h.sort()
g = float('inf')
for i in range(n-k+1):
  if g > max(h[i:i+k]) - min(h[i:i+k]):
    g = max(h[i:i+k]) - min(h[i:i+k])
print(g)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
h = []
for i in range(n):
  h.append(int(input()))
h.sort()
g = []
for i in range(n-k+1):
  g.append(max(h[i:i+k]) - min(h[i:i+k]))
print(min(g))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
h = []
ans = 1<<50
for i in range(n):
    h.append(int(input()))
h = sorted(h)
for i in range(n-k+1):
    temp = h[i:i+k]
    # print(temp)
    ans = min(ans,temp[-1]-temp[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=input().split()
c,d=int(a),int(b)
l=[int(input()) for i in range(c)]
L=sorted(l)
x=max(L[:d])-min(L[:d])
for i in range(c-d+1):
    if max(L[i:i+d])-min(L[i:i+d])<x:
        x=max(L[i:i+d])-min(L[i:i+d])
print(x)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
h=[]
for i in range(0,N):
    h.append(int(input()))
h_New=[]
for i in range(0,N):
    a=min(h)
    h_New.append(a)
    h.remove(a)
h_k=[]
for i in range(0,N-K+1):
    h_k.append(h_New[i+K-1]-h_New[i])
print(min(h_k))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
hn = sorted([int(input())for i in range(N)],reverse = True)
ans = 10**10
for i in range(len(hn)-K+1):
    ans = min(ans,max(hn[i:i+K])-min(hn[i:i+K]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]

h_arr = []
for i in range(n):
    h_arr.append(int(input()))

h_sort = sorted(h_arr, reverse=True)

tmp = 0
for i in range(n-k+1):
    if i == 0:
        tmp = max(h_sort[i:i+k]) - min(h_sort[i:i+k])
    else:
        sub = max(h_sort[i:i+k]) - min(h_sort[i:i+k])
        tmp = min(sub, tmp)

print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
hmin = 10**9
for selected in itertools.combinations(h, K):
    delta = max(selected) - min(selected)
    hmin = min(hmin, delta)
    
print(hmin)

Submission status: Time Limit Exceeded

Solution code:
N, K = (int(i) for i in input().split(" "))
h = []

for i in range(N):
    h.append(int(input()))

M = N - K

h = sorted(h, reverse=True)

result = h[0] - h[K-1]

for i in range(M+1):
    tmp = h[i:]

    if (tmp[0] - tmp[K-1]) < result:
        result = tmp[0] - tmp[K-1]

print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,k = map(int, input().split(' '))
prices = []
for i in range(n):
    prices.append(int(input()))

sortedPrices = sorted(prices)


trees = []
for i in range(k):
    trees.append(sortedPrices.pop(0))

hdiff = 1000000000

while(True):
    hdiff = min( (trees[-1] - trees[0]), hdiff )
    trees.pop(0)
    if len(sortedPrices) == 0:
        break
    trees.append(sortedPrices.pop(0))

print(hdiff)

Submission status: Time Limit Exceeded

Solution code:
def func(L):
    return sum([L[i+1] - L[i] for i in range(len(L)-1)])


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

H = []

for n in range(N):
    H.append(int(input()))

H.sort()

R = [func(H[i:i+K]) for i in range(N+1-K)]

print(min(R))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())

H = []

def func(L):
    result = 0
    for i in range(len(L)-1):
        result += L[i+1] - L[i]
    return result


for n in range(N):
    H.append(int(input()))

H.sort()

R = [func(H[i:i+K]) for i in range(N+1-K)]

print(min(R))

Submission status: Time Limit Exceeded

Solution code:
def insertionSort(A,n,g):
    for i in range(g,n):
        v = A[i]
        j = i-g
        while j>= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j-g
        A[j+g] = v

def shellSort(A,n):
    G=[]
    h = 1
    while h<=n:
        G.append(h)
        h += h*3
    m = len(G)
    G.reverse()
    for i in range(m):
        insertionSort(A,n,G[i])


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

R = []

for i in range(n):
    R.append(int(input()))

shellSort(R,n)

minv = 2000000000

for j in range(n-k+1):
    minv = min(minv,R[j+k-1]-R[j])

print(minv)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = (int(i) for i in input().split())  
heights = [int(input()) for i in range(N)] 
heights_lists = list(itertools.combinations(heights, K))

min_diff = max(heights) - min(heights) 
for heights_one in heights_lists:
    if min_diff > (max(heights_one) - min(heights_one) ):
        min_diff = (max(heights_one) - min(heights_one) )

print(min_diff)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
h = sorted(list(map(int, [input() for i in range(n)])))
ans = int(max(h))

for j in range(n-k+1):
    ans = min(ans, (max(h[j:j+k])-min(h[j:j+k])))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = sorted([int(input()) for i in range(N)])
res = []
for i in range(N-K+1):
    tmp = h[i:i+K]
    res.append(tmp[-1] - tmp[0])
print(min(res))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = sorted([int(input()) for i in range(N)])
res = []
for i in range(N-K+1):
    tmp = h[i:i+K]
    res.append(max(tmp) - min(tmp))
print(min(res))

Submission status: Time Limit Exceeded

Solution code:
N,K=(int(i) for i in input().split())
h=[int(input()) for i in range(N)]
h.sort()
m = max(h[0:K]) - min(h[0:K])
for i in range(N-K+1):
    d = max(h[i:i+K]) - min(h[i:i+K])
    if m>d:
        m = d
print(m)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        th = hs[i:i + K]
        r = min(r, th[-1] - th[0])
        i += 1
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = list(map(int, input().split()))
    hs = [int(input()) for i in range(N)]
    hs.sort()
    i = 0
    r = 10 ** 9
    while True:
        if i + K > N:
            break
        r = min(r, max(hs[i:i + K]) - min(hs[i:i + K]))
        i += 1
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))


def check(k, hs, mx, mn, r, memo):
    if (k, mx, mn) in memo:
        return memo[(k, mx, mn)]
    if mx - mn > r:
        return r
    if k == 0:
        return min(r, mx - mn)
    for i, h in enumerate(hs):
        hs.remove(h)
        r = min(r, check(k - 1, hs[::], max(mx, h), min(mn, h), r, memo))
        hs.insert(i, h)
    memo[(k, mx, mn)] = r
    return r


def main():
    hs = [int(input()) for i in range(N)]
    print(check(K, hs, 0, 10 ** 9, 10 ** 9, {}))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))


def check(k, hs, mx, mn, r):
    if mx - mn > r:
        return r
    if k == 0:
        return min(r, mx - mn)
    for i, h in enumerate(hs):
        hs.remove(h)
        r = min(r, check(k - 1, hs[::], max(mx, h), min(mn, h), r))
        hs.insert(i, h)
    return r


def main():
    hs = [int(input()) for i in range(N)]
    print(check(K, hs, 0, 10 ** 9, 10 ** 9))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- cording: utf-8 -*-
import statistics
n, k = map(int, input().split())
a = list(map(int, [input() for i in range(n)]))

while not len(a) == k:
    med = statistics.median(a)
    if a[a.index(max(a))] - med > med - a[a.index(min(a))]:
        del a[a.index(max(a))]
    else:
        del a[a.index(min(a))]

print(max(a)-min(a))

Submission status: Time Limit Exceeded

Solution code:
n,k  = map(int,input().split())
l = sorted([int(input()) for i in range(n)])
#print(l)
ansl = []
for m in range(n-k+1):
  ansl.append(max(l[m:m+k])-min(l[m:m+k]))
print(min(ansl))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
hlist = []
for i in range(N):
    hlist.append(int(input()))

import numpy as np
dlist = np.diff(np.sort(hlist))

ans = []
for i in range(len(dlist)-1):
    ans.append(sum(dlist[i:i+K-1]))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

H.sort()
res = 10000000000
for i in range(N-K+1):
    res = min(res, max(H[i:i+K]) - min(H[i:i+K]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = sorted([int(input()) for i in range(N)])
min_max = lambda x: max(x) - min(x)
print(min([min_max(h[i:i+K]) for i in range(N-K+1)]))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)
dh = []
for i in range(N - K + 1):
    dh = dh + [h[i + K - 1]-h[i]]

print(min(dh))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = [int(input()) for i in range(N)]


def quick(a):
    if len(a) < 2:
        return a
    p = a[0]
    x, y = quick_div(p, a[1:])
    return quick(x) + [p] + quick(y)


def quick_div(p, a):
    if len(a) < 1:
        return ([], [])
    x, y = quick_div(p, a[1:])
    if a[0] < p:
        return ([a[0]] + x, y)
    else:
        return (x, [a[0]] + y)


h = quick(h)
dh = []
for i in range(len(h) - K + 1):
    dh = dh + [h[i + K - 1]-h[i]]

print(min(dh))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = [int(input()) for i in range(N)]


def quick(a):
    if len(a) < 2:
        return a
    p = a[0]
    x, y = quick_div(p, a[1:])
    return quick(x) + [p] + quick(y)


def quick_div(p, a):
    if len(a) < 1:
        return ([], [])
    x, y = quick_div(p, a[1:])
    if a[0] < p:
        return ([a[0]] + x, y)
    else:
        return (x, [a[0]] + y)


h = quick(h)
# print(h)
dh = []
for i in range(len(h) - K + 1):
    dh = dh + [h[i + K - 1]-h[i]]

print(min(dh))

# 入力例1
# 5 3
# 5
# 7
# 5
# 7
# 7

# 出力
# 2

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
sh = sorted(h)
u = []
for i in range(len(sh)-k+1):
    a = sh[i:i+k]
    u.append(max(a) - min(a))
print(min(u))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
h = sorted([int(input()) for _ in range(n)], reverse=True)
u = []
for i, v in enumerate(h[:-k+1]):
    a = h[i:i+k]
    u.append(max(a) - min(a))
print(min(u))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=input().split()
N = int(N)
K = int(K)
e = [0]*N

for i in range(N):
    e[i] = int(input())

for i in range(N):
    for j in range(N):      
        if e[i] < e[j]:
            tmp = e[i]
            e[i] = e[j]
            e[j] = tmp

f = [0]*(N - K + 1)
for i in range(N-K+1):
    f[i] = e[K + i - 1] - e[i]

print(np.min(np.array(f)))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = []
[h.append(int(input())) for i in range(N)]

l = []
for i in range(N):
    a = []
    for j in range(N):
        if i != j and h[i]-h[j]>=0:
            a.append(h[i]-h[j])
    if len(a) >= K-1:
        l.append(a)

l2 = []
for i in range(len(l)):
    a = min(l[i])
    if len(l[i]) > 1:
        l[i].remove(a)
    l2.append(min(l[i]))
print(min(l2))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h_in = []
[h_in.append(int(input())) for i in range(N)]
import itertools

h = []
for l in itertools.combinations(h_in,K):
    h.append(max(l) - min(l))
print(min(h))

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
heights = [int(input()) for i in range(n)]

heights.sort()

# あり得る最大のサイズ差
answer = max(heights) - min(heights)

for i in range(0, n-k+1):
    x = heights[i:i + k]
    candidate = max(x) - min(x)
    if candidate < answer:
        answer = candidate

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
heights = []
for i in range(0,n):
    heights.append(int(input()))

heights.sort()

answer = -1
for i in range(0, n-k+1):
    xlist = heights[i:i + k]
    item = max(xlist) - min(xlist)
    if answer == -1 or item < answer:
        answer = item

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]

h.sort()

DEF_MIN = max(h)-min(h)

for i in range(n-k+1):
    tmp = max(h[i:i+k])-min(h[i:i+k])
    DEF_MIN = min(DEF_MIN, tmp)

print(DEF_MIN)

Submission status: Time Limit Exceeded

Solution code:
N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

mindiff = 1000000000

for i in range(int(N)-(S - 1)):
    v = 0
    for j in range(int(S)-1):
        v += a[i+j+1]-a[i+j]
        if i%3 == 0 and mindiff < v:break

    if mindiff > v: mindiff = v

print(mindiff)

Submission status: Time Limit Exceeded

Solution code:
N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

mindiff = 10000000000

for i in range(int(N)-(S - 1)):
    v = 0
    for j in range(int(S)-1):
        v += a[i+j+1]-a[i+j]
        if mindiff < v:break

    if mindiff > v: mindiff = v

print(mindiff)

Submission status: Time Limit Exceeded

Solution code:
N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

diff = []

for i in range(int(N)-(S - 1)):
    v = 0
    for j in range(int(S)-1):
        v += a[i+j+1]-a[i+j]

    diff.append(v)

print(min(diff))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import itertools
n,k = map(int, input().split())

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

groups = list(itertools.combinations(h, k))
dif = []
for group in groups:
    dif.append(max(group) - min(group))
print(min(dif))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,raw_input().split())
arr = [input() for ii in range(n)]
arr.sort(reverse = True)
ans = 10**20
for i in xrange(0,n-k+1):
	ans = min(ans,arr[i]-arr[i+k-1])
print ans