시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 32 | 10 | 10 | 32.258% |
Vera has N integers a1, . . . , aN . A margin is a non-negative integer L such that it is possible to choose N integers x1, . . . , xN such that for all i, 1 ≤ i ≤ N, the interval [xi, xi + L] contains at least K of Vera’s integers and also contains ai.
Compute the minimum possible margin.
Line 1 contains integers N and K (1 ≤ K ≤ N ≤ 2 × 105).
Line 2 contains N integers, a1, . . . , aN (−109 ≤ ai ≤ 109).
Print one line with one integer, the minimum possible margin.
5 3 1 -2 10 5 4
6
For the first example, one possible solution is to choose x1 = −1, x2 = −2, x3 = 4, x4 = 0, x5 = 0, which is illustrated below.