fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int MAX_N = 100000;
  5.  
  6. int main() {
  7. 	int n;
  8. 	cin>>n;
  9. 	int maxi = 0;
  10. 	vector<long long> freq(MAX_N + 1, 0);
  11. 	for(int i = 0; i < n; i++){
  12. 		int x;
  13. 		cin>>x;
  14. 		freq[x]++;
  15. 		maxi = max(maxi,x);
  16. 	}
  17. 	vector<long long> dp(maxi + 1, 0);
  18. 	dp[0] = 0;
  19. 	dp[1] = freq[1] * 1;
  20. 	for(int i = 2; i <= maxi; i++){
  21. 		dp[i] = max(dp[i - 1], dp[i - 2] + freq[i] * i);
  22. 	}
  23. 	cout<<dp[maxi]<<endl;
  24. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
9
1 2 1 3 2 2 2 2 3
stdout
copy 
10
https://ideone.com/KlHo7b
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

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!