Submission #3780092

---

Source Code Expand

#include <iostream>
#include <queue>

using namespace std;

int main(){
    int a[3*100000];
    long max_sum_l[100000+1], min_sum_r[100000+1];
    long sum_l = 0, sum_r = 0;
    priority_queue<int> que_l, que_r;
    int N;
    cin >> N;
    for(int i = 0; i < 3*N; i++){
        cin >> a[i];
    }
    for(int i = 0; i < N; i++){
        que_l.push(-a[i]);
        sum_l += a[i];
        que_r.push(a[2*N+i]);
        sum_r += a[2*N+i];
    }
    max_sum_l[0] = sum_l;
    min_sum_r[N] = sum_r;
    for(int i = 0; i < N; i++){
        que_l.push(-a[N+i]);
        sum_l += a[N+i];
        sum_l += que_l.top();
        max_sum_l[i+1] = sum_l;
        //cout << que_l.top() << endl;
        que_l.pop();
        que_r.push(a[2*N-i-1]);
        sum_r += a[2*N-i-1];
        sum_r -= que_r.top();
        //cout << que_r.top() << endl;
        que_r.pop();
        min_sum_r[N-i-1] = sum_r;
    }
    long diff_max = -__LONG_MAX__;
    for(int i = 0; i <= N; i++){
        if(max_sum_l[i] - min_sum_r[i] > diff_max){
            diff_max = max_sum_l[i] - min_sum_r[i];
            //cout << i << ' ' << max_sum_l[i] << ' ' << min_sum_r[i] << endl;
        }
    }
    cout << diff_max << endl;
}

Submission Info

Judge Result