#P11727. [JOIG 2025] 神経衰弱 2 / Pair Matching 2

[JOIG 2025] 神経衰弱 2 / Pair Matching 2

题目描述

2N2N 张卡牌从左到右依次放在桌子上,编号为 1,2,,2N1,2,\ldots,2N,卡牌 ii 上写有整数 AiA_i。对于 x=1,2,,Nx=1,2,\ldots,N,存在恰好两张卡牌上写的整数为 xx

海狸比太郎决定用这些卡牌玩一个叫做“神经衰弱”的游戏;该游戏的流程如下:

  • 依次考虑卡牌 i=1,2,,2Ni=1,2,\ldots,2N
    1. 比太郎决定是否拿起这张卡牌:如果他决定拿起,那么依次进行以下的步骤 2 至步骤 5;如果他决定不拿起(跳过该卡牌),则跳过以下的步骤;
    2. 如果比太郎的手中持有一张写有 AiA_i 的卡牌,那么该卡牌和卡牌 ii 同时消失,他获得 VAiV_{A_i} 分;
    3. 如果比太郎左手中有一张卡牌,那么他将其丢弃;
    4. 如果比太郎右手中有一张卡牌,那么他将其转移到左手;
    5. 如果卡牌 ii 没有在步骤 2 中消失,那么他将其放在右手中。

通过上面的流程,每次得到的分数之和即为比太郎的最终得分。

请求出比太郎能获得的最大得分。

输入格式

第一行输入一个整数 NN

第二行输入 2N2N 个整数 A1,A2,,A2NA_1,A_2,\ldots,A_{2N}

第三行输入 NN 个整数 V1,V2,,VNV_1,V_2,\ldots,V_N

输出格式

输出一行一个整数,表示最大得分。

3
1 2 3 1 2 3
5 2 8
13
4
1 2 1 2 3 4 4 3
39 62 55 21
156
10
7 2 5 8 4 10 8 2 7 5 6 3 4 1 10 9 9 1 6 3
185163245 734376902 849123714 97860221 844860642 689054872 471545587 607735137 664633003 831663829
3117416130
15
4 3 8 3 10 15 14 1 12 4 13 1 6 7 10 15 2 8 12 2 9 11 11 13 5 9 14 5 6 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6

提示

【样例解释 #1】

比太郎可以通过以下流程获得分数 1313

  1. 拿起卡牌 11,该卡牌上面写着 11;由于比太郎没有其他写着 11 的纸牌,所以他将其放在右手中;
  2. 跳过卡牌 22
  3. 拿起卡牌 33,该卡牌上面写着 33;由于比太郎没有其他写着 33 的纸牌,所以卡牌 11 从右手转移到了左手,他将卡牌 33 放在右手中;
  4. 拿起卡牌 44,该卡牌上面写着 11;由于卡牌 11 上也写着 11,所以两张牌都消失了,他获得 V1=5V_1=5 分,卡牌 33 则从右手转移到了左手;
  5. 跳过卡牌 55
  6. 拿起卡牌 66,该卡牌上面写着 33;由于卡牌 33 上也写着 33,所以两张牌都消失了,他获得 V3=8V_3=8 分,此时他两只手上都没有任何卡牌了。

可以证明这是最优的。

该样例满足子任务 1,2,3,4,5,6,8,91,2,3,4,5,6,8,9 的限制。

【样例解释 #2】

比太郎可以通过拿起卡牌 1,2,3,4,5,6,81,2,3,4,5,6,8 来获得分数 V1+V2+V3=156V_1+V_2+V_3=156。可以证明这是最优的。

该样例满足子任务 3,4,5,6,8,93,4,5,6,8,9 的限制。

【样例解释 #3】

该样例满足子任务 4,5,6,8,94,5,6,8,9 的限制。

【样例解释 #4】

该样例满足子任务 4,5,6,7,8,94,5,6,7,8,9 的限制。

【数据范围】

  • 1N4×1051\le N\le 4\times 10^5
  • A1,A2,,A2NA_1,A_2,\ldots,A_{2N} 中,对于 x=1,2,,Nx=1,2,\ldots,Nxx 正好出现两次;
  • 1Vk1091\le V_k\le 10^9

【子任务】

  1. 88 分)(A1,A2,,AN)=(1,2,,N)(A_1,A_2,\ldots,A_N)=(1,2,\ldots,N)N5000N\le 5000
  2. 1212 分)(A1,A2,,AN)=(1,2,,N)(A_1,A_2,\ldots,A_N)=(1,2,\ldots,N)
  3. 66 分)N9N\le 9
  4. 99 分)N18N\le 18
  5. 1616 分)N300N\le 300
  6. 1818 分)N3000N\le 3000
  7. 1818 分)N1.5×105N\le 1.5\times 10^5Vk1(1kN)V_k\le 1(1\le k\le N)
  8. 88 分)N1.5×105N\le 1.5\times 10^5
  9. 55 分)无附加限制。