一家电子商务初创公司向投资者推销以获得资金。他们已经运行了 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)。