【题目描述】
给定两个长度为 $n$ 的序列 ${a_i}, {b_i}$,设 $f(l, r) = \max_{s⊆ [l,r]∩Z}\frac{∑_{i\in s}a_i} {(∑_{i\in s}b_i)+ c}$。
求 $f(i, j) (1 ⩽ i ⩽ j ⩽ n)$ 的第 $k$ 小值。
【输入格式】
从文件 fraction.in
中读入数据。
第一行三个正整数 $n$, $k$, $c$。
第二行 $n$ 个正整数 $a_1, a_2, . . . , a_n$。
第三行 $n$ 个正整数 $b_1, b_2, . . . , b_n$。
【输出格式】
输出到文件 fraction.out
中。
一行一个实数。
当你的答案和标准答案的绝对或相对误差不超过 $10^{-6}$ 时,你的答案被视为正确。
【样例 1 输入】
3 4 12
2 1 5
6 8 6
【样例 1 输出】
0.277777778
【样例 1 解释】
$f(1, 1) = \frac1 9, f(2, 2) = \frac 1 {20}, f(3, 3) = \frac 5 {18}, f(1, 2) = \frac 3 {26}, f(2, 3) = \frac 5{18}, f(3, 3) = \frac 7{24}$,第 4 小为 $\frac 5{18}$
。
你可以通过修改 $k$ 获得更多小样例。
【数据范围与提示】
对于所有数据,$1 ⩽ n ⩽ 2 × 10^5, 1 ⩽ k ⩽\frac {n(n + 1)}2, 1 ⩽ a_i, b_i ⩽ 10^7, 1 ⩽ c ⩽ 10^{12}, a_i ⩽ b_i$。
子任务编号 | 特殊限制 | 分值 |
---|---|---|
$1$ | $1 ⩽ n ⩽ 18$ | $5$ |
$2$ | $∀i < j, a_i = a_j , b_i = b_j$ | $7$ |
$3$ | $∀i < j, \frac {a_i} {b_i}=\frac {a_j} {b_j}$ | $8$ |
$4$ | $1 ⩽ n ⩽ 50$ | $11$ |
$5$ | $1 ⩽ n ⩽ 200$ | $14$ |
$6$ | $1 ⩽ n ⩽ 2000$ | $17$ |
$7$ | $k = 1$ | $5$ |
$8$ | $k = n(n + 1)/2$ | $5$ |
$9$ | 无 | 28 |