QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
[0]

# 6174. 最佳收益问题

Statistics

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

  1. 给定 n 个任务的集合 A
  2. 在上午完成的任务必须按照给定任务序列 x1,x2,,xn 的顺序依次完成;在下午完成的任务必须按照给定任务序列 y1,y2,,ym 的顺序依次完成。
  3. 完成任务所获得的收益在不同时间段有所不同。在上午完成的任务序列 xi 中的各项任务可获得相应收益 ai,而在下午完成的任务序列 yi 中的各项任务可获得相应收益 bi
  4. 每个任务可以在上午完成,也可以在下午完成,但最多只能完成1次。

1la+1ran,且 1lb+1rbn, 则 [la,ra][lb,rb] 分别是上午和下午完成的连续任务区间。当 {xla,xla+1,,xra}{ylb,ylb+1,,yrb}= 时,称这两个连续任务区间不重叠,即这两个连续任务区间中的任务均不相同。此时,这两个连续任务区间所获得的总收益为:

rai=laai+rbi=lbbi

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

输入格式

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

第二行中有 n 个整数,表示上午完成的任务序列 x1,x2,,xn

第三行中有 n 个整数,表示上午完成的任务序列所相应的收益 a1,a2,,an

第四行中有 m 个整数,表示下午完成的任务序列 y1,y2,,ym

第五行中有 m 个整数,表示下午完成的任务序列所相应的收益 b1,b2,,bm

输出格式

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

样例数据

样例输入

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,m10000

测试数据中 100% 的数据满足 1n,m5000001ai,bi1091xi,yin+m