#2509. 「AHOI / HNOI2018」排列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定 n 个整数 a_1, a_2, \ldots , a_n(0 \le a_i \le n) ,以及 n 个整数 w_1, w_2, …, w_n 。称 a_1, a_2, \ldots , a_n 的一个排列 a_{p[1]}, a_{p[2]}, \ldots , a_{p[n]} a_1, a_2, \ldots , a_n 的一个合法排列,当且仅当该排列满足:对于任意的 k 和任意的 j ,如果 j \le k ,那么 a_{p[j]} 不等于 p[k] 。(换句话说就是:对于任意的 k 和任意的 j ,如果 p[k] 等于 a_{p[j]} ,那么 k<j 。)

定义这个合法排列的权值为 w_{p[1]} + 2w_{p[2]} + \ldots + nw_{p[n]} 。你需要求出在所有合法排列中的最大权值。如果不存在合法排列,输出 -1

样例解释中给出了合法排列和非法排列的实例。

输入格式

第一行一个整数 n

接下来一行 n 个整数,表示 a_1,a_2,\ldots , a_n

接下来一行 n 个整数,表示 w_1,w_2,\ldots ,w_n

输出格式

输出一个整数表示答案。

样例

样例输入 1

3
0 1 1
5 7 3

样例输出 1

32

样例解释 1

对于 a_1=0,a_2=1,a_3=1 ,其排列有

  • a_1=0,a_2=1,a_3=1 ,是合法排列,排列的权值是 1*5+2*7+3*3=28
  • a_2=1,a_1=0,a_3=1 ,是非法排列,因为 a_{p[1]} 等于 p[2]
  • a_1=0,a_3=1,a_2=1 ,是合法排列,排列的权值是 1*5+2*3+3*7=32
  • a_3=1,a_1=0,a_2=1 ,是非法排列,因为 a_{p[1]} 等于 p[2]
  • a_2=1,a_3=1,a_1=0 ,是非法排列,因为 a_{p[1]} 等于 p[3]
  • a_3=1,a_2=1,a_1=0 ,是非法排列,因为 a_{p[1]} 等于 p[3]

因此该题输出最大权值 32

样例输入 2

3
2 3 1
1 2 3

样例输出 2

-1

样例解释 2

对于 a_1=2,a_2=3,a_3=1 ,其排列有:

  • a_1=2,a_2=3,a_3=1 ,是非法排列,因为 a_{p[1]} 等于 p[2]
  • a_2=3,a_1=2,a_3=1 ,是非法排列,因为 a_{p[1]} 等于 p[3]
  • a_1=2,a_3=1,a_2=3 ,是非法排列,因为 a_{p[1]} 等于 p[3]
  • a_3=1,a_1=2,a_2=3 ,是非法排列,因为 a_{p[2]} 等于 p[3]
  • a_2=3,a_3=1,a_1=2 ,是非法排列,因为 a_{p[2]} 等于 p[3]
  • a_3=1,a_2=3,a_1=2 ,是非法排列,因为 a_{p[1]} 等于 p[3]

因此该题没有合法排列。

样例输入 3

10
6 6 10 1 7 0 0 1 7 7
16 3 10 20 5 14 17 17 16 13

样例输出 3

809

数据范围与提示

对于前 20\% 的数据, 1 \le n \le 10

对于前 40\% 的数据, 1 \le n \le 15

对于前 60\% 的数据, 1 \le n \le 1000

对于前 80\% 的数据, 1 \le n \le 100000

对于 100\% 的数据, 1 \le n \le 500000 0 \le a_i \le n (1 \le i \le n) 1 \le w_i \le 10^9 ,所有 w_i 的和不超过 1.5 \times 10^{13}