Submission #64590775

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back 

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int>> pinp;
    
const int N = 300'000;
    
ll n, a[N + 10];
multiset<ll> l[2], r[2];
ll sum[2];

void add(int t, ll x, ll y) {
    r[t].insert(x);
    r[t].insert(y);
    sum[t] += x + y;
    while (r[t].size() > l[t].size()) {
        ll d = *r[t].begin();
        r[t].erase(r[t].lower_bound(d));
        l[t].insert(d);
        sum[t] -= d + d;
    }
    while (*r[t].begin() < *l[t].rbegin()) {
        ll d = *r[t].begin();
        ll d2 = *l[t].rbegin();
        r[t].erase(r[t].lower_bound(d));
        l[t].erase(l[t].lower_bound(d2));
        l[t].insert(d);
        r[t].insert(d2);
        sum[t] -= d + d;
        sum[t] += d2 + d2;
    }
}

void del(int t, ll x) {
    if (l[t].find(x) != l[t].end()) {
        l[t].erase(l[t].lower_bound(x));
        sum[t] += x;
    }
    else {
        r[t].erase(r[t].lower_bound(x));
        sum[t] -= x;
    }
}

void del(int t, ll x, ll y) {
    del(t, x);
    del(t, y);
    while (l[t].size() > r[t].size()) {
        ll d = *l[t].rbegin();
        l[t].erase(l[t].lower_bound(d));
        r[t].insert(d);
        sum[t] += d + d;
    }
    while (r[t].size() > l[t].size()) {
        ll d = *r[t].begin();
        r[t].erase(r[t].lower_bound(d));
        l[t].insert(d);
        sum[t] -= d + d;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)    
        cin >> a[i];
    if (n % 2 == 0) {
        sort(a + 1, a + n + 1);
        ll sum = 0;
        for (int i = 1; i <= n / 2; i++)
            sum -= a[i];
        for (int i = n / 2 + 1; i <= n; i++)
            sum += a[i];
        cout << sum;
    }
    else {
        ll mx = 0;
        for (int i = 2; i <= n; i += 2)
            add(0, a[i], a[i + 1]);
        mx = max(mx, sum[0] + sum[1]);
        for (int i = 3; i <= n; i += 2) {
            del(0, a[i - 1], a[i]);
            add(1, a[i - 1], a[i - 2]);
            mx = max(mx, sum[0] + sum[1]);
        }
        cout << mx;
    }
    cout.flush();
    return 0;
}

Submission Info

Judge Result