시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB554100.000%

문제

Arash har nu kommit hem från onsite-finalen i Linköping och är tillbaka i vardagen. Nu har han precis kommit hem från ett tvättstugebesök och ska återigen matcha strumpor. När han nu sitter där med sina $N$ strumpor så känner han att han bara behöver $K$ par strumpor, resten kan få förbli osorterade. Det är alltså okej om $N-2K$ strumpor förblir omatchade, tänker Arash.

Varje strumpa en färg $F_i$. Två strumpor $i$ och $j$ kan paras ihop om skillnaden i färg strikt understiger heltalet $D$ d.v.s. $|F_{i} - F_{j}|<D$. Men istället för att hjälpa Arash matcha så många strumpor som möjligt så ska du hjälpa honom att hitta det minsta möjliga $D$ så att han kan matcha minst $K$ strumppar!

입력

Indata består av en rad med de två heltalen $N$ och $K$ ($2 \le N \le 50\,000$, $2 \le 2K \le N$).

Därefter följer en rad med $N$ heltal: $F_1, F_2, \dots, F_N$. Talen $F_i$ ligger mellan $1$ och $10^{15}$ (inklusive).

출력

Du ska skriva ut ett enda heltal: den minimala differens $D$ som gör att Arash kan matcha minst $K$ strumppar med varandra.

예제 입력 1

5 2
3 8 1 5 9

예제 출력 1

3

예제 입력 2

4 1
100 101 102 103

예제 출력 2

2

예제 입력 3

10 4
81 92 42 45 62 5 4 85 73 22

예제 출력 3

9

예제 입력 4

2 1
1000000000000 5000000000000

예제 출력 4

4000000000001

출처

Olympiad > Swedish Olympiad in Informatics > 2014 > KATT A번

  • 문제를 만든 사람: Oskar Werkelin Ahlin