fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;   // needed for tree + PBDS
  6.  
  7. #define pb push_back
  8. #define all(x) x.begin(), x.end()
  9. typedef long long ll;
  10. const ll INF = (ll)1e18;
  11. const ll MOD = 1000000000+7 ;
  12.  
  13. template <class T>
  14. using ordered_set = tree<
  15.     T,
  16.     null_type,
  17.     less<T>,
  18.     rb_tree_tag,
  19.     tree_order_statistics_node_update
  20. >;
  21.  
  22. void solve() {
  23.     ll n ; cin >> n ;
  24.     map < ll , ll  >mp ;
  25.     for (int i = 0 ; i<  n ; i ++ ) {
  26.         ll x ; cin >> x ;mp[x] ++ ;
  27.     }
  28.     ll nb = 0 ;
  29.     set < ll > st;
  30.     ll ans= 0 ;
  31.     for (auto &e : mp ) {
  32.         if (e.second == 1 ) {
  33.             st.insert(e.first) ; continue ;
  34.         }
  35.  
  36.         nb += (e.second/2) ;
  37.         if (e.second %2 == 0 )ans+=(e.second *e.first);
  38.         else {
  39.             ans+=e.first*(e.second-1) ;
  40.             st.insert(e.first ) ;
  41.         }
  42.  
  43.     }
  44.     if (nb == 0 ) {
  45.         cout <<0 << endl ;return;
  46.     }
  47.     if (nb == 1 ) {
  48.         if (st.size() >= 1 ) {
  49.             ll z = *st.rbegin() ;
  50.             //cout <<z <<"e" << ans << endl ;
  51.             if (z >= ans) {
  52.                 cout << 0<< endl ;return;
  53.             }
  54.             ans+=(*st.rbegin()) ;
  55.             cout << ans << endl ;return;
  56.         }
  57.         cout << 0 << endl ;return;
  58.     }
  59.      ///  nb> 1
  60.      if (st.size()  ==  0 ) {
  61.          cout << ans << endl ;return;
  62.      }
  63.     if (st.size() ==  1 ) {
  64.         ll z = *st.begin() ;
  65.         if (z>=ans ) {
  66.             cout << 0  << endl ; return;
  67.         }
  68.         ans+= z ;
  69.  
  70.         cout << ans << endl ; return;
  71.     }
  72.     //auto it = st.upper_bound(ans)
  73.     ans+=(*st.rbegin() + *prev(st.rbegin())) ;
  74.     cout << ans << endl ;
  75.  
  76. }
  77. int main() {
  78.     ios::sync_with_stdio(false);
  79.     cin.tie(nullptr);
  80. #ifndef ONLINE_JUDGE
  81.     freopen("input.txt", "r", stdin);
  82.     freopen("output.txt", "w", stdout);
  83. #endif
  84.     int t = 1 ; cin >> t;
  85.     int maxi = 200000 + 5;
  86.  
  87.     while (t--) solve();
  88.     return 0;
  89. }
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Q8vzOb
language:
C++ (gcc 8.3)
created:
2 days 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!