Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <algorithm>
- using namespace std;
- int n, m;
- vector<int> arr;
- vector<long long> dp;
- vector<pair<int, long long>> freq;
- long long sim(int i)
- {
- // stop at end of array
- if(i >= m) return 0;
- // return saved values
- if(dp[i] != -1) return dp[i];
- // if we take this item, we have to go to the next item > item+1
- int next = ((i+1 < m) && (freq[i].first + 1 == freq[i+1].first))?i+2:i+1;
- // answer is max(not taking this item, taking this item and getting value)
- return dp[i] = max(sim(i+1), freq[i].first * freq[i].second + sim(next));
- }
- int main()
- {
- // read array
- cin>>n;
- arr.resize(n);
- // make vector of pairs of items with freqs
- map<int, long long> mfreq;
- for(int i=0;i<n;i++)
- {
- int x; cin>>x;
- mfreq[x]++;
- }
- m = mfreq.size();
- freq = vector<pair<int, long long>>(mfreq.begin(), mfreq.end());
- dp.assign(m, -1);
- // calculate max value
- cout << sim(0) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment