配点 : 400 点
問題文
N 光球和 有 M 黑暗球体。 第
i 个光球的能量为 a_i 在,i 个暗球的能量为 b_i 。
另外,每个 i \in \{1, 2, ..., N\}, j \in \{l_i, l_i+1, ..., r_i\} , 当我输入i 与第 光球 第 j 黑暗宝珠已合并。
你可以 1 以上 K 同时设置以下整数表示的级别。
设置等级后,所有仅与比你等级更高的宝珠组合的宝珠都会消失。
找到剩余球体的最大平均能量值。
制約
- 所有输入均为整数。
- 1 \leq N, M \leq 3 \times 10^4
- 2 \leq K \leq 3 \times 10^4
- 1 \leq a_i, b_i \leq 10^5
- 1 \leq l_i \leq r_i \leq M
- 每个球体都与一个或多个球体组合。
部分点
- N, M, K \leq 300 的数据集,30 点。 如果您正确回答了所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 370 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N M K a_1 a_2 ... a_N b_1 b_2 ... b_M l_1 r_1 l_2 r_2 : l_N r_N
出力
输出剩余球体的最大平均能量值。 请注意,绝对误差或相对误差为 10^{−5} 如果答案如下,则视为正确。
入力例 1
2 3 10 15 10 11 12 13 1 2 2 3
出力例 1
13.3333333333
例如,如果您设置如下, 第2 与第 光球 第 1 个暗球消失,剩余球的平均能量值为 (15 + 12 + 13) / 3 = 13.3333... 是最大值。
- 光球等级: 10, 8
- 黑暗宝珠等级: 7, 9, 9
入力例 2
1 1 2 10 20 1 1
出力例 2
20.0000000000
入力例 3
10 10 5 97925 72167 60717 63438 89200 6986 16104 76483 23620 9806 24712 38409 16480 2643 28121 51951 23492 4420 28197 28607 1 2 3 10 2 5 9 9 6 7 2 8 3 5 2 3 4 10 5 9
出力例 3
51672.4545454545