Advertisement
cbgcbgcbg

Untitled

Feb 19th, 2021
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int nax = 1e5 + 5;
  5. ll freq[nax], n, dp[nax];
  6. ll solve(int x){
  7.     if (x == 0) return 0ll;
  8.     if (x == 1) return freq[1];
  9.     if (dp[x] != -1) return dp[x];
  10.     dp[x] = max(solve(x-1), solve(x-2) + freq[x] * x);
  11.     return dp[x];
  12. }
  13. int main() {
  14.     memset(dp,-1,sizeof(dp));
  15.     cin >> n;
  16.     for (int i = 0; i < n; ++i){
  17.         int a;
  18.         cin >> a;
  19.         freq[a]++;
  20.     }
  21.     cout << (solve(100001)) << "\n";
  22.     return 0;
  23. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement