K - 光と闇の調和
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
- どのオーブも1つ以上のオーブと結合されている。
部分点
- 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