← 返回题目列表

AtCoder · kupc2018_k

K. 光明与黑暗的和谐

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

配点 : 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