Informatica Online Judge

  난로 #1 [2194 / 0892]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 30   Total Tried : 30


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 218byte
My Best Submission (C++) : N/A

[JOI 2018 honsen]

Background

경곽이 방에는 난로가 있다.

경곽이는 추위에 강하기 때문에 혼자서 방에 있을 때에는 난로를 켤 필요가 없다.

이 날, 경곽이 집에 N명의 친구들이 놀러오기로 했다.

$i$번째 천구는 시각 $T_i$ 에 도착하고 시각 $T_{i}+1$ 에 떠난다.

동시에 여러 명의 친구들이 오는 경우는 없다.

경곽이는 임의의 시각에 난로를 켜거나 끌 수 있다. 단, 난로를 켤 때마다 성냥을 하나씩 써야 한다.

경곽이는 성냥을 K개만 가지고 있으므로 최대 K번까지 난로를 켤 수 있다.

처음에는 난로가 꺼져있는 상태이다.

난로를 켜져있을 때에는 연료를 소비하므로 연료의 낭비를 최소화하고자 한다.

경곽이가 각 친구들이 도착하는 시간을 이용하여 난로를 켜져 있는 시간의 최솟값을 구하시오.

단, 모든 친구들은 추위에 약하기 때문에 반드시 친구들이 있을 때에는 난로가 켜져 있어야 한다.

Input

첫 번째 줄에는 N, K가 공백으로 구분되어 입력된다.

다음 줄부터 N줄에 걸쳐서 친구들이 도착하는 시각 $T_i$들이 주어진다.

[입력값의 정의역]
#1 : $1 <= K <= N <= 5,000$ ; $1 <= T_i <= 1,000,000,000$

Output

경곽이가 난로를 사용하는 최소 시간을 출력한다.

IO Example

입력
3 2
1
3
6

출력
4

* 시각 1에서 난로를 켜고, 4에 끈다. (4-1 = 3만큼 켜져 있음)
다음으로 6에 켜고 7에 끈다. 따라서 모두 4만큼 난로를 사용한다. 이 보다 더 적게 사용하는 경우는 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]