1 #include <stdio.h> 2 #include <algorithm> 3 using namespace std; 4 int f[1000010], w[1000010] , next[1000010], sign[1000010]; 5 long long tree[4000040],add[4000040], v; 6 int L, R, n, m; 7 void update(int o, int l, int r) 8 { 9 if (L <= l && r <= R)add[o] += v; 10 else { 11 int mid = (l + r) / 2; 12 if (L <= mid) update(o*2, l, mid); 13 if (R > mid) update(o*2+1, mid+1 , r); 14 } 15 tree[o] = l == r ? 0 : max(tree[o*2], tree[o*2+1]); 16 tree[o] += add[o]; 17 } 18 19 int main() 20 { 21 //freopen("1.in", "r", stdin); 22 //freopen("1.out", "w", stdout); 23 scanf("%d %d", &n, &m); 24 for (int i = 1; i <= n; i++)scanf("%d", &f[i]); 25 for (int i = 1; i <= m; i++)scanf("%d", &w[i]); 26 for (int i = n; i >= 1; i--){ 27 if (sign[f[i]]) next[i] = sign[f[i]]; 28 else next[i] = n + 1; 29 sign[f[i]] = i; 30 } 31 for (int i = 1; i <= m; i++){ 32 if (sign[i]) 33 { 34 v = (long long )w[i];L = sign[i];R = next[sign[i]] -1; 35 update(1, 1, n); 36 } 37 } 38 long long ans =0; 39 for (int i = 1; i <= n; i++){ 40 ans = max (ans, tree[1]); 41 int t = next[i]; 42 v = (long long ) -w[f[i]]; L = i; R = next[i] -1; 43 update(1, 1, n); 44 v = -v; L = R; R = next[R + 1] - 1; 45 if (L <= R) 46 update(1, 1, n); 47 } 48 printf("%lld ", ans); 49 }