Submission #1856869

---

Source Code Expand

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

int main(void){

    int n; cin >> n;
    vector<long long> a(3*n);
    for(int i = 0; i < 3*n; i++){
        cin >> a[i];
    }

    long long sum_red = 0, sum_blue = 0;
    priority_queue<long long, vector<long>, greater<long> > pb_red;
    priority_queue<long long> pb_blue;

    //redの表
    for(int i = 0; i < n; i++){
        pb_red.push(a[i]);
        sum_red += a[i];
    }

    long long ans[2][100010];
    ans[0][0] = sum_red;

    for(int i = 1; i <= n; i++){
        sum_red += a[i + n - 1];
        pb_red.push(a[i + n - 1]);
        sum_red -= pb_red.top();
        pb_red.pop();
        ans[0][i] = sum_red;
    }

    //blueの表
    for(int i = 0; i < n; i++){
        pb_blue.push(a[3*n - 1 - i]);
        sum_blue += a[3*n - 1 - i];
    }
    ans[1][n] = sum_blue;

    for(int i = n - 1; i >= 0; i--){
        sum_blue += a[i + n];
        pb_blue.push(a[i + n]);
        sum_blue -= pb_blue.top();
        pb_blue.pop();
        ans[1][i] = sum_blue;
    }

    long long ans_max = ans[0][0] - ans[1][0];
    for(int i = 1; i <= n; i++){
        ans_max = max(ans_max, ans[0][i] - ans[1][i]);
    }

    cout << ans_max << endl;
    return 0;
}

Submission Info

Judge Result