Submission #64590585

---

Source Code Expand

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) (x).begin(), (x).end()

struct Split {
  multiset<ll> low, high;
  ll sum_low, sum_high;

  Split() :
      sum_low(0),
      sum_high(0) {}

  ll score() const {
    return sum_high - sum_low;
  }

  void rebalance() {
    if (low.empty() || high.empty())
      return;

    while (true) {
      auto max_low = *(--low.end());
      auto min_high = *high.begin();

      if (max_low <= min_high)
        break;

      low.erase(low.find(max_low));
      sum_low -= max_low;
      high.erase(high.find(min_high));
      sum_high -= min_high;

      low.insert(min_high);
      sum_low += min_high;
      high.insert(max_low);
      sum_high += max_low;
    }
  }

  void add(ll x) {
    if (high.size() < low.size()) {
      high.insert(x);
      sum_high += x;
    } else {
      low.insert(x);
      sum_low += x;
    }

    rebalance();
  }
};

int main() {
#ifndef ONLINE_JUDGE
  freopen("a.txt", "r", stdin);
#endif
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];

  if (n % 2 == 0) {
    Split cur;
    for (ll x: a)
      cur.add(x);
    cout << cur.score() << "\n";
  } else {

    vector<ll> l, r;

    {
      Split cur;
      l.push_back(0);
      for (int i = 0; i < n; ++i) {
        cur.add(a[i]);
        if (i % 2 == 1)
          l.push_back(cur.score());
      }
    }

    {
      Split cur;
      r.push_back(0);
      reverse(all(a));
      for (int i = 0; i < n; ++i) {
        cur.add(a[i]);
        if (i % 2 == 1)
          r.push_back(cur.score());
      }
    }

    ll ans = 0;
    int sz = l.size();
    for (int i = 0; i < sz; ++i)
      ans = max(ans, l[i] + r[sz - 1 - i]);

    cout << ans << "\n";
  }

  return 0;
}

Submission Info

Judge Result