#2509. 「AHOI / HNOI2018」排列

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

题目描述

给定 nnn 个整数 a1,a2,,an(0ain),以及 nnn 个整数 w1,w2,,wn。称 a1,a2,,an 的一个排列 ap[1],ap[2],,ap[n]a1,a2,,an 的一个合法排列,当且仅当该排列满足:对于任意的 kkk 和任意的 jjj,如果 j≤kj \le kjk,那么 ap[j]a_{p[j]}ap[j] 不等于 p[k]p[k]p[k]。(换句话说就是:对于任意的 kkk 和任意的 jjj,如果 p[k]p[k]p[k] 等于 ap[j]a_{p[j]}ap[j],那么 k<jk<jk<j。)

定义这个合法排列的权值为 wp[1]+2wp[2]++nwp[n]。你需要求出在所有合法排列中的最大权值。如果不存在合法排列,输出 −1-11

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

输入格式

第一行一个整数 nnn

接下来一行 nnn 个整数,表示 a1,a2,,an

接下来一行 nnn 个整数,表示 w1,w2,,wn

输出格式

输出一个整数表示答案。

样例

样例输入 1

3
0 1 1
5 7 3

样例输出 1

32

样例解释 1

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

  • a1=0,a2=1,a3=1a_1=0,a_2=1,a_3=1a1=0,a2=1,a3=1,是合法排列,排列的权值是 1∗5+2∗7+3∗3=281*5+2*7+3*3=2815+27+33=28
  • a2=1,a1=0,a3=1a_2=1,a_1=0,a_3=1a2=1,a1=0,a3=1,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[2]p[2]p[2]
  • a1=0,a3=1,a2=1a_1=0,a_3=1,a_2=1a1=0,a3=1,a2=1,是合法排列,排列的权值是 1∗5+2∗3+3∗7=321*5+2*3+3*7=3215+23+37=32
  • a3=1,a1=0,a2=1a_3=1,a_1=0,a_2=1a3=1,a1=0,a2=1,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[2]p[2]p[2]
  • a2=1,a3=1,a1=0a_2=1,a_3=1,a_1=0a2=1,a3=1,a1=0,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]
  • a3=1,a2=1,a1=0a_3=1,a_2=1,a_1=0a3=1,a2=1,a1=0,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]

因此该题输出最大权值 323232

样例输入 2

3
2 3 1
1 2 3

样例输出 2

-1

样例解释 2

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

  • a1=2,a2=3,a3=1a_1=2,a_2=3,a_3=1a1=2,a2=3,a3=1,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[2]p[2]p[2]
  • a2=3,a1=2,a3=1a_2=3,a_1=2,a_3=1a2=3,a1=2,a3=1,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]
  • a1=2,a3=1,a2=3a_1=2,a_3=1,a_2=3a1=2,a3=1,a2=3,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]
  • a3=1,a1=2,a2=3a_3=1,a_1=2,a_2=3a3=1,a1=2,a2=3,是非法排列,因为 ap[2]a_{p[2]}ap[2] 等于 p[3]p[3]p[3]
  • a2=3,a3=1,a1=2a_2=3,a_3=1,a_1=2a2=3,a3=1,a1=2,是非法排列,因为 ap[2]a_{p[2]}ap[2] 等于 p[3]p[3]p[3]
  • a3=1,a2=3,a1=2a_3=1,a_2=3,a_1=2a3=1,a2=3,a1=2,是非法排列,因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]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%20\%20% 的数据,1≤n≤101 \le n \le 101n10

对于前 40%40\%40% 的数据,1≤n≤151 \le n \le 151n15

对于前 60%60\%60% 的数据,1≤n≤10001 \le n \le 10001n1000

对于前 80%80\%80% 的数据,1≤n≤1000001 \le n \le 1000001n100000

对于 100%100\%100% 的数据,1≤n≤5000001 \le n \le 5000001n5000000≤ai≤n(1≤i≤n)0 \le a_i \le n (1 \le i \le n)0ain(1in)1≤wi≤1091 \le w_i \le 10^91wi109 ,所有 wiw_iwi 的和不超过 1.5×10131.5 \times 10^{13}1.5×1013