Submission #5912477

---

Source Code Expand

#include <bits/stdc++.h>

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

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

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<int> a(3*n);
    for(int i = 0; i < n*3; ++i){
        cin >> a[i];
    }
    priority_queue<int, vector<int>, greater<int>> que1;
    priority_queue<int> que2;
    vector<ll> fst(n+1), snd(n+1);
    for(int i = 0; i < n; ++i){
        fst[0] += a[i];
        que1.push(a[i]);
        snd[n] += a[3*n-1-i];
        que2.push(a[3*n-1-i]);
    }
    for(int i = 1; i <= n; ++i){
        que1.push(a[i+n-1]);
        fst[i] = fst[i-1] + a[i+n-1] - que1.top();
        que1.pop();
        que2.push(a[2*n-i]);
        snd[n-i] = snd[n-i+1] + a[2*n-i] - que2.top();
        que2.pop();
    }
    ll ans = -LLINF;
    for(int i = 0; i <= n; ++i){
        ans = max(ans, fst[i] - snd[i]);
    }
    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result