← 返回题目列表

Codeforces · 150/C

C. 聪明的骗子

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

我想提醒您恩沃茨克的冬天并不热并没有多大意义。这极大地提高了公共交通的受欢迎程度。 62 路公交车的路线恰好有 n 个站点(第 1 站最先行驶,第 n 站最后行驶)。停靠点位于一条直线上,其坐标为 0 = x1 < x2 < ... < xn。

每天正好有 m 个人乘坐 62 路公交车。对于每个人,我们都知道他上车的车站号码和他下车的车站号码。从站点 a 到站点 b (a < b) 的车票费用为 xb - xa 卢布。但是,售票员最多可以选择一个不售票的航段。我们的意思是售票员应该选择 C ​​和 D (С <= D) 并出售航段 [A, C] 和 [D, B] 的车票,或者根本不出售车票。售票员和乘客平分节省下来的钱。售票员的“免税收入”有时会因公交车在两个连续站点之间的某些路段上行驶时进行的检查而中断。检查员对每位未持有该线路路段车票的乘客处以c卢布的罚款。

你知道所有站点 xi 的协调;第 i 名乘客上下车的站点数,ai 和 bi (ai < bi);罚款c;还有 pi — 在第 i 个站点和第 i + 1 个站点之间的路段进行检查的概率。售票员要求你帮助他制定一个售票计划,使他的利润的数学期望最大化。

输入

第一行包含三个整数 n、m 和 c (2 ≤ n ≤ 150 000, 1 ≤ m ≤ 300 000, 1 ≤ c ≤ 10 000)。

下一行包含 n 个整数 xi (0 ≤ xi ≤ 109, x1 = 0, xi < xi + 1) — 公交车路线上车站的坐标。

第三行包含 n - 1 个整数 pi (0 ≤ pi ≤ 100) — 在停靠点 i 和停靠点 i + 1 之间的路段上进行检查的概率(以百分比表示)。

然后按照描述公交车乘客的 m 行进行操作。每行恰好包含两个整数 ai 和 bi (1 ≤ ai < bi ≤ n) — 第 i 位乘客上下车的站点数。

输出

打印单个实数——售票员利润的最大期望。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

3 3 10
0 10 100
100 0
1 2
2 3
1 3

输出 #1

90.000000000

输入 #2

10 8 187
0 10 30 70 150 310 630 1270 2550 51100
13 87 65 0 100 44 67 3 4
1 10
2 9
3 8
1 5
6 10
2 7
4 10
4 5

输出 #2

76859.990000000

注意

对第一个示例的评论:

第一个和第三个乘客获得了从站点 1 到站点 2 的车票。第二个乘客没有获得车票。 1-2 段始终会有检查,但两位乘客都有该检查的票。 2-3 路段从来没有检查,这就是为什么第二位乘客可以逃脱作弊行为。我们的总利润是 (0 + 90 / 2 + 90 / 2) = 90。