# CFR 264 C. Choosing Balls ( DP )

Problem - C - Codeforces

The first line contains two integers n and q (1 ≤ n ≤ 1e5; 1 ≤ q ≤ 500). The second line contains n integers: v1, v2, ..., vn (|vi| ≤ 1e5). The third line contains n integers: c1, c2, ..., cn (1 ≤ ci ≤ n).
The following q lines contain the values of the constants a and b for queries. The i-th of these lines contains two integers ai and bi (|ai|, |bi| ≤ 1e5).
TL: 5000 ms
ML: 256 MB

dp[ i ]：當前，以顏色 i 結尾的狀態下，最大可能貢獻總和

O( Q * N ) / O( N )

```int N, Q;
vi V;
vi C;

void init(){
cin >> N >> Q;
V = C = vi( N );
for( int i = 0; i < N; ++i ){
cin >> V[ i ];
}
for( int i = 0; i < N; ++i ){
cin >> C[ i ];
}
}

void solve(){
for( int kase = 0; kase < Q; ++kase ){
int A, B; cin >> A >> B;
vl dp( N + 1, - ( 1LL << 60 ) );
dp[ 0 ] = 0;
int max1_col = 0, max2_col = -1;
for( int i = 0; i < N; ++i ){
if( dp[ C[ i ] ] == - ( 1LL << 60 ) ){
dp[ C[ i ] ] = 1LL * B * V[ i ];
} else{
upmax( dp[ C[ i ] ], dp[ C[ i ] ] + 1LL * A * V[ i ] );
}
assert( max1_col != max2_col );
if( max1_col != C[ i ] ){
upmax( dp[ C[ i ] ], dp[ max1_col ] + 1LL * B * V[ i ] );
} else if( max2_col != -1 ){
upmax( dp[ C[ i ] ], dp[ max2_col ] + 1LL * B * V[ i ] );
}
if( dp[ max1_col ] < dp[ C[ i ] ] ){
max2_col = max1_col;
max1_col = C[ i ];
} else if( max1_col != C[ i ] and ( max2_col == -1 or dp[ max2_col ] < dp[ C[ i ] ] ) ){
max2_col = C[ i ];
}
}
cout << *max_element( dp.begin(), dp.end() ) << endl;
}
}
```