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
| #include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
inline char nc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
int res=0,f=1;char ch=nc();
while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
return res*f;
}
const int maxn=1000005,maxs=4000005;
int n,m,f[maxn],w[maxn],nxt[maxn],lst[maxn];
ll a[maxn]; bool vis[maxn];
ll mx[maxs],ad[maxs];
#define ls x<<1
#define rs x<<1|1
inline void pushup(int x) {mx[x]=max(mx[ls],mx[rs]);}
inline void addad(int x,ll w) {mx[x]+=w;ad[x]+=w;}
inline void pushdown(int x){
if (ad[x]) addad(ls,ad[x]),addad(rs,ad[x]),ad[x]=0;
}
void build(int x,int l,int r){
if (l==r) {mx[x]=a[l];return;}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(x);
}
void ist(int x,int l,int r,int ql,int qr,ll w){
if (ql<=l&&r<=qr) return addad(x,w);
if (qr<l||r<ql) return;
int mid=l+r>>1; pushdown(x);
ist(ls,l,mid,ql,qr,w); ist(rs,mid+1,r,ql,qr,w);
pushup(x);
}
ll qry(int x,int l,int r,int ql,int qr){
if (ql<=l&&r<=qr) return mx[x];
if (qr<l||r<ql) return 0;
int mid=l+r>>1; pushdown(x);
return max(qry(ls,l,mid,ql,qr),qry(rs,mid+1,r,ql,qr));
}
int main(){
n=red(),m=red();
for (int i=1;i<=n;i++) f[i]=red();
for (int i=1;i<=m;i++) w[i]=red(),lst[i]=n+1;
for (int i=n;i;i--){
nxt[i]=lst[f[i]];
lst[f[i]]=i;
}
for (int i=1;i<=n;i++)
if (!vis[f[i]]){
vis[f[i]]=1;
a[i]=w[f[i]];a[nxt[i]]=-w[f[i]];
}
ll ans=0;
for (int i=1;i<=n;i++) a[i]+=a[i-1],ans=max(ans,a[i]);
build(1,1,n);
for (int i=1;i<n;i++){
ist(1,1,n,i,nxt[i]-1,-w[f[i]]);
ist(1,1,n,nxt[i],nxt[nxt[i]]-1,w[f[i]]);
ans=max(ans,qry(1,1,n,i+1,n));
}
printf("%lld",ans);
return 0;
}
|
