fork download
copy 
  1. //codeforces.com/problemset/problem/455/A 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef long double lld;
  7. /*
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. using namespace __gnu_pbds;
  11.  
  12. template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  13. // ordered_set.find_by_order(k) returns the iterator to kth element
  14. // ordered_set.order_of_key(k) returns the number of elements strictly less than k 
  15.  
  16. (FOR ORDERED MULTISET "UPPER_BOUND" AND "LOWER_BOUND" ARE REVERSED)
  17. template<class T> using ordered_multiset =tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
  18. // ordered_set.find_by_order(k) returns the iterator to kth element
  19. // ordered_set.order_of_key(k) returns the number of elements strictly less than k 
  20. */
  21. #ifdef LOCALIO
  22.     #define dbg(...) cerr<< __VA_ARGS__;
  23.     #define dbgl(...) cerr<< __VA_ARGS__<<nl;
  24. #else
  25.     #define dbg(...) ;
  26.     #define dbgl(...) ;
  27. #endif
  28. #define fastio ios_base::sync_with_stdio(0); cin.tie(0);
  29. #define all(x) x.begin(),x.end()
  30. #define nl '\n'
  31. #define mp(x,y) make_pair(x,y)
  32. #define ff first
  33. #define ss second
  34. #define pb(x) push_back(x)
  35. #define sz(x) (int)x.size()
  36. #define szl(x) (long long)x.size()
  37.  
  38. // const int mod = 998244353;
  39. const int mod = 1e9+7;
  40.  
  41.  
  42.  
  43. void solve()
  44. {
  45.     int n; cin>>n;
  46.     int arr[n]; for(auto &i:arr) cin>>i;
  47.  
  48.     int freq[100001] = {0};
  49.  
  50.     for(auto i:arr) freq[i]++;
  51.  
  52.     ll dp[100001][2];
  53.  
  54.     dp[1][0] = 0;
  55.     dp[1][1] = freq[1];
  56.  
  57.     for(int i=2; i<=100000; ++i)
  58.     {
  59.         dp[i][1] = dp[i-1][0] + 1LL*i*freq[i];
  60.  
  61.         dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
  62.     }
  63.  
  64.     cout<<max(dp[100000][1],dp[100000][0])<<nl;
  65.  
  66. }
  67.  
  68. signed main() {
  69.     fastio;
  70.     #ifdef LOCALIO
  71.         freopen("error.txt", "w", stderr);
  72.     #endif
  73.     int t=1;
  74.     // cin>>t;
  75.     while(t--)
  76.     {
  77.         solve();
  78.     }
  79. }
Success #stdin #stdout 0.01s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FJZFDh
language:
C++14 (gcc 8.3)
created:
4 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!