Problems
조이의 집에는 난로가 하나 있다.
조이는 추위에 강하기 때문에 집에 혼자 있을 때는 난로를 켜지 않아도 되지만, 손님이 오면 난로를 켜야 한다.
오늘, 조이의 집에는 N명의 손님이 온다.
i번째 (1 ≦ i ≦ N) 손님은 시간 T_i에 와서 시간 T_i + 1에 나간다.
같은 시간에 2명 이상의 손님이 조이의 집에 있는 경우는 없다.
조이는 임의의 시간에 난로를 껐다 켰다 할 수 있다.
그러나 난로를 켤 때마다 성냥을 하나씩 써야한다.
조이는 성냥을 K개밖에 가지고 있지 않기 때문에, K번만 난로를 켤 수 있다.
하루의 시작에는 난로가 꺼져있다.
또한 난로는 켜져있는 시간만큼 연료를 소비하기 때문에, 난로를 잘 조작하여 난로가 켜져있는 시간을 최소로 하고 싶다.
조이의 방에 오는 손님의 정보와 조이가 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져있는 시간의 최솟값을 구하자.
Input
첫 번째 줄에 두 개의 자연수 N과 K가 공백을 사이에 두고 주어진다. N은 손님의 수를, K는 조이가 가지고 있는 성냥 개수를 의미한다.
두 번째 줄부터 N개의 줄에 손님의 방문 시간을 나타내는 자연수 T_i가 주어진다.
i번째 손님은 T_i시간에 들어와 T_i + 1시간에 나간다.
[제한]
1 ≦ N ≦ 100,000 1 ≦ K ≦ N 1 ≦ T_i ≦ 1,000,000,000 (1 ≦ i ≦ N) T_i < T_(i +1) (1 ≦ i ≦ N – 1)
1번 부분문제 (20점)
• N ≦ 20
• 1 ≦ T_i ≦ 20 (1 ≦ i ≦ N)
2번 부분문제 (30점)
• N ≦ 5,000
3번 부분문제 (50점)
• 추가 제한은 없다.
Output
Example #1
3 2
1
3
6
4
Example #2
3 1
1
2
6
6
Example #3
3 3
1
3
6
3
Example #4
10 5
1
2
5
6
8
11
13
15
16
20
12
You must sign in to write code.