Submission #5906065

---

Source Code Expand

#include <bits/stdc++.h>

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
template<typename T> inline void swap(T& a, T& b) {T tmp = a; a = b; b = tmp;}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


int N;
int a[300000];
ll A[100001], B[100001];
priority_queue<int, vector<int>, greater<int> > L;
priority_queue<int, vector<int>, less<int> > R;

signed main(){
    in(N);
    REP(i, 3 * N) in(a[i]);
    REP(i, N){
        L.push(a[i]);
    }
    REP(i, N){
        R.push(a[i + 2 * N]);
    }
    A[0] = accumulate(a, a + N, 0LL);
    B[N] = accumulate(a + 2 * N, a + 3 * N, 0LL);
    REP(i, N){
        L.push(a[i + N]);
        A[i + 1] += A[i] + a[i + N] - L.top();
        L.pop();
    }
    REP(i, N){
        R.push(a[2 * N - 1 - i]);
        B[N - i - 1] += B[N - i] + a[2 * N - 1 - i] - R.top();
        R.pop();
    }
    ll m = A[0] - B[0];
    FOR(i, 1, N + 1) m = max(m, A[i] - B[i]);
    PRINT(m);
    return 0;
}

Submission Info

Judge Result