d088. Q-6-24. 隔離採礦 ( @@@ ) ( 108 全國高中賽 )

Content

外星採礦隊在烏邦圖星球已經探勘到某種礦物的礦脈，這條礦脈是一個筆直的直線，且一共有 $n$ 個可以挖礦井的地點，這些地點就稱為可開採點。所有的可開採點由 $1$ 到 $n$ 依序編號，第 $i$ 個可開採點的高度為 $h(i)$ 而開採價值為 $v(i)$。

現在希望能找出某些可開採點來實際進行鑽井挖礦，因為安全因素，任兩個礦井之間必須有另外一個開採點，其高度超過這兩個礦井。

身為外星採礦隊的程式設計師，你的目標是計算出最大的開採價值總和。

一個 $n=10$ 的例子，各點的高度依序是 $h = (2, 5, 3, 2, 4, 2, 3, 1, 4, 3)$，

而開採價值則依序是 $v = (1, 8, 3, 1, 5, 1, 4, 2, 4, 2)$，

也就是說 $h(1)=2, h(2)=5, …, h(10)=3$，而 $v(1)=1, v(2)=8, …, v(10)=2$。

在此例中，最佳的開採方式是$1,3,7,10$，所能獲得的最大開採價值總和為 $1+3+4+2=10$。

你可以看到，任兩個實際開採點之間都有一個高度更高的點。

Input

每筆測資的第一行是一個正整數 $n$，$n ≤ 1e6$，代表可開採點的數量。

第二行是 $n$ 個非負整數，依序代表每一點的高度 $h(1), h(2), …, h(n)$；

第三行是 $n$ 個正整數，依序代表每一點的開採價值 $v(1), v(2), …, v(n)$。

每一行相鄰數字間以一空白間隔。

每一點的高度不會超過 1e9，價值不會超過 1e5。

Output

輸出爲一整數，代表最大的開採價值總和。

每筆測資的答案不超過 2e9。

Sample Input #1

10
2 5 3 2 4 2 3 1 4 3
1 8 3 1 5 1 4 2 4 2

Sample Output #1

Sample Input #2

5
3 3 3 3 3
5 3 2 3 4

Sample Output #2

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (20%): 1.0s , <50M
不公開測資點#1 (20%): 1.0s , <50M
不公開測資點#2 (20%): 1.0s , <50M
不公開測資點#3 (20%): 1.0s , <50M
不公開測資點#4 (20%): 1.0s , <50M

Hint ：

Tags:

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」