fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define REP(i, a, b) for (int i = a; i <= b; i++)
  5. #define BACK(i, a, b) for (int i = a; i >= b; i--) 
  6. #define MOD 1000000007
  7. #define PI 4 * atan(1)
  8. #define sz(A) (int)A.size()
  9. typedef long long ll;
  10. typedef vector<int> vi;
  11. typedef pair<int, int> pii;
  12. typedef vector<long long> vll;
  13. typedef long int int32;
  14. typedef unsigned long int uint32;
  15. typedef long long int int64;
  16. typedef unsigned long long int uint64;
  17.  
  18. ll a[100002];
  19. void solve(int test){
  20.     int n; cin >> n;
  21.     ll sum_all = 0;
  22.     REP(i,0,n-1){
  23.         cin >> a[i];
  24.         sum_all += a[i];
  25.     }
  26.     multiset<ll> ms_max;
  27.     multiset<ll, greater<ll>> ms_min;
  28.     ms_max.insert(max(a[0], a[1]));
  29.     ms_min.insert(min(a[0], a[1]));
  30.     for(int i=2; i <n; i+= 2){
  31.         auto mn = ms_max.begin();
  32.         if(*mn < min(a[i], a[i+1])){
  33.             ms_max.erase(mn);
  34.             ms_max.insert(a[i]);
  35.             ms_max.insert(a[i+1]);
  36.         }else{
  37.             ms_max.insert(max(a[i], a[i+1]));
  38.         }
  39.         mn = ms_min.begin();
  40.         if(*mn > max(a[i], a[i+1])){
  41.             ms_min.erase(mn);
  42.             ms_min.insert(a[i]);
  43.             ms_min.insert(a[i+1]);
  44.         }
  45.         else{
  46.             ms_min.insert(min(a[i], a[i+1]));
  47.         }
  48.     }
  49.     ll sum_max = 0;
  50.     ll sum_min = 0;
  51.     for(ll x: ms_max){
  52.         sum_max += x;
  53.     }
  54.     for(ll x: ms_min){
  55.         sum_min += x;
  56.     }
  57.     ll res = max(2 * sum_max - sum_all, sum_all - 2 * sum_min);
  58.     cout << res << "\n";
  59. }   
  60. int main(){
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(NULL);
  63.     cout.tie(NULL);
  64.     int typetest = 0;
  65.     if (typetest){
  66.         int t;
  67.         cin >> t;
  68.         cin.ignore();
  69.         REP(i, 1, t){
  70.             solve(i);
  71.         }
  72.     }
  73.     else solve(0);
  74. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
4
6 2 1 4
stdout
copy 
7
https://ideone.com/4lZTqn
language:
C++14 (gcc 8.3)
created:
282 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!