fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e6 + 42, logn = 23;
  6. int c[maxn], v[maxn], dp[maxn];
  7. int last_v[logn];
  8. vector<int> last_c[maxn];
  9.  
  10. signed main()
  11. {
  12.     ios::sync_with_stdio(0);
  13.     cin.tie(0);
  14.     int n;
  15.     cin >> n;
  16.     for(int i = 0; i < n; i++)
  17.         cin >> c[i];
  18.     for(int i = 0; i < n; i++)
  19.         cin >> v[i];
  20.     int st = 0;
  21.     for(int i = 0; i < n; i++)
  22.     {
  23.         last_c[c[i]].push_back(i + 1);
  24.         if(last_c[c[i]].size() >= 2)
  25.             st = max(st, last_c[c[i]][last_c[c[i]].size() - 2]);
  26.         dp[i + 1] = dp[i] + v[i];
  27.         pair<int, int> tv[logn];
  28.         for(int j = 0; j < logn; j++)
  29.             tv[j] = {last_v[j], j};
  30.         sort(tv, tv + logn, greater<pair<int, int>>());
  31.         int cur = v[i];
  32.         for(int j = 0; tv[j].first; j++)
  33.         {
  34.             cur |= 1 << tv[j].second;
  35.             if(tv[j].first == tv[j + 1].first)
  36.                 continue;
  37.             dp[i + 1] = min(dp[i + 1], dp[max(st, tv[j + 1].first)] + cur);
  38.         }
  39.         for(int z = 0; z < logn; z++)
  40.             if((v[i] >> z) & 1)
  41.                 last_v[z] = i + 1;
  42.     }
  43.     cout << dp[n] << endl;
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 50384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/15OQ3J
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!