#PQJ1416x7762. QOJ 1416_7762

    ID: 2600 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测

QOJ 1416_7762

标题: 数据库 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

给定长为 n 的序列 w1,w2,...,wn,有一个长为 m 的序列 a1,a2,...,am,初始 ∀1≤i≤m,ai=0

给定 q 次请求,每次请求包含一个数 k:

若 ∃1≤i≤m,ai=k,则不进行操作

否则,付出 wk 的代价,并选择一个 1≤i≤m,修改 ai=k

求最小的代价和

输入格式

第一行三个整数 n,m,q,第二行 n 个整数 w1,w2,...,wn,第三行 q 个整数 k1,k2,...,kq

输出格式:

一行一个整数,表示答案

样例输入:

3 2 5
1 2 3
1 2 3 2 1

样例输出:

7

样例解释:

第一次操作修改 a1=1,第二次操作修改 a2=2,第三次操作修改 a1=3,第四次操作无修改,第五次操作修改 a1=1,代价和为 1+2+3+0+1=7

数据范围:

1≤n,q≤5×103,1≤m≤15,∀1≤i≤n,1≤wi≤105,∀1≤i≤q,1≤ki≤n

Subtask1(20分): 1≤n≤10

Subtask2(20分): m=2

Subtask3(20分): n=5×103,m=15,q=400且ki在[1,n]中均匀随机

Subtask4(20分): 1≤q≤103

Subtask5(20分): 无特殊限制