fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  5. using namespace std;
  6.  
  7. int const N = 1e5 + 5;
  8. int n, q, color[N], val[N], dp[N]; 
  9.  
  10. void solve(){
  11.     cin >> n >> q;
  12.     for (int i = 0; i < n; i++) cin >> val[i];
  13.     for (int i = 0; i < n; i++) cin >> color[i], color[i]--;
  14.  
  15.     while (q--) {
  16.         int a, b;
  17.         cin >> a >> b;
  18.         int mx1 = 0 , mx2 = 0;
  19.         // int mx1{}, mx2{};
  20.         for (int i = 0; i < n; i++) dp[i] = -1e15;
  21.         for (int i = 0; i < n; i++) {
  22.             if (mx1 == dp[color[i]]) {
  23.                 dp[color[i]] = max(dp[color[i]], dp[color[i]] + a * val[i]);
  24.                 dp[color[i]] = max(dp[color[i]], mx2 + b * val[i]);
  25.                 mx1 = max(mx1, dp[color[i]]);
  26.             } 
  27.             else {
  28.                 dp[color[i]] = max(dp[color[i]], dp[color[i]] + a * val[i]);
  29.                 dp[color[i]] = max(dp[color[i]], mx1 + b * val[i]);
  30.                 mx2 = max(mx2, dp[color[i]]);
  31.  
  32.                 if (mx2 > mx1) swap(mx1, mx2);
  33.             }
  34.         }
  35.  
  36.         cout << mx1 << '\n';
  37.     }
  38. }
  39. signed main() {
  40.     faster();
  41.     int test = 1 ;
  42.     while(test--){
  43.         solve();
  44.     }
  45.  
  46. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6 3
1 -2 3 4 0 -1
1 2 1 2 1 1
5 1
-2 1
1 0
stdout
copy 
20
9
4
https://ideone.com/N9BQet
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!