AdditionalFile4899.zip

P3582 [POI 2015 R1] 影迷 Movie-goer

题目描述

共有 $m$ 部电影，编号为 $1,2,\ldots,m$，第 $i$ 部电影的好看值为 $w_i$。

在 $n$ 天之中，每天会放映一部电影，第 $i$ 天放映的是第 $f_i$ 部。

你可以选择 $l,r$（$1\le l\le r\le n$），并观看第 $l,l+1,\ldots,r$ 天内所有的电影。

但如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。

现在，您需要最大化观看且仅观看过一次的电影的好看值的总和。

输入格式

第一行两个整数 $n,m$。

第二行包含 $n$ 个整数，第 $i$ 个表示 $f_i$。

第三行包含 $m$ 个整数，第 $i$ 个表示 $w_i$。

输出格式

一行一个整数，表示仅观看过一次的电影的好看值的总和的最大值。

输入输出样例 #1

输入 #1

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

输出 #1

15

说明/提示

【数据范围】

对于 $100\%$ 的数据，$1\le m\le n\le 10^6$，$1\le f_i\le m$，$1\le w_i\le 10^6$。

---

原题名称：Kinoman。

#4899. 「POI2015 R1」影迷 Movie-goer

标签: 传统 | 时间限制: 6000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — I etap Kinoman

Bajtazar 是个狂热的电影爱好者，得知他最爱的小众影院推出夏季促销活动，兴奋不已。整个夏天，$n$ 天里每天放映一部来自 $m$ 部电影的影片。促销通票允许免费观看任意场次，但有个条件：不能中断观影（即错过一场，通票作废；首场可自由选择）。

Bajtazar 根据网评给每部电影定了精彩度。他想用通票最大化观看电影的精彩度总和。但他讨厌重复看同一部电影，因为重看会让他觉得无聊，破坏美好回忆。所以，他真正想做的是最大化只看恰好一次的电影的精彩度总和。

输入格式

输入第一行包含两个整数 $n$ 和 $m$ $(1 \leq m \leq n \leq 1000000)$，分别表示促销天数和电影数量。为方便起见，电影编号为 $1$ 到 $m$。

第二行包含 $n$ 个整数 $f_{1}, f_{2}, \ldots, f_{n}$ $(1 \leq f_{i} \leq m)$，$f_{i}$ 表示第 $i$ 天放映的电影编号。

第三行包含 $m$ 个整数 $w_{1}, w_{2}, \ldots, w_{m}$ $(1 \leq w_{j} \leq 1000000)$，$w_{j}$ 表示编号 $j$ 的电影的精彩度。

某些电影可能在促销期间完全不放映。

输出格式

输出一行一个整数，表示 Bajtazar 最佳使用通票时，只看恰好一次的电影的精彩度总和。

样例

输入

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

输出

15

Bajtazar 可从第二天开始连续看 $6$ 场，观看编号为 $2$、$3$、$4$ 的电影各一次，总精彩度为 $3+6+6=15$。

附加样例

1. $n=10, m=5$，随机样例；
2. $n=100, m=50$，随机样例；
3. $n=1000000, m=1000000$，除一部电影外，所有电影精彩度为 $200000$ 且不重复；一部电影精彩度为 $1000000$，每 $10$ 天重复一次。

数据范围与提示

对于 $70\%$ 的数据，$n \leq 100000$。
对于其中 $20\%$ 的数据，$n \leq 8000$。