Advertisement
Guest User

Untitled

a guest
Mar 26th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5.  
  6. ll dp[100010];
  7. ll a[100010];
  8. set<int> vr;
  9. int main()
  10. {
  11. ios_base::sync_with_stdio(false);
  12. cin.tie(NULL);
  13.  
  14. int n;
  15. cin >> n;
  16. for(int i = 0; i < n; i++)
  17. {
  18. int x;
  19. cin >> x;
  20. a[x]++;
  21. vr.insert(x);
  22. }
  23. if(vr.size() == 1)
  24. {
  25. ll x = *vr.begin();
  26. cout << a[x]*x;
  27. return 0;
  28. }
  29. dp[0] = 0;
  30. dp[1]=a[1];
  31. for(int i = 2; i <= n; i++)
  32. {
  33. dp[i] = max(dp[i-1], i*a[i] + dp[i-2]);
  34. }
  35. cout << dp[n];
  36.  
  37. return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement