Source Code
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
// please, read the question correctly (do you need set or multiset)???
const int N=1000010; //check the limits, dummy
int a[N], b[N];
int n, m, nn;
int pos[N];

ll t[2 * N];
void modify(int l, int r, ll value) {
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) t[l++] += value;
    if (r&1) t[--r] += value;
  }
}

ll query(int p) {
  ll res = 0;
  for (p += n; p > 0; p >>= 1) res += t[p];
  return res;
}
ll dp(){
	for(int i=0; i<nn; ++i){
		int p = pos[a[i]];
		// cout<<i<<" "<<a[i]<<" "<<p<<endl;
		if(p==0){
			if(b[i]<0){
				modify(0,n,b[i]);
			}
		}
		else{
			ll tmp = query(p-1);
			ll tmp1 = query(p);
			// cout<<"@@"<<tmp<<" "<<tmp1<<endl;
			if(tmp<tmp1+min(b[i], 0)){
				modify(p, p+1, tmp-tmp1);
				// cout<<"###"<<p<<" "<<query(p)<<endl;
			}
			else{
				modify(p, p+1, min(b[i], 0));
			}
			// cout<<"#*)(%"<<p-1<<" "<<query(p-1)<<endl;
			if(b[i]<0){
				modify(0, p, b[i]);
			}
		}
	}
	return query(m);
}
int main(){
// int t;cin>>t;while(t--){

	scanf("%d%d",&nn,&m);
	for(int i=0; i<nn; ++i){
		scanf("%d",a+i);
	}
	n = m+1;
	for(int i=0; i<nn; ++i){
		scanf("%d",b+i);
	}
	int x;
	for(int i=1; i<=m; ++i){
		scanf("%d",&x);
		pos[x]=i;
		modify(i,i+1,1e14);
	}
	ll ans = dp();
	cout<<ans<<endl;

// }
return 0;
}
Copy
Always with Me, Always with You Zain
GNU G++17
209 ms
14.8 MB
Wrong Answer