Strange Function

题意翻译

### 题面描述 定义函数 $f$：$f(x)$ 为所有满足 $x_i>x_{1,2,\cdots,i-1}$ 的 $x_i$ 组成的序列，例如 $f[3,1,2,7,7,3,6,7,8]=[3,7,8]$。 给出两个序列 $a,b$，你可以删掉 $a$ 中的一些元素。删掉 $a_i$ 的代价为 $p_i$。你需要求出最小代价使得 $f(a)=b$ 或给出无解。 ### 输入格式 第一行一个整数 $n\ (1\leq n\leq 5\cdot 10^5)$，表示 $a$ 的长度。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n\ (1\leq a_i\leq n)$。 第三行 $n$ 个整数 $p_1,p_2,\cdots,p_n\ (|p_i|\leq 10^9)$。 第四行一个整数 $m\ (1\leq m\leq n)$，表示 $b$ 的长度。 第五行 $m$ 个整数 $b_1,b_2,\cdots,b_m\ (1\leq b_i\leq n,b_{i-1}<b_i)$。 ### 输出格式 如果答案存在，在第一行输出 $\texttt{YES}$，第二行输出最小代价。否则输出一行 $\texttt{NO}$。 translated by Alex_Wei.

题目描述

Let's denote the following function $ f $ . This function takes an array $ a $ of length $ n $ and returns an array. Initially the result is an empty array. For each integer $ i $ from $ 1 $ to $ n $ we add element $ a_i $ to the end of the resulting array if it is greater than all previous elements (more formally, if $ a_i > \max\limits_{1 \le j < i}a_j $ ). Some examples of the function $ f $ : 1. if $ a = [3, 1, 2, 7, 7, 3, 6, 7, 8] $ then $ f(a) = [3, 7, 8] $ ; 2. if $ a = [1] $ then $ f(a) = [1] $ ; 3. if $ a = [4, 1, 1, 2, 3] $ then $ f(a) = [4] $ ; 4. if $ a = [1, 3, 1, 2, 6, 8, 7, 7, 4, 11, 10] $ then $ f(a) = [1, 3, 6, 8, 11] $ . You are given two arrays: array $ a_1, a_2, \dots , a_n $ and array $ b_1, b_2, \dots , b_m $ . You can delete some elements of array $ a $ (possibly zero). To delete the element $ a_i $ , you have to pay $ p_i $ coins (the value of $ p_i $ can be negative, then you get $ |p_i| $ coins, if you delete this element). Calculate the minimum number of coins (possibly negative) you have to spend for fulfilling equality $ f(a) = b $ .

输入输出格式

输入格式

The first line contains one integer $ n $ $ (1 \le n \le 5 \cdot 10^5) $ — the length of array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ $ (1 \le a_i \le n) $ — the array $ a $ . The third line contains $ n $ integers $ p_1, p_2, \dots, p_n $ $ (|p_i| \le 10^9) $ — the array $ p $ . The fourth line contains one integer $ m $ $ (1 \le m \le n) $ — the length of array $ b $ . The fifth line contains $ m $ integers $ b_1, b_2, \dots, b_m $ $ (1 \le b_i \le n, b_{i-1} < b_i) $ — the array $ b $ .

输出格式

If the answer exists, in the first line print YES. In the second line, print the minimum number of coins you have to spend for fulfilling equality $ f(a) = b $ . Otherwise in only line print NO.

输入输出样例

输入样例 #1

11
4 1 3 3 7 8 7 9 10 7 11
3 5 0 -2 5 3 6 7 8 2 4
3
3 7 10

输出样例 #1

YES
20

输入样例 #2

6
2 1 5 3 6 5
3 -9 0 16 22 -14
4
2 3 5 6

输出样例 #2

NO

题意翻译

### 题面描述 定义函数 $f$：$f(x)$ 为所有满足 $x_i>x_{1,2,\cdots,i-1}$ 的 $x_i$ 组成的序列，例如 $f[3,1,2,7,7,3,6,7,8]=[3,7,8]$。 给出两个序列 $a,b$，你可以删掉 $a$ 中的一些元素。删掉 $a_i$ 的代价为 $p_i$。你需要求出最小代价使得 $f(a)=b$ 或给出无解。 ### 输入格式 第一行一个整数 $n\ (1\leq n\leq 5\cdot 10^5)$，表示 $a$ 的长度。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n\ (1\leq a_i\leq n)$。 第三行 $n$ 个整数 $p_1,p_2,\cdots,p_n\ (|p_i|\leq 10^9)$。 第四行一个整数 $m\ (1\leq m\leq n)$，表示 $b$ 的长度。 第五行 $m$ 个整数 $b_1,b_2,\cdots,b_m\ (1\leq b_i\leq n,b_{i-1}<b_i)$。 ### 输出格式 如果答案存在，在第一行输出 $\texttt{YES}$，第二行输出最小代价。否则输出一行 $\texttt{NO}$。 translated by Alex_Wei.