문제
N명의 친구들이 스파클러를 하나씩 손에 들고 불꽃놀이를 하고 있다.
N명의 친구들은 현재 직선 상에 위치해 있다.
i번째 친구는 1번째 친구에게서 X_i미터 만큼 멀리 떨어져 있다.
스파클러 하나에 불을 붙이면 T초 동안 불이 유지되고 K번째 친구의 스파클러에 불을 붙이면서 놀이가 시작된다.
친구들은 직선 위를 달려서 서로 만나 불꽃을 옮겨주며 놀 것이다.
한 친구가 다른 친구에게 불꽃을 옮겨주려면 둘은 같은 위치에 있어야 하고, 한쪽은 불이 아직 꺼지지 않은 상태며 한 쪽은 아직 불이 붙지 않은 상태여야 한다.
정확히 불꽃이 꺼지기 직전 (꺼짐과 동시에) 불을 붙이는 것만 가능하다.
모든 친구들이 스파클러에 불을 붙이는 것이 그들의 목적이다.
너무 빠른 속도로 달리는 것은 위험하기 때문에 친구들은 S m/s이하의 속도로 달리려고 한다.
모든 친구들이 불을 붙일 수 있는 최소의 S를 구해보자.
입력
첫 줄에 N, K, T가 주어진다. (1 <= K <= N <= 100000, 1 <= T <= 1 000 000 000)
이후 N줄에 걸쳐 i번째 줄에 X_i가 주어진다. (0 <= X_i <= 1 000 000 000, X_1 = 0, X_i <= X_j)
<서브태스크>
#1 (30점) : N <= 20
#2 (20점) : N <= 1000
#3 (50점) : 추가적인 제약 조건이 없다.
출력
모든 친구들의 스파클러에 불을 붙일 수 있는 최소의 정수 S를 출력하라.
예제 #1
3 2 50
0
200
300
2
예제 #2
3 2 10
0
200
300
8
예제 #3
20 6 1
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192
6
출처
JOI spring camp 2016/2017
로그인해야 코드를 작성할 수 있어요.