UOJ Logo Universal Online Judge

UOJ

#357. 【JOISC2017】Sparklers

附件下载 统计

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

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

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

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

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

输入格式

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

接下来 n 行,每行一个整数 xi,表示第 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

限制与约定

对于所有数据,

1Kn105,1T109,0xi109,x1=0,xixj(1ijn)

子任务 分值 n
1 30 20
2 20 1000
3 50 105

时间限制:2s

空间限制:256MB

下载

样例数据下载