QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

# 6174. 最佳收益问题

统计

具有连续时间段和变化收益的任务安排问题可描述如下。

  1. 给定 $n$ 个任务的集合 $A$。
  2. 在上午完成的任务必须按照给定任务序列 $x_1,x_2,\cdots,x_n$ 的顺序依次完成;在下午完成的任务必须按照给定任务序列 $y_1,y_2,\cdots,y_m$ 的顺序依次完成。
  3. 完成任务所获得的收益在不同时间段有所不同。在上午完成的任务序列 $x_i$ 中的各项任务可获得相应收益 $a_i$,而在下午完成的任务序列 $y_i$ 中的各项任务可获得相应收益 $b_i$。
  4. 每个任务可以在上午完成,也可以在下午完成,但最多只能完成1次。

设 $1 \leq l_a +1 \leq r_a \leq n$,且 $1 \leq l_b +1 \leq r_b \leq n$, 则 $[l_a,r_a]$ 和 $[l_b,r_b]$ 分别是上午和下午完成的连续任务区间。当 $\{x_{l_a}, x_{l_a+1}, \cdots, x_{r_a}\} \cap \{y_{l_b}, y_{l_b+1}, \cdots, y_{r_b}\} = \varnothing$ 时,称这两个连续任务区间不重叠,即这两个连续任务区间中的任务均不相同。此时,这两个连续任务区间所获得的总收益为:

$$\sum_{i=l_a}^{r_a} a_i + \sum_{i=l_b}^{r_b} b_i$$

最佳收益问题:对于给定的上午和下午完成的任务序列,在所有不重叠的连续任务区间对中,计算能获得的最大收益。上午和下午完成的连续任务区间均可为空,此时相应的任务区间中没有任务。

输入格式

第一行中有两个正整数 $n$ 和 $m$,分别表示上午和下午完成的任务序列的长度。

第二行中有 $n$ 个整数,表示上午完成的任务序列 $x_1,x_2,\cdots, x_n$。

第三行中有 $n$ 个整数,表示上午完成的任务序列所相应的收益 $a_1,a_2,\cdots,a_n$。

第四行中有 $m$ 个整数,表示下午完成的任务序列 $y_1,y_2,\cdots, y_m$。

第五行中有 $m$ 个整数,表示下午完成的任务序列所相应的收益 $b_1,b_2,\cdots,b_m$。

输出格式

输出一行一个整数,表示答案。

样例数据

样例输入

8 5
12 10 2 1 6 7 4 8
1 9 2 8 2 10 9 10
6 9 7 8 3
7 7 8 3 3

样例输出

58

子任务

测试数据中 $40\%$ 的数据满足 $n,m \leq 10\,000$

测试数据中 $100\%$ 的数据满足 $1 \leq n,m \leq 500\,000$,$1 \leq a_i,b_i \leq 10^9$,$1 \leq x_i,y_i \leq n+m$。