LibreOJ

3062 「ROI 2016 Day1」摸鱼否

内存限制：256 MB 时间限制：1000 ms

题目描述

译自 ROI 2016 Day1 T3. Ловить или не ловить

河口是入海口啊，你说河口在上游还是下游 →_→
「开渔」指捕鱼季开始，「休渔」指捕鱼季结束

开渔了！你可以在河流上的 $n$ 个地点捕鱼，它们距离河口的距离为 $x_1\ldots x_n$（按递增顺序给出）。在这个捕鱼季节，$i$ 号地点最多能捕捞 $a_i$ 吨鱼。
你可以在岸边的 $m$ 个批发基地卖鱼，$y_1\ldots y_m$（按递增顺序给出）。在这个捕鱼季节，$j$ 号批发基地计划以每吨 $c_j$ 卢布的价格购买至多 $b_j$ 吨鱼。
开渔时，你从河口出发捕鱼，休渔时需要返回河口。你可以任意顺流而下 / 逆流而上 / 捕鱼 / 卖鱼。逆流而上的燃料费用为每单位距离 $p$ 卢布，顺流而下则无需燃料费用。
试求可以获得的最大利润（卖鱼所得的净利润与消耗燃料的成本之差）。

输入格式

$n,m,p$
接下来 $n$ 行：$x_i, a_i$
接下来 $m$ 行：$y_j, b_j, c_j$

样例 1

样例 2

  • 先去 1 号地点（消耗了价值 600 卢布的燃料）
  • 捕捞 5 吨鱼
  • 顺流而下 1 单位距离，到达 1 号批发基地
  • 以每吨 2000 卢布的价格卖掉（毛收入 10000 卢布）

总利润 9400 卢布。

样例 3

数据范围与提示

对于所有数据，$0 ⩽ p ⩽ 10^9,$ $0 < x_1 < x_2 < \dots < x_n ⩽ 10^9,$ $0 < a_i ⩽ 10^6,$ $0 < y_1 < y_2 < \dots < y_m ⩽ 10^9,$ $0 < b_j ,c_j ⩽ 10 ^6.$

子任务 # 分值 $1 ⩽ n,m ⩽ $ 附加条件 依赖子任务
1 16 $\phantom{0}50\:000$ $p = 0$
2 9 $\phantom{0}50\:000$ $y_m < x_1$ 1
3 16 $\phantom{0}50\:000$ $x_n < y_1$  1 
4 11 $\phantom{00}1\:000$ 无
5 9 $\phantom{00}8\:500$ 无 4
6 20 $\phantom{0}50\:000$ 无 1–5
7 6 $200\:000$ 无 1–6
8 7 $320\:000$ 无 1–7
9 6 $500\:000$ 无 1–8

样例

样例输入 1

3 2 0
1 5
2 3
4 5
2 2 10
3 6 5

样例输出 1

50

样例输入 2

2 1 100
6 5
100 4
5 100 2000

样例输出 2

9400

样例输入 3

3 3 10
1 1
10 100
20 10
2 1000 1
11 50 50
17 50 2

样例输出 3

2441