| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 135 | 79 | 69 | 62.162% |
Let us define the value of a multiset of integers is the minimum difference between any two distinct elements. If a multiset contains two elements with the same value, then the two elements are considered different elements thus the value of the multiset is 0.
Given a multiset of integers A consisting of N elements, we want to find the value of the subset of A consisting of K elements which has the maximum value.
The first line contains two integers: N K (2 ≤ K ≤ N ≤ 100,000) in a line denoting the number of elements of A and the number of elements of the subset of A we are looking for. The second line contains N integers: A1, A2, ..., AN (0 ≤ Ai ≤ 1,000,000,000) representing the elements of set A.
The output contains the value of the subset of A consisting of K elements which has the maximum value, in a line.
4 2 1 2 4 10
9
On the first sample, the optimal subset is {1, 10}. The value is 10 - 1 = 9.
4 3 1 2 4 10
3
On the second sample, the optimal subset is {1, 4, 10}. The value is 4 - 1 = 3.
4 4 1 2 4 10
1
On the third sample, the optimal subset is {1, 2, 4, 10}. The value is 2 - 1 = 1.
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2017 F번