Source Code
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

struct segtree
{
    int sz;

    vector <ll> mins;

    void init(int n)
    {
        sz = n;
        mins.resize(n<<2);
    }

    void update(int nd,int l,int r,int pos,ll val)
    {
        if( l == pos && r == pos )
        {
            mins[nd] = val;
            return;
        }

        int mid = (l+r)/2;

        if( pos <= mid )
            update(nd<<1,l,mid,pos,val);
        else
            update(nd<<1|1,mid+1,r,pos,val);

        mins[nd] = min( mins[nd<<1] , mins[nd<<1|1] );
    }

    void update(int pos,ll val) { update(1,1,sz,pos,val); }

    ll querymin(int nd,int l,int r,int from,int to)
    {
        if( from <= l && r <= to )
            return mins[nd];
        if( from > r || l > to )
            return 1e18;

        int mid = (l+r)/2;

        return min( querymin(nd<<1,l,mid,from,to) , querymin(nd<<1|1,mid+1,r,from,to) );
    }

    ll querymin(int l,int r) { return querymin(1,1,sz,l,r); }
};

const int N = 1001000;

int n,m,a[N],b[N],c[N];
ll dp[N],inf = 1e18,ans;
vector <int> v[N];
set <int> s;
segtree st;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        c[i] = min( c[i] , 0 );
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        s.insert(b[i]);
    }

    st.init(n+1);

    for(int i=m;i>=1;i--)
    {
        ll del = 0;
        for(auto &x:v[b[i]])
            del += c[x];

        for(auto &x:v[b[i]])
        {
            dp[x] = del-c[x]+st.querymin(x+1,n+1);
            st.update(x,del-c[x]+st.querymin(x+1,n+1));
        }
    }

    for(int i=1;i<=n;i++)
        if( s.find(a[i]) != s.end() )
            ans = min( ans , dp[i] );

    for(int i=1;i<=n;i++)
        if( s.find(a[i]) == s.end() )
            ans += c[i];

    printf("%lld\n",ans);
}
Copy
Always with Me, Always with You Naseem17
GNU G++17
1319 ms
94.7 MB
Wrong Answer