Submission #3748906

---

Source Code Expand

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


int main(){
    int N;
    cin >> N;
    
    int a[3 * N];
    vector<lint> sum(N + 1);
    
    priority_queue<int> q1, q2;
    
    sum[0] = 0;
    
    for(int i = 0; i < N; ++i){
        cin >> a[i];
        q1.push(-a[i]);
        sum[0] += a[i];
    }
    
    for(int i = N; i < 2 * N; ++i){
        cin >> a[i];
        int temp =  -q1.top();
        if(temp >= a[i]){
            sum[i - N + 1] = sum[i - N];
        } else {
            sum[i - N + 1] = sum[i - N] - temp + a[i];
            q1.pop();
            q1.push(-a[i]);
        }
    }
    
    lint sub = 0;
    for(int i = 2 * N; i < 3 * N; ++i){
        cin >> a[i];
        q2.push(a[i]);
        sub += a[i];
    }
    
    for(int i = 0; i < N + 1; ++i){
        sum[N - i] = sum[N - i] - sub;
        int temp = q2.top();
        if(temp <= a[2 * N - i - 1]){
        } else {
            q2.pop();
            q2.push(a[2 * N - i - 1]);
            sub = sub - temp + a[2 * N - i - 1];
        }
    }
    sort(sum.begin(), sum.end());
    cout << sum[N] << endl;
    
}

Submission Info

Judge Result