matbensch

Boredom Solution

Sep 13th, 2023
727
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int n, m;
  8. vector<int> arr;
  9. vector<long long> dp;
  10. vector<pair<int, long long>> freq;
  11.  
  12. long long sim(int i)
  13. {
  14.     // stop at end of array
  15.     if(i >= m) return 0;
  16.     // return saved values
  17.     if(dp[i] != -1) return dp[i];
  18.     // if we take this item, we have to go to the next item > item+1
  19.     int next = ((i+1 < m) && (freq[i].first + 1 == freq[i+1].first))?i+2:i+1;
  20.     // answer is max(not taking this item, taking this item and getting value)
  21.     return dp[i] = max(sim(i+1), freq[i].first * freq[i].second + sim(next));
  22. }
  23.  
  24. int main()
  25. {
  26.     // read array
  27.     cin>>n;
  28.     arr.resize(n);
  29.    
  30.     // make vector of pairs of items with freqs
  31.     map<int, long long> mfreq;
  32.     for(int i=0;i<n;i++)
  33.     {
  34.         int x; cin>>x;
  35.         mfreq[x]++;
  36.     }
  37.     m = mfreq.size();
  38.     freq = vector<pair<int, long long>>(mfreq.begin(), mfreq.end());
  39.     dp.assign(m, -1);
  40.    
  41.     // calculate max value
  42.     cout << sim(0) << '\n';
  43. }
Advertisement
Add Comment
Please, Sign In to add comment