Source Code
#include<bits/stdc++.h>
#define GO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef pair<int, int> pi;
const ll Mod = 998244353;
const ll INF = (ll)(1e18) + 5;
const ll N = 1e6 + 5, M = 18;

// for range update point query use upd(l,r,val) and query(pos)
// for point update range query use upd(pos,val) and query(l,r)
// for range update range query please code lazy segtree XD
struct BIT
{
	vector<ll> a;
	int n;
	BIT() {}
	BIT(int n) :n(n + 1), a(n + 5) {}
	void upd(int i, ll val = 1)
	{
		i++;
		while (i <= n)
		{
			a[i] += val;
			i += (i & -i);
		}
	}
	void upd(int i, int j, ll val)
	{
		if (i > j)
			return;
		upd(i, val);
		upd(j + 1, -val);
	}
	ll query(int i)
	{
		i++;
		ll res = 0;
		while (i > 0)
		{
			res += a[i];
			i -= (i & -i);
		}
		return res;
	}
	ll query(int i, int j)
	{
		if (i > j)
			return 0;
		return query(j) - query(i - 1);
	}
};


int n, m;
int a[N], cost[N], b[N];
map<int, int> idx;

int main() {
	GO;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> cost[i];
	BIT bit(m + 1);
	for (int i = 1; i <= m; i++)
	{
		cin >> b[i];
		idx[b[i]] = i;
		bit.upd(i, i, -INF);
	}
	ll sum = 0;
	ll ALL = 0;
	int k = 0;
	for (int i = 1; i <= n; i++) {
		ALL += cost[i];
		int x = a[i];
		int j = (idx.count(x) ? idx[x] : -1);
		if (j == -1 || bit.query(j - 1) == -INF) {
			if (cost[i] > 0)
				sum += cost[i];
			continue;
		}
		ll dp = bit.query(j - 1) + cost[i];
		k = max(j, k);
		if (cost[i] > 0)
			bit.upd(1, k, cost[i]);
		ll cur = bit.query(j);
		if (dp > cur)
			bit.upd(j, j, dp - cur);
	}
	cout << ALL - (sum + bit.query(m)) << '\n';
	return 0;
}
Copy
Always with Me, Always with You Oxygen
GNU G++17
616 ms
23.8 MB
Accepted