← 返回题目列表

AtCoder · joig2025_e

E. 神经恶化2(配对2)

中文机器翻译题面 查看原题

配点: 100 点

問題文

2N 卡片从左侧开始在桌子上水平排列。 它的编号为 1, 2, \dots, 2N 。卡 写入 i (1 \leqq i \leqq 2N) 是一个整数 A_i 。每个 对于 x = 1, 2, \dots, N ,一个整数 上面写着 x 的卡片就是 有 2 份。

海狸 Bitaro 使用这些卡片 玩一个名为 神経衰弱 的游戏。 Bitaro有他的右手和左手 1 您一次只能拥有一张卡。
神経衰弱 使用以下步骤执行。 按照

  • i = 1, 2, \dots, 2N 的顺序执行以下操作。
    1. Bitaro是一张卡 选择是否接听 i 。当尝试拿起卡片时,将按顺序执行以下步骤 2. 至 5.。如果您没有拿起任何卡片,请跳过下面的步骤 2 至 5。 如果Bitaro有一张写有
    2. 整数 A_i 的卡片,那么该卡片和桌子上的卡片 i 消失了,Bitaro 获取 V_{A_i} 的分数。
    3. 如果Bitaro的左手有一张牌,他会丢弃该牌。
    4. 如果 Bitaro 右手有一张牌,他会将该牌移至左手。
    5. 卡 如果 i 存在(没有消失),Bitaro用右手打出这张牌。 它有 i 。

通过这些步骤获得的总分将是Bitaro的最终得分。 Bitaro 想知道他在这场比赛中可以获得的最高分数。

给定卡片排列的信息以及分配给每个整数的分数,编写一个程序来找到 Bitaro 可以获得的最大分数。 这是一种

制約

  • 1 \leqq N \leqq 400\,000.
  • (A_1, A_2, \dots, A_{2N}) 为 (1, 1, 2, 2, \dots, N, N) 。
  • 1 \leqq V_k \leqq 10^9 (1 \leqq k \leqq N).
  • 所有输入值都是整数。

小課題

  1. (8 点) (A_1, A_2, \dots, A_N) = (1, 2, \dots, N),N \leqq 5\,000.
  2. (12 点) (A_1, A_2, \dots, A_N) = (1, 2, \dots, N).
  3. (6 点) N \leqq 9.
  4. (9 点) N \leqq 18.
  5. (16 点) N \leqq 300.
  6. (18 点) N \leqq 3\,000.
  7. (18 点) N \leqq 150\,000,V_k = 1 (1 \leqq k \leqq N).
  8. (8 点) N \leqq 150\,000.
  9. (5 点)没有额外的限制。

入力

输入按以下格式给出。

N
A_1 A_2 \cdots A_{2N}
V_1 V_2 \cdots V_N

出力

输出Bitaro可以获得的最高分数。


入力例 1

3
1 2 3 1 2 3
5 2 8

出力例 1

13

Bitaro 按照以下步骤进行评分。 您可以获得 13 。 尝试接听

  1. 卡 如果 1 。卡 写入 1 是一个整数 写入 1 。 Bitaro 是一个整数 由于您没有写有 1 的卡片,因此该卡片不会消失。比特太郎右手拿着一张卡片 您将拥有 1 。
  2. 卡 如果 2 被跳过而不被拾取。 由于您没有写有
  3. 卡 如果 3 。卡 写入 3 是一个整数 写入 3 。 Bitaro 是一个整数 由于您没有写有 3 的卡片,因此该卡片不会消失。 Bitaro左手拿着牌 1 右手有一张牌 一张写有 3 。
  4. 卡 如果 4 。卡 写入 4 是一个整数 写入 1 。 Bitaro 是一个整数 由于您没有写有 1 的卡片。 由于我有 1 ,所以我将这张卡握在左手上。 1 和桌子上的卡片 获取 4 消失了,Bitaro 获取 V_1 = 5 的分数。随后,比太郎左手打出了一张牌。 获取 3 。
  5. 卡 如果 5 被跳过而不被拾取。 由于您没有写有
  6. 卡 如果 6 。卡 写入 6 是一个整数 写入 3 。 Bitaro 是一个整数 由于您没有写有 3 的卡片。 由于我有 3 ,所以我将这张卡握在左手上。 3 和桌子上的卡片 获取 6 消失了,Bitaro 获取 V_3 = 8 的分数。此后,比特罗两手牌都没有了。

比特太郎是 13 由于不可能获得大于13 。

此输入示例是一个小作业。 1, 2, 3, 4, 5, 6, 8, 9 满足约束。


入力例 2

4
1 2 1 2 3 4 4 3
39 62 55 21

出力例 2

156

例如,Bitaro 是一名纸牌玩家。 通过尝试拾取 1, 2, 3, 4, 5, 6, 8 ,得分 V_1 + V_2 + V_3 = 156 。 尝试接听

比特太郎是 156 由于不可能获得大于156 。

此输入示例是一个小作业。 3, 4, 5, 6, 8, 9 满足约束。


入力例 3

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

出力例 3

3117416130

此输入示例是一个小作业。 4, 5, 6, 8, 9 满足约束。


入力例 4

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

出力例 4

6

此输入示例是一个小作业。 4, 5, 6, 7, 8, 9 满足约束。