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

using namespace std;
ll MOD = 998244353 ;
ll bigMod(ll x,ll y){
    if (y == 0)return 1;
    if (y == 1)return x;
    ll res = bigMod(x , y / 2LL);
    res *= res;
    res %= MOD;
    if (y % 2){
        res *= x;
        res %= MOD;
    }
    return res;
}
ll fac[1000005];
ll choose(ll x,ll y){
    if (x == y)return 1;
    if (y > x)return 0;
    if (y == 0)return 1;
    ll up = fac[x];
    ll down = fac[y] * fac[x-y];
    down %= MOD;
    ll ret = up * bigMod(down , MOD - 2);
    ret %= MOD;
    return ret;
}

int t;
ll n , k , m;
ll a[1000005] , b[1000005] , c[1000005];
ll mem[1000005];
ll idx[1000005];
int pre[1000005];
int ch[1000005];
ll seg[4000000];
void update(int l,int r,int s,int e,int p,ll val){
    if (l > e || r < s)return;
    if (s <= l && r <= e){
        seg[p] = val;
        return;
    }
    int mid = (l+r)/2;
    update(l,mid,s,e,p<<1,val);
    update(mid+1,r,s,e,(p<<1)|1 , val);
    seg[p] = max(seg[p<<1] , seg[(p<<1)|1]);
}
ll qu(int l,int r,int s,int e,int p){
    if (l > e || r < s)return -1e12;
    if (s <= l && r <= e)return seg[p];
    int mid = (l + r)/2;
    return max(qu(l,mid,s,e,p<<1) , qu(mid+1,r,s,e,(p<<1)|1));
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    ll sum = 0;
    for (int i=0;i<n;i++)cin >> a[i];
    for (int i=0;i<n;i++)cin >> c[i] , sum += c[i];
    for (int i=0;i<m;i++)cin >> b[i];
    for (int i=0;i<=1000000;i++)idx[i] = -1;
    for (int i=0;i<m;i++){
        idx[b[i]] = i;
    }
    for (int i=0;i<4000000;i++)seg[i] = -1e12;
    ll add = 0;
    for (int i=0;i<n;i++){
        if (idx[a[i]] == -1 && c[i] > 0)add+=c[i];
    }
    for (int i=0;i<n;i++){
        int x = idx[a[i]];
        if (x != -1){
            ll q = 0;
            if (x > 0)
                q = qu(0,m-1,x-1,m-1,1);
            ll mx = max(q + c[i] , qu(0,m-1,x,x,1));
            update(0,m-1,x,x,1,mx);
        }
    }
    cout << max(0LL , sum - (qu(0,m-1,m-1,m-1,1) + add)) << endl;
    return 0;
}
Copy
Always with Me, Always with You Khaled97ha
GNU G++17
19 ms
39.7 MB
Wrong Answer