Source Code
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()

const double eps=1e-7,PI=3.1415926;
const int N=1e6+10;

using namespace std;

int n,q,m,k,x,y,a[N],mx=-1,mn=1e9,sum,b[N],c[N],mp[N];
string s,s1,s2;
vector < int > vec[N],id[N];

int dis[N],par[N];
void dijkstra(){
    for (int i=1;i<=n;i++)dis[i]=1e18;
    priority_queue < pair < int , int > , vector  < pair < int, int > > ,greater < pair < int, int > > > st;
    for (int i=1;i<=n;i++){
        b[i]*=-1;
        if (a[i]==c[1])dis[i]=b[i],st.push({b[i],i});
    }
    while (st.size()){
        auto tmp=st.top();
        int u=tmp.S;
        st.pop();
        if (dis[u]!=tmp.F)continue;
        for (auto X:vec[u]){
            int len=b[X]*(u!=X);
            if (dis[X]>dis[u]+len){
                dis[X]=dis[u]+len;
                par[X]=u;
                st.push({dis[X],X});
            }
        }
    }
    mn=1e18;
    int idx;
    for (int i=1;i<=n;i++){
        if (a[i]==c[m]&&dis[i]<mn){
            mn=dis[i];
            idx=i;
        }
    }
    while (idx){
        if (a[idx]!=a[par[idx]])mp[idx]=1;
        idx=par[idx];
    }
    mx=0;
    for (int i=1;i<=n;i++){
        b[i]*=-1;
        if (!mp[i]&&b[i]<0)mx+=b[i];
    }
}
int nxt[N];
int32_t main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        id[a[i]].pb(i);
    }
    for (int i=1;i<=n;i++){
        cin>>b[i];
    }
    for (int i=1;i<=m;i++){
        cin>>c[i];
        for (int j=0;j<id[c[i]].size()-1;j++){
            int u=id[c[i]][j],v=id[c[i]][j+1];
            vec[u].pb(v);
        }
    }
    for (int i=1;i<n;i++){
        for (auto x:id[c[i]]){
            int idx=lower_bound(all(id[c[i+1]]),x)-id[c[i+1]].begin();
            if (idx==id[c[i+1]].size())break;
            int v=id[c[i+1]][idx];
            vec[x].pb(v);
        }
    }
    dijkstra();
    cout<<mx<<endl;
    return 0;
}
Copy
Always with Me, Always with You BabaVoss
GNU G++17
821 ms
112.0 MB
Wrong Answer