#P12545. [集训队互测 2024day4]数据库

[集训队互测 2024day4]数据库

给定长为 nn 的序列 w1,w2,...,wnw_{1},w_{2},...,w_{n},有一个长为 mm 的序列 a1,a2,...,ama_{1},a_{2},...,a_{m},初始 ∀1≤i≤m,ai=0\forall 1\le i\le m,a_{i}=0

给定 qq 次请求,每次请求包含一个数 kk:

若 ∃1≤i≤m,ai=k\exists 1\le i\le m,a_{i}=k,则不进行操作

否则,付出 wkw_{k} 的代价,并选择一个 1≤i≤m1\le i\le m,修改 ai=ka_{i}=k

求最小的代价和

输入格式

第一行三个整数 n,m,qn,m,q,第二行 nn 个整数 w1,w2,...,wnw_{1},w_{2},...,w_{n},第三行 qq 个整数 k1,k2,...,kqk_{1},k_{2},...,k_{q}

输出格式:

一行一个整数,表示答案

样例输入:

3 2 5
1 2 3
1 2 3 2 1

样例输出:

7

样例解释:

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

数据范围:

1≤n,q≤5×1031\le n,q\le 5\times 10^{3},1≤m≤151\le m\le 15,∀1≤i≤n,1≤wi≤105\forall 1\le i\le n,1\le w_{i}\le 10^{5},∀1≤i≤q,1≤ki≤n\forall 1\le i\le q,1\le k_{i}\le n

Subtask1(20分): 1≤n≤101\le n\le 10

Subtask2(20分): m=2m=2

Subtask3(20分): n=5×103n=5\times 10^{3},m=15m=15,q=400q=400且kik_{i}在[1,n][1,n]中均匀随机

Subtask4(20分): 1≤q≤1031\le q\le 10^{3}

Subtask5(20分): 无特殊限制