fork download
copy 
  1. //#pragma GCC optimize("O3")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC optimize("unroll-loops")
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long
  7. #define db double
  8. #define is insert
  9. #define pb push_back
  10. #define pii pair<int, int>
  11. #define pll pair<long long, long long>
  12. #define X first
  13. #define Y second
  14. #define vi vector<int>
  15. #define vpi vector<pair<int, int>>
  16. #define msi multiset<int>
  17. #define int long long
  18. const int m97 = (int)1e9+7;
  19. const int m83 = 998244353;
  20. const int N = 100005;
  21. const int K = 5;
  22. const int inf = (int)1e18;
  23.  
  24. //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26. int n;
  27. vpi a;
  28. map<int, int> cnt;
  29. bool ok[N];
  30.  
  31. void solve(){
  32. 	cin >> n;
  33. 	int ans = 0;
  34. 	for(int i=1, tmp; i<=n; i++){
  35. 		cin >> tmp;
  36. 		cnt[tmp]++;
  37. 	}
  38. 	for(pii p : cnt){
  39. 		a.pb(p);
  40. 	}
  41. 	reverse(a.begin(), a.end());
  42. 	int sz = a.size();
  43. 	int cur = a[0].Y;
  44. 	for(int i=1; i<sz; i++){
  45. 		int tmp = cur;
  46. 		cur = max(a[i].Y, cur);
  47. 		a[i].Y = max(0ll, a[i].Y - tmp);
  48. 	}
  49. 	for(pii p : a){
  50. //		cout << p.X << " " << p.Y <<"\n";
  51. 		ans += p.X * p.Y;
  52. 	}
  53. 	cout << ans;
  54. }
  55.  
  56. signed main(){
  57. //	freopen("*.INP", "r", stdin);
  58. //    freopen("*.OUT", "w", stdout);
  59.     ios::sync_with_stdio(0);
  60.     cin.tie(0); cout.tie(0);
  61.     int tt = 1; //cin >> tt;
  62.     while(tt--){
  63.     	solve();
  64. 	}
  65. }
  66.  
  67. /*
  68. sample
  69.  
  70. 6
  71. 3 3 4 4 3 6
  72.  
  73. */
  74.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XskA8Q
language:
C++14 (gcc 8.3)
created:
1 day 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!