AT_kupc2018_k.光と闇の調和

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

现在你面前有 $N$ 个光之宝珠和 $M$ 个暗之宝珠。

每个光之宝珠的能量分别为 $a_1, a_2, \ldots, a_N$ ，对应的，每个暗之宝珠的能量为 $b_1, b_2, \ldots, b_M$ 。

对于每个光之宝珠 $i$ （ $1 \leq i \leq N$ ），它与暗之宝珠的结合范围是从第 $l_i$ 个到第 $r_i$ 个（即 $l_i \leq j \leq r_i$ ）。

你的任务是为这些宝珠设定等级，等级范围为 $1$ 到 $K$ 的整数。

设定等级后，每个宝珠只会与等级比自己低或相同的宝珠结合，那么仅与比自己等级高的宝珠结合的宝珠就会消失。

请你求出，在这种设定下，剩余宝珠的能量平均值的最大值。

输入格式

输入以以下格式从标准输入给出：

$N$ $M$ $K$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_M$ $l_1$ $r_1$ $l_2$ $r_2$ $\ldots$ $l_N$ $r_N$

输出格式

请输出剩余宝珠能量平均值的最大值。允许的绝对误差或相对误差应不超过 $10^{-5}$ 。

输入输出样例

输入#1

输出#1

13.3333333333

输入#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

说明/提示

约束条件

所有输入为整数。
$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$ 分。

样例说明

例如，如果设定光之宝珠的等级为 $10$ 和 $8$ ，暗之宝珠的等级为 $7, 9, 9$ ，那么第 $2$ 个光之宝珠与第 $1$ 个暗之宝珠会消失。此时，剩下的宝珠能量平均值是 $(15 + 12 + 13) / 3 = 13.3333...$ ，这已是最大值。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页