fork(2) download
  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
stdin
Standard input is empty
stdout
Standard output is empty