Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

【题目描述】

给定两个长度为 $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

样例