1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#include <bits/stdc++.h>
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read())
x = (x + (x << 2) << 1) + (c ^ '0');
if (iosig) x = -x;
}
namespace SegmentTree {
const int MAXN = 1000005;
#define long long long
struct Node {
long max, add;
} d[1048576 * 2 + 1];
int M;
inline void maintain(int k) {
d[k].max = std::max(d[k << 1].max, d[k << 1 | 1].max);
}
inline void build(const int n) {
for (M = 1; M < n + 2; M <<= 1);
}
inline void cover(int k, long v) {
d[k].max += v, d[k].add += v;
}
inline void pushDown(int k) {
if (d[k].add && k <= M) {
(k << 1) ? (cover(k << 1, d[k].add), 0) : 0;
(k << 1 | 1) ? (cover(k << 1 | 1, d[k].add), 0) : 0;
d[k].add = 0;
}
}
inline void update(int k) {
static int st[25], top;
for (top = 0; k; k >>= 1) st[++top] = k;
while (top--) pushDown(st[top]);
}
inline void modify(int s, int t, int v) {
register int l = 0, r = 0;
for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
(~s & 1) ? (l ? 0 : (update(l = s ^ 1), 0), cover(s ^ 1, v), 0) : 0;
(t & 1) ? (r ? 0 : (update(r = t ^ 1), 0), cover(t ^ 1, v), 0) : 0;
}
for (l >>= 1; l; l >>= 1) maintain(l);
for (r >>= 1; r; r >>= 1) maintain(r);
}
inline void solve() {
register int n, m;
static int f[MAXN], w[MAXN], next[MAXN], last[MAXN];
read(n), read(m);
for (register int i = 1; i <= n; i++) read(f[i]);
for (register int i = 1; i <= m; i++) read(w[i]);
for (register int i = n; i; i--) next[i] = last[f[i]], last[f[i]] = i;
build(n);
for (register int i = 1; i <= m; i++) {
if (last[i]) {
if (!next[last[i]]) modify(last[i], n, w[i]);
else modify(last[i], next[last[i]] - 1, w[i]);
}
}
register long ans = 0;
for (register int i = 1; i <= n; i++) {
ans = std::max(ans, d[1].max);
register int t = next[i];
if (t) {
modify(i, t - 1, -w[f[i]]);
if (next[t]) modify(t, next[t] - 1, w[f[i]]);
else modify(t, n, w[f[i]]);
} else {
modify(i, n, -w[f[i]]);
}
}
printf("%lld\n", ans);
}
}
int main() {
SegmentTree::solve();
return 0;
}
|
