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
|
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std ;
const int N = 1e6+10 ;
struct {
int add , val ;
} t[N<<2] ;
int cnt , n , m ; int f[N] , w[N] , last[N] ;
struct L {
int num , mvi ;
} g[N] ;
inline int read ( ) {
char ch = getchar ( ) ; int res = 0 ;
while ( ch > '9' || ch < '0' ) ch = getchar ( ) ;
while ( ch >= '0' && ch <= '9' ) res = res * 10 + ch - 48 , ch = getchar ( ) ;
return res ;
}
void spread ( int p ) {
if ( t[p].add ) {
t[p<<1].add += t[p].add ; t[p<<1|1].add += t[p].add ;
t[p<<1].val += t[p].add ; t[p<<1|1].add += t[p].add ; t[p].add = 0 ;
}
}
void change ( int p , int l , int r , int x , int y , int z ) {
if ( x <= l && y >= r ) { t[p].val += z ; t[p].add += z ; return ; }
spread ( p ) ;
int mid = ( l + r ) >> 1 ;
if ( x <= mid ) change ( p << 1 , l , mid , x , y , z ) ;
if ( y > mid ) change ( p << 1 | 1 , mid + 1 , r , x , y , z ) ;
t[p].val = max ( t[p<<1].val , t[p<<1|1].val ) ;
}
int ask ( int p , int l , int r , int x , int y ) {
if ( x <= l && y >= r ) { return t[p].val ; } spread ( p ) ;
int mid = ( l + r ) >> 1 ; int ans = 0 ;
if ( x <= mid ) ans = max ( ans , ask ( p << 1 , l , mid , x , y ) ) ;
if ( y > mid ) ans = max ( ans , ask ( p << 1 | 1 , mid + 1 , r , x , y ) ) ;
t[p].val = max ( t[p<<1].val , t[p<<1|1].val ) ;
}
bool cmp ( L a , L b ) {
if ( a.mvi == b.mvi ) return a.num < b.num ;
return a.mvi < b.mvi ;
}
int main ( ) {
int ans = 0 ;
n = read ( ) , m = read ( ) ;
for ( int i = 1 ; i <= n ; i ++ ) f[i] = g[i].mvi = read ( ) , g[i].num = i ;
for ( int i = 1 ; i <= m ; i ++ ) w[i] = read ( ) ; sort ( g + 1 , g + n + 1 , cmp ) ;
for ( int i = 1 ; i <= n ; i ++ ) { while ( g[i].mvi == g[i+1].mvi ) last[g[i+1].num] = g[i].num , i ++ ; }
for ( int i = 1 ; i <= n ; i ++ ) {
if ( last[i] == 0 ) change ( 1 , 1 , n , 1 , i , w[f[i]] ) ;
if ( last[i]!=0 ) { change ( 1 , 1 , n , last[i] + 1 , i , w[f[i]] ) ; change ( 1 , 1 , n , last[last[i]] + 1 , last[i] , -w[f[i]] ) ; }
ans = max ( ans , ask ( 1 , 1 , n , 1 , n ) ) ;
}
printf ( "%d" , ans ) ;
}
|
近期评论