← 返回题目列表

Codeforces · 633/E

E. 启动资金

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

一家电子商务初创公司向投资者推销以获得资金。他们已经运行了 n 周,并且还有一个网站!

他们每周都知道本周的独立访客数量 vi 和收入 ci。为了评估初创公司在从 l 到 r 的某些周内的潜力(包括投资者),投资者使用最大访问者数量乘以 100 和该期间的最低收入中的最小值,即:

$$p(l,r) = \min(100 \cdot \max_{k=l}^{r} v_k, \min_{k=l}^{r} c_k)$$

事实是,投资者不知道如何有效地评估初创公司,因此他们将随机选择 k 个不同的周 li 并将其交给初创公司的经理。对于每个 li,他们应该选择一些 ri ≥ li 并报告在此期间的最大访客数量和最小收入。

然后,投资者将计算初创公司在每个范围内的潜力,并取p(li,ri)的最小值作为初创公司的总评估等级。假设初创公司的管理者总是报告某些特定 li 的 ri 最优值,即使初创公司的最终等级最大化的值,那么初创公司的预期最终等级是多少?

输入

输入的第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 1 000 000)。

第二行包含 n 个整数 vi (1 ≤ vi ≤ 107) - 每周的唯一身份访问者数量。

第三行包含 n 个整数 ci (1 ≤ ci ≤ 107) – 每周的收入。

输出

打印单个实际值 - 启动的预期等级。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

3 2
3 2 1
300 200 300

输出 #1

133.3333333

注意

考虑第一个样本。

如果投资者要求 li = 1 以后,初创公司将选择 ri = 1,这样最大访客数为 3,最小收入为 300。因此,在这种情况下的潜力为 min(3·100, 300) = 300。

如果投资者要求 li = 2 及以上,初创公司将选择 ri = 3,这样最大访客数为 2,最小收入为 200。因此,在这种情况下的潜力为 min(2·100, 200) = 200。

如果投资者要求 li = 3 及以上,初创公司将选择 ri = 3,这样最大访客数为 1,最小收入为 300。因此,在这种情况下的潜力为 min(1·100, 300) = 100。

我们必须等概率地选择一组大小为 2 的集合,并取每个集合中的最小值。这里可能的集合是:{200, 300},{100, 300},{100, 200},实际上是投资者等概率感知的可能值的集合:{200, 100, 100}。因此,期望值为 (100 + 200 + 100) / 3 = 133.(3)。