配点: 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