UOJ Logo Universal Online Judge

UOJ

#357. 【JOI2017春季合宿】Sparklers

统计

小S和小M去看花火大会。

一共有 $n$ 个人按顺序排成一排,每个人手上有一个仅能被点燃一次的烟花。最开始时第 $K$ 个人手上的烟花是点燃的。

烟花最多能燃烧 $T$ 时间。每当两个人的位置重叠且其中一个人手上的烟花是点燃的时,另一个人手上的烟花可以被点燃。

现在小M想要知道,每个人至少需要以多快的速度 $s$ 奔跑,才能使得每个人手中的烟花都能被点燃。

可怜的小M当然不会啦,所以她向你求助。

输入格式

第一行三个整数 $n,K,T$。意义如题面所示。

接下来 $n$ 行,每行一个整数 $x_i$,表示第 $i$ 个人的位置。

输出格式

一行一个整数,表示最小的整数 $s$ 使得每个人手中的烟花都能被点燃。

样例一

input

3 2 50
0
200
300

output

2

样例二

input

3 2 10
0
200
300

output

8

样例三

input

20 6 1
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192

output

6

限制与约定

对于所有数据,

$1\le K\le n\le 10^5,1\le T\le 10^9 ,0\le x_i\le 10^9 ,x_1=0,x_i \le x_j(1\le i\le j \le n)$。

子任务 分值 $n$
1 30 $\le 20$
2 20 $\le 1000$
3 50 $\le 10^5$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载