← 返回题目列表

AtCoder · typical90_a

001. 羊羹派对(★4)

中文机器翻译题面 查看原题

配点: 4 点

問題文

左右长度为 L [cm] 有洗衣机。 从左侧开始有 N 次剪切。 i 第一个中断从左边开始 它位于 A_i [cm]。

你 超出 N 削减 K 选择棋子并使用羊羹。 我想把它分成 K+1 块。因此,以下值是 分数 。

  • K+1 最短的长度(厘米)

求除以最大化分数时获得的分数。

制約

  • 1 \leq K \leq N \leq 100000
  • 0 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \leq 10^9
  • 输入全部为整数

入力

输入是按以下格式从标准输入给出的。

N L
K
A_1 A_2 \cdots A_N

出力

请输出所需的分数。


入力例 1

3 34
1
8 13 26

出力例 1

13

从左起 当在第 2 次切割时,长度 13 [cm]件数和长度 21 分成[cm]块并评分 13 可以实现。


入力例 2

7 45
2
7 11 16 20 28 34 38

出力例 2

12

从左起 当在第 3 第 和 在第 5 次休息时划分时,分数 12 可以实现。


入力例 3

3 100
1
28 54 81

出力例 3

46

从左起 当在第 2 次休息时划分时,分数 46 可以实现。


入力例 4

3 100
2
28 54 81

出力例 4

26

入力例 5

20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954

出力例 5

170