Submission #1518377

---

Source Code Expand

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

#define maxn 100002
#define FOR(i, l, r) for (int i=l; i<=r; ++i)
#define FORD(i, r, l) for (int i=r; i>=l; --i)
#define REP(i, r) for (int i=0; i<(int)r; ++i)
#define REPD(i, r) for (int i=(int)r-1; i>=0; --i)
#define fi first
#define se second
#define mk make_pair
#define nil NULL
#define y0 __y0
#define y1 __y1
#define x0 __x0
#define x1 __x1
#define next __next
#define sz size
#define Debug(X) {cerr << #X << " = " << X << '\n';}
#define PR(A, n) {cerr << #A << " = "; FOR(i, 1, n) cerr << A[i] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; REP(i, n) cerr << A[i] << ' '; cerr << '\n';}
typedef long long ll;
typedef double db;
typedef pair<db, db> dd;
typedef pair<int, int> ii;
typedef vector<int> vi;
const ll inf = 1e18;
template<class T> int getbit(T x, int pos) {return (x>>(pos-1)) & 1;}
template<class T> void turn_on(T &x, int pos) {x = x | ((T)1<<(pos-1));}
template<class T> void turn_off(T &x, int pos) {x = x & ~((T)1<<(pos-1));}
template<class T> T sqr(T a) {return a*a;}

int n, a[maxn];
ll ps[maxn], Left[maxn], Right[maxn];
priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    //freopen("num3N.inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i, 1, 3*n) cin >> a[i];
    ll s = 0;
    FOR(i, 1, 3*n) {
        if (int(pq.sz())<n) {
            s += a[i];
            pq.push(a[i]);
        }
        else if (pq.top()<a[i]) {
            s -= pq.top(); pq.pop();
            s += a[i]; pq.push(a[i]);
        }
        Left[i] = s;
    }
    s = 0;
    while (pq.sz()) pq.pop();
    FORD(i, 3*n, 1) {
        if (int(pq.sz())<n) {
            s -= a[i];
            pq.push(-a[i]);
        }
        else if (pq.top()<-a[i]) {
            s -= pq.top(); pq.pop();
            s -= a[i]; pq.push(-a[i]);
        }
        Right[i] = s;
    }
    ll res = -inf;
    FOR(i, n, 2*n) {
        res = max(res, Left[i] + Right[i+1]);
    }
    cout << res;
}

Submission Info

Judge Result