Submission #1869353

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const ll LL_INF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

ll aMax[100005];
ll aMin[100005];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<ll> a(3*N);
  REP(i,3*N){
    cin >> a[i];
  }
  priority_queue<int, vector<int>, greater<int>> maxque;
  priority_queue<int> minque;
  REP(i,N){
    maxque.push(a[i]);
    minque.push(a[i+2*N]);
    aMax[0] += a[i];
    aMin[0] += a[i+2*N];
  }
  REP(i,N){
    int mi = maxque.top();
    maxque.pop();
    aMax[i + 1] = aMax[i] - mi + a[N+i];
    maxque.push(a[N+i]);
    int ma = minque.top();
    minque.pop();
    aMin[i + 1] = aMin[i] - ma + a[2*N-i-1];
    minque.push(a[2*N-i-1]);
  }
  ll ans = -1e16;
  REP(i,N + 1){
    ans = max(ans, aMax[i] - aMin[N - i]);
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result