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:
import sys
from collections import deque
input = sys.stdin.readline
N, K = [int(x) for x in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
h.sort()
i = 0
ans = 10 ** 9
while N - i >= K:
    temp = h[i:i+K]
    ans = min(ans,temp[-1] - temp[0])
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
import numpy as np
N, K = [int(x) for x in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
h.sort()
i = 0
ans = 10 ** 9
while N - i >= K:
    temp = h[i:i+K]
    ans = min(ans,temp[-1] - temp[0])
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline().rstrip()
n, k = [int(i) for i in input().split()]
h = sorted(int(input()) for _ in range(n))
a = float("inf")
for i in range(n - k + 1):
  hik = h[i:i + k]
  a = min(a, hik[-1] - hik[0])
print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline().rstrip()
n, k = [int(i) for i in input().split()]
h = sorted(int(input()) for _ in range(n))
a = float("inf")
for i in range(n - k + 1):
  hik = h[i:i + k]
  a = min(a, max(hik) - min(hik))
print(a)

Submission status: Time Limit Exceeded

Solution code:
A,B = map(int,input().split())
C = [int(input()) for _ in range(A)]
c = []
p = 0
C = sorted(C)
for i in range(B,A+1):
  c.append(max(C[i-(B):i]) - min(C[i-(B):i]))
  if min(c) == 0:
    break;
print(min(c))

Submission status: Time Limit Exceeded

Solution code:
A,B = map(int,input().split())
C = [int(input()) for _ in range(A)]
c = []
p = 0
C = sorted(C)
for i in range(B,A+1):
  c.append(max(C[i-(B):i]) - min(C[i-(B):i]))
print(min(c))

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()
h_max = 0
h_min = 0
r = 0
ans = []
#print(h)
for i in range(r,n-k+1):
    if n - r < k: 
        break
    h_max = max(h[r:k+r])
    #print(h[r:k])
    h_min = min(h[r:k+r])
    ans.append(h_max - h_min)
    r += 1
print(min(ans))

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()
h_max = 0
h_min = 0
r = 0
ans = []
#print(h)
for i in range(r,n):
    if n - r < k: 
        break
    h_max = max(h[r:k+r])
    #print(h[r:k])
    h_min = min(h[r:k+r])
    ans.append(h_max - h_min)
    r += 1
print(min(ans))

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()
h_max = 0
h_min = 0
r = 0
ans = []
#print(h)
for i in range(r,n):
    h_max = max(h[r:k+r])
    #print(h[r:k])
    h_min = min(h[r:k+r])
    if n - r < k: 
        break
    ans.append(h_max - h_min)
    r += 1
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans = h[-1]
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 sys
from collections import deque
input = sys.stdin.readline

N, K = [int(x) for x in input().strip().split()]
highest = 0
lowest = 10 ** 9
q = deque([])
ans = 10 ** 9
pre = -1
H = sorted([int(input()) for _ in range(N)])
for n, ne in enumerate(H):
    q.append(ne)
    if len(q) > K:
        pre = q.popleft()
    if ne > highest:
        highest = ne
    if ne < lowest:
        lowest = ne
    if pre == highest:
        highest = max(q)
    if pre == lowest:
        lowest = min(q)
    if n >= K - 1:
        ans = min(ans, highest - lowest)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N, K = [int(x) for x in input().strip().split()]
highest = 0
lowest = 10 ** 9
high = [0] * N
low = [0] * N
q = deque([])
ans = 10 ** 9
pre = -1
H = sorted([int(input()) for _ in range(N)])
for n, ne in enumerate(H):
    q.append(ne)
    if len(q) > K:
        pre = q.popleft()
    if ne > highest:
        highest = ne
    if ne < lowest:
        lowest = ne
    if pre == highest:
        highest = max(q)
    if pre == lowest:
        lowest = min(q)
    if n >= K - 1:
        ans = min(ans, highest - lowest)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N, K = [int(x) for x in input().strip().split()]
highest = 0
lowest = 10 ** 9
high = [0] * N
low = [0] * N
q = deque([])
ans = 10 ** 9
pre = -1
H = sorted([int(input()) for _ in range(N)])
for n, ne in enumerate(H):
    q.append(ne)
    if len(q) > K:
        pre = q.popleft()
    if ne > highest:
        highest = ne
    if ne < lowest:
        lowest = ne
    if pre == highest:
        highest = max(q)
    if pre == lowest:
        lowest = min(q)
    high[n] = highest
    low[n] = lowest
    if n >= K - 1:
        ans = min(ans, highest - lowest)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
li = list(int(input()) for i in range(n))

li.sort()
num = 0
li2,li3 = [],[]
for i in range(len(li)-k+1):
    li2.append(li[i:i+k])

for i in range(len(li2)):
    li3.append(max(li2[i]) - min(li2[i]))
print(min(li3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
l=[0]*n
c=0
for i in range(n):
    l[i]=int(input())
    if l.count(l[i])>=k:
        print(0)
        c=1
if c==0:
    l.sort()
    print(l[k-1]-l[0])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[0]*n
c=0
for i in range(n):
    l[i]=int(input())
    if l.count(l[i])>=k:
        print(0)
        c=1
if c==0:
    l.sort()
    print(l[k-1]-l[0])

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-11 18:30:26(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, k, *h = (int(x) for x in sys.stdin.read().split())
    h.sort()
    min_diff = h[-1] - h[0] # default value
    for i in range(n - k + 1):
        heights = h[i:i+k]
        diff = heights[-1] - heights[0]
        min_diff = min(min_diff, diff)
    print(min_diff)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().strip().split())
#print(N, K)
H = []
for i in range(N):
    h = int(input().strip())
    H.append(h)
#print(H)
H.sort()
#print(H)
smallest = 10 ** 10
#least = []
for i in range(len(H) - K + 1):
    test = H[i:i + K]
    difference = test[K - 1] - test[0]
    if difference < smallest:
        smallest = difference
        #least = test
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().strip().split())
#print(N, K)
H = []
for i in range(N):
    h = int(input().strip())
    H.append(h)
#print(H)
H.sort()
#print(H)
smallest = 10 ** 10
least = []
for i in range(len(H) - K + 1):
    test = H[i:i + K]
    difference = test[K - 1] - test[0]
    if difference < smallest:
        smallest = difference
        least = test
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
ans=1000000000
for j in range(len(h)-2):
    c=h[j:j+k]
    ans=min(ans,c[-1]-c[0])
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()
ans=1000000000
for j in range(len(h)-2):
    c=h[j:j+k]
    ans=min(ans,max(c)-min(c))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
h = [int(input()) for _ in range(n)]
h.sort()
between = [h[i+1]-h[i] for i in range(n-1)]
answer = 10**9
for i in range(n-k+1):
  answer = min(answer, sum(between[i: i+k-1]))
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
l=[]
ans=10**9

for _ in range(N):
    l.append(int(input()))
    
l.sort()

for i in range(N-K+1):
    temp=max(l[i:i+K])-min(l[i:i+K])
    ans=min(ans,temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list()
    for i in range(N):
        h.append(int(input()))

    h = sorted(h)

    res = 10 ** 9 + 1
    for i in range(N-K + 1):
        if res > max(h[i:i+K]) - min(h[i:i+K]):
            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 = [0] * n
ans = 0
for i in range(n):
  h[i] = int(input())
h.sort()
for i in range(n-k+1):
  temp = max(h[i:i+k]) - min(h[i:i+k])
  if temp == 0:
    ans = temp
    break
  elif i == 0:
    ans = temp
  elif ans > temp:
    ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
h = sorted([int(input()) for i in range(n)])
diff = [h[i+1] - h[i] for i in range(n-1)]
ans = float("inf")

for i in range(n-k+1):
    ans = min(ans, sum(diff[i:i+k-1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# print('input >>')
N, K = map(int, (input().split()))
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()
hdiff = [h[i + 1] - h[i] for i in range(len(h) - 1)]
hdiff = np.array(hdiff)
ans = 10 ** 10
# print('hdiff: %s' % hdiff)
for i in range(N - K+1):
    # print('i %s' % i)
    # print('hdiff[i:i+K-1]: %s' % hdiff[i:i+K-1])
    ans = min(ans,np.sum(hdiff[i:i+K-1]))

# print('----------output----------')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# print('input >>')

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

h.sort()
hdiff = [h[i + 1] - h[i] for i in range(len(h) - 1)]
ans = 10 ** 10
# print('hdiff: %s' % hdiff)
for i in range(N - K+1):
    # print('i %s' % i)
    # print('hdiff[i:i+K-1]: %s' % hdiff[i:i+K-1])
    ans = min(ans,sum(hdiff[i:i+K-1]))

# print('----------output----------')
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    b=int(input())
    a.append(b)

a=sorted(a)


min=a[K-1]-a[0]
for j in range(N-K+1):
    s=a[j:j+K]
    
    if min >= s[K-1]-s[0]:
        min=s[K-1]-s[0]
        
print(min)

Submission status: Time Limit Exceeded

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

height.sort()

ans = 10**10
for i in range(n-k+1):
    temp = height[i:i+k]
    if temp[-1] - temp[0] < ans:
        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, reverse=True)
ans = 1e9
for i in range(N-K+1):
    h = H[i:i+K]
    dh = h[0]-h[-1]
    if dh < ans:
        ans = dh
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, reverse=True)
ans = 1e9
for i in range(N-K+1):
    h = H[i:i+K]
    dh = max(h)-min(h)
    if dh < ans:
        ans = dh
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

ans = []

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

Submission status: Time Limit Exceeded

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

ans = float("inf")

for i in range(N-K+1):
    tree = H[i:i+K]
    ans =min(ans, tree[-1]-tree[0])
print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

Ha = np.sort(H)
Hd = Ha[1:] - Ha[:-1]

ans = 10**9
for i in range(N-K+1):
    if sum(Hd[i:i+K-1]) < ans:
        ans = sum(Hd[i:i+K-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
h = sorted([int(input()) for _ in range(n)])
ans = 10**9
for i in range(n-k+1):
  tmp = max(h[i:i+k])-min(h[i:i+k])
  if ans > tmp:
    ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def christmas_eve(n,k,h):
    _h = sorted(h)
    opt = 0
    ans = 10**9 + 1

    for i in range(n-(k-1)):
        l = _h[i:i+k]
        opt = max(l) - min(l)
        if ans > opt:
            ans = opt

    return ans
if __name__ == '__main__':
    n,k = map(int,raw_input().split())
    h = [int(raw_input()) for _ in range(n)]


    print christmas_eve(n,k,h)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

#sys.setrecursionlimit(10000)

n,k = map(int, input().split())
h = sorted(list(map(int, (input() for i in range(n)))))

l = [0] * (n-1)
for i in range(n - 1):
    l[i] = h[i + 1] - h[i]

ans = max(l)
for j in range(len(l) - (k - 2)):
    ans = min(ans,sum(l[j:j + k - 1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

#sys.setrecursionlimit(10000)

n,k = map(int, input().split())
h = sorted(list(map(int, (input() for i in range(n)))))

l = []
for i in range(n - 1):
    l.append(h[i + 1] - h[i])

ans = max(l)
for j in range(len(l) - (k - 2)):
    ans = min(ans,sum(l[j:j + k - 1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc115/tasks/abc115_c
# C - Christmas Eve
import itertools

n, k = list(map(int, input().split()))
h_list = []

for _ in range(n):
    h_list.append(int(input().split()[0]))

# 全探索で頑張る方法
# 多分時間が足りない
p_list = itertools.combinations(h_list, k)
min_value = float('inf')

for p in p_list:
    p = list(p)
    v = max(p) - min(p)
    if v < min_value:
        min_value = v

print(min_value)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, k = map(int, input().split())
    h = sorted(list(int(input()) for _ in range(n)))
    min_diff = 10 ** 9
    for i in range(n - k + 1):
        part = h[i:i + k]
        diff = part[-1] - part[0]
        if diff < min_diff:
            min_diff = diff
    return min_diff


if __name__ == "__main__":
    print(solve())

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()

ans=[]

for i in range(N):
	if i+K==N+1:
		break
	else:
		ans.append(max(h[i:i+K]) - min(h[i:i+K]))
print(min(ans))

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()
ans=10**9
a=[]
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 sys
input = sys.stdin.readline

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

hh = [h[i+1] - h[i] for i in range(n-1)]

ans = float("inf")
for i in range(n-k+1):
    ans = min([ans, sum(hh[i:i+k-1])])

print(ans)

Submission status: Time Limit Exceeded

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

hh = [h[i+1] - h[i] for i in range(n-1)]

ans = float("inf")
for i in range(n-k+1):
    ans = min([ans, sum(hh[i:i+k-1])])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
hhh = [int(input()) for _ in range(n)]
hhh.sort()
ans = float("inf")
for i in range(n-k+1):
  ans = min(ans, max(hhh[i:i+k]) - min(hhh[i:i+k]))
print(ans)

Submission status: Time Limit Exceeded

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

h_dif = []
ans = 10 ** 9 + 1

for i in range(1, n):
    h_dif.append(h[i]-h[i-1])
    if i >= k-1:
        ans = min(ans, sum(h_dif[i-k+1:i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC 115 C

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

h = [int(input()) for _ in range(N)]

h.sort()

ans = 1.0e+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:
N, K = map(int, input().split())
trees = []
for _ in range(N):
    tree = int(input())
    trees.append(tree)

trees.sort()

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

print(m)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def q49(n, k, h):
    a = []
    for i in itertools.combinations(h, k):
        mi = min(i)
        ma = max(i)
        a.append(ma - mi)
    return min(a)
            
N, K = [int(i) for i in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
print(q49(N, K, h))

Submission status: Time Limit Exceeded

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

h.sort()
# print(h)
tmp = 10 ** 10

for i in range(n - 1):
    d.append(h[i + 1] - h[i])
# print(d)
for i in range(n):
    if i + k - 1 >= len(h):
        break
    sub = sum(d[i:i + k - 1])
    # print(sub)
    tmp = min(tmp, sub)

print(tmp)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

H = sorted(H)
min_diff = float('inf')
for i in range(N-K+1):
    trees = H[i:i+K]
    diff = trees[-1] - trees[0]
    if diff < min_diff:
        min_diff = diff
print(min_diff)

Submission status: Time Limit Exceeded

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

h.sort()

ans = float('inf')
for i in range(N - K + 1):
    s = h[i: i + K]
    ans = min(ans, max(s) - min(s))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
li = list(int(input()) for i in range(n))

li.sort()
num = 0
li2 = []
for i in range(len(li)-k+1):
    li2.append( max(li[i:i+k]) - min(li[i:i+k]))

print(min(li2))

Submission status: Time Limit Exceeded

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

# 小さい順にソートする
#def sort(h):
#    if len(h) <= 1:
#        return h
#    base = h[-1]
#    low_temp = [];
#    high_temp = [];
#    base_count = 1
#    for i in range(len(h)-1):
#        if h[i] < base:
#            low_temp.append(h[i])
#        elif h[i] > base:
#            high_temp.append(h[i])
#        else:
#            base_count += 1
#    low = sort(low_temp)
#    high = sort(high_temp)
#    return low + [base]*base_count + high

h.sort()
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    if (temp[-1] - temp[0]) < hantei:
        hantei = temp[-1] - temp[0]

print(hantei)

Submission status: Time Limit Exceeded

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

# 小さい順にソートする
#def sort(h):
#    if len(h) <= 1:
#        return h
#    base = h[-1]
#    low_temp = [];
#    high_temp = [];
#    base_count = 1
#    for i in range(len(h)-1):
#        if h[i] < base:
#            low_temp.append(h[i])
#        elif h[i] > base:
#            high_temp.append(h[i])
#        else:
#            base_count += 1
#    low = sort(low_temp)
#    high = sort(high_temp)
#    return low + [base]*base_count + high

h.sort()
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    temp_dif = max(temp) - min(temp)
    if temp_dif < hantei:
        hantei = temp_dif

print(hantei)

Submission status: Time Limit Exceeded

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

# 小さい順にソートする
def sort(h):
    if len(h) <= 1:
        return h
    base = h[-1]
    low_temp = [];
    high_temp = [];
    base_count = 1
    for i in range(len(h)-1):
        if h[i] < base:
            low_temp.append(h[i])
        elif h[i] > base:
            high_temp.append(h[i])
        else:
            base_count += 1
    low = sort(low_temp)
    high = sort(high_temp)
    return low + [base]*base_count + high

h = sort(h)
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    temp_dif = max(temp) - min(temp)
    if temp_dif < hantei:
        hantei = temp_dif

print(hantei)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as comb

n, k = map(int, input().split())
p_list = []
for i in range(n):
    p = int(input())
    p_list.append(p)

comb_list = list(comb(p_list, k))
min = 10000000000000000
for c in comb_list:
    c = sorted(list(c))
    if min > c[-1]-c[0]:
        min = c[-1]-c[0]

print(min)

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()

mindiff=max(h)-min(h)
for i in range(N-K+1):
    maxmin=max(h[i:i+K])-min(h[i:i+K])
    mindiff=min(mindiff,maxmin)
print(mindiff)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h.sort()
H = []
for i in range(1, N):
    H.append(h[i] - h[i - 1])
ans = 10 ** 9
for i in range(N - 1):
    if i + K <= N:
        ans = min(ans, sum(H[i:i + K - 1]))
print(ans)

Submission status: Time Limit Exceeded

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

List = sorted(List)

tmp = 10**9
for i in range(N-K+1):
    lst = List[i:i+K]
    diff = max(lst)-min(lst)
    if diff<tmp:
        tmp = diff
print(tmp)

Submission status: Time Limit Exceeded

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

c.sort()

ans = []
for i in range(n-k+1):
    ans.append(max(c[i:k+i])-min(c[i:k+i]))

print(min(ans))

Submission status: Time Limit Exceeded

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

c.sort()

ans = 10**9
for i in range(n-k+1):
    ans = min(ans,max(c[i:k+i])-min(c[i:k+i]))

print(ans)

Submission status: Time Limit Exceeded

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

c.sort()

ans = 10**9
for i in range(n-k+1):
    ls = c[i:k+i]
    ans = min(ans,max(ls)-min(ls))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

    arr = list(itertools.permutations(h, K))
    res1 = []
    res2 = []
    ans = []
    for j in range(len(arr)):
        res1.append(sorted(arr[j]))

    for k in range(len(res1)):
        res2.append(sorted(res1[k]))

    for l in range(len(res2)):
        ans.append(res2[l][K-1] - res2[l][0])
    print(min(ans))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, K = map(int, input().split())
    h = []
    for i in range(N):
        h.append(int(input()))
    arr = list(itertools.permutations(h, K))
    res1 = []
    res2 = []
    ans = []
    for j in range(len(arr)):
        res1.append(sorted(arr[j]))

    for k in range(len(res1)):
        res2.append(sorted(res1[k]))

    for l in range(len(res2)):
        ans.append(res2[l][K-1] - res2[l][0])
    print(min(ans))
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m


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

H = []

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

    H.append(h)
    
def Merge(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    B = A[p : q + 1]
    B = np.append(B, 10e11)
    C = A[q + 1 : r + 1]
    C = np.append(C, 10e11)
    i = 0
    j = 0
    k = p

    while i <= n_1 - 1 or j <= n_2 - 1:
        if B[i] <= C[j]:
            A[k] = B[i]
            i += 1
            k += 1
        else:
            A[k] = C[j]
            j += 1
            k += 1

    return A

def Merge_Sort(A, p, r):
    if p < r:
        q = m.floor( (p + r)/2 )
        A = Merge_Sort(A, p, q)
        A = Merge_Sort(A, q + 1, r)
        A = Merge(A, p, q, r)

    return A


H = np.array(H)

p = 0
r = len(H) - 1

H = Merge_Sort(H, p, r)

Dummy = []

for i in range(N - K + 1):

    Dummy.append(H[K - 1 + i] - H[i])

print(int(min(Dummy)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

# 初期値を入力

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

H = []

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

    H.append(h)

# 関数定義

def Merge(A, p, q, r):
    # 配列Aのpからr番目の部分配列をソートすることを目的とする関数．ここで，pからqの部分配列と，q+1からrの部分配列はそれぞれソートされているものとする．
    n_1 = q - p + 1
    n_2 = r - q
    B = A[p : q + 1]
    B = np.append(B, 10e11)
    C = A[q + 1 : r + 1]
    C = np.append(C, 10e11)
    i = 0
    j = 0
    k = p

    while i <= n_1 - 1 or j <= n_2 - 1:
        if B[i] <= C[j]:
            A[k] = B[i]
            i += 1
            k += 1
        else:
            A[k] = C[j]
            j += 1
            k += 1

    return A

def Merge_Sort(A, p, r):
    if p < r:
        q = m.floor( (p + r)/2 )
        A = Merge_Sort(A, p, q)
        A = Merge_Sort(A, q + 1, r)
        A = Merge(A, p, q, r)

    return A


# メインプログラム

H = np.array(H)

p = 0
r = len(H) - 1

H = Merge_Sort(H, p, r)

Dummy = []

for i in range(N - K + 1):

    Dummy.append(H[K - 1 + i] - H[i]) 

print(int(min(Dummy)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

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

H = []

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

    H.append(h)

def Merge(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    B = A[p : q + 1]
    B = np.append(B, 10e11)
    C = A[q + 1 : r + 1]
    C = np.append(C, 10e11)
    i = 0
    j = 0
    k = p

    while i <= n_1 - 1 or j <= n_2 - 1:
        if B[i] <= C[j]:
            A[k] = B[i]
            i += 1
            k += 1
        else:
            A[k] = C[j]
            j += 1
            k += 1

    return A

def Merge_Sort(A, p, r):
    if p < r:
        q = m.floor( (p + r)/2 )
        A = Merge_Sort(A, p, q)
        A = Merge_Sort(A, q + 1, r)
        A = Merge(A, p, q, r)

    return A

H = np.array(H)

p = 0
r = len(H) - 1

H = Merge_Sort(H, p, r)

Answer = 10e10

for i in range(N - K + 1):

    Dummy = H[K - 1 + i] - H[i]
    if Answer > Dummy:
        Answer = Dummy

print(int(Answer))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

# 初期値を入力

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

H = []

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

    H.append(h)

# 関数定義

def Merge(A, p, q, r):
    # 配列Aのpからr番目の部分配列をソートすることを目的とする関数．ここで，pからqの部分配列と，q+1からrの部分配列はそれぞれソートされているものとする．
    n_1 = q - p + 1
    n_2 = r - q
    B = A[p : q + 1]
    B = np.append(B, 10e11)
    C = A[q + 1 : r + 1]
    C = np.append(C, 10e11)
    i = 0
    j = 0
    k = p

    while i <= n_1 - 1 or j <= n_2 - 1:
        if B[i] <= C[j]:
            A[k] = B[i]
            i += 1
            k += 1
        else:
            A[k] = C[j]
            j += 1
            k += 1

    return A

def Merge_Sort(A, p, r):
    if p < r:
        q = m.floor( (p + r)/2 )
        A = Merge_Sort(A, p, q)
        A = Merge_Sort(A, q + 1, r)
        A = Merge(A, p, q, r)

    return A


# メインプログラム

H = np.array(H)

p = 0
r = len(H) - 1

H = Merge_Sort(H, p, r)

Answer = 10e10

for i in range(N - K + 1):

    Dummy = H[K - 1 + i] - H[i]
    if Answer > Dummy:
        Answer = Dummy

print(int(Answer))

Submission status: Time Limit Exceeded

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

ans = 10**9
for v in combinations(H, K):
    diff = max(v) - min(v)
    if diff < ans:
        ans = diff
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K=map(int,input().split())
L=[]
n=0
while n<N:
  L.append(int(input()))
  n=n+1
ans=[]
for r in list(itertools.combinations(L,K)):
  ans.append(max(r)-min(r))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K=map(int,input().split())
L=[]
for l in range(N):
  L.append(int(input()))
ans=[]
for r in list(itertools.combinations(L,K)):
  ans.append(max(r)-min(r))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K=map(int,input().split())
L=[]
for l in range(N):
  L.append(int(input()))
R=list(itertools.combinations(L,K))
ans=[]
for r in R:
  ans.append(max(r)-min(r))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
in_1 = input().split()
n = int(in_1[0])
k = int(in_1[1])

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

trees_height.sort()


def sub_minmax(list):
    return max(list)-min(list)

subs = []

for i in range(n+1-k):
    subs.append(sub_minmax(trees_height[i:i+k]))

print(min(subs))

Submission status: Time Limit Exceeded

Solution code:

in_1 = input().split()
n = int(in_1[0])
k = int(in_1[1])

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

trees_height.sort()


def sub_minmax(list):
    return max(list)-min(list)

subs = []

for i in range(n+1-k):
    subs.append(sub_minmax(trees_height[i:i+k]))


print(min(subs))

Submission status: Time Limit Exceeded

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