fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pb push_back
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int,int> pii;
  9. typedef long double ld;
  10. typedef map<pii,set<pii> >::iterator mapit;
  11. typedef multiset<ll>::iterator setit;
  12.  
  13. const int maxn = 1e5 + 5;
  14. const int maxlog = 20;
  15. const ll mod = 1e9 + 7;
  16. const int sq = 340;
  17. const int inf = 1e9 + 43;
  18. const ld pi = 3.14159265;
  19. int n ;
  20. multiset<int> notused , usedmax ;
  21. int main()
  22. {
  23.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  24.     cin >> n;
  25.     ll ans = 0;
  26.     for(int i = 1 ; i <= n ; i ++ ){
  27.         int x ;
  28.         cin >> x;
  29.         int m1 = inf , m2 = inf;
  30.         if(notused.size() != 0){
  31.             m1 = *notused.begin();
  32.         }
  33.         if(usedmax.size() != 0)
  34.             m2 = *usedmax.begin();
  35.         if(m1 < m2){
  36.             if(x > m1){
  37.                 notused.erase(notused.begin());
  38.                 usedmax.insert(x);
  39.                 ans += (ll) (x - m1);
  40.             }
  41.             else
  42.                 notused.insert(x);
  43.         }
  44.         else{
  45.             if(x > m2){
  46.                 usedmax.erase(usedmax.begin());
  47.                 usedmax.insert(x);
  48.                 notused.insert(m2);
  49.                 ans += (ll) (x - m2);
  50.             }
  51.             else
  52.                 notused.insert(x);
  53.         }
  54.     }
  55.     cout << ans ;
  56.     return 0;
  57. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/giXvIl
language:
C++14 (clang 8.0)
created:
6 years 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!