Submission #2122565

---

Source Code Expand

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

using LL = long long;

LL sum(auto& a, auto l, auto r) {
  LL s=0;
  for(auto i=l; i<=r;++i) s+= a[i];
  return s;
}

int main() {
  int N;
  cin >> N;
  vector<LL> A(3*N);
  for(auto& i: A) cin >> i;

  priority_queue<LL, vector<LL>, greater<LL>> l;
  vector<LL> L(3*N), R(3*N);
  L[N-1] = sum(A, 0, N-1);
  for(auto i=0; i<N; ++i) l.emplace(A[i]);
  for(auto i=N; i<2*N; ++i) {
    l.emplace(A[i]);
    L[i] = L[i-1] + A[i] - l.top();
    l.pop();
  }

  priority_queue<LL> r;
  R[2*N] = sum(A, 2*N, 3*N-1);
  for(auto i=2*N; i<3*N; ++i) r.emplace(A[i]);
  for(auto i=2*N-1; N<=i; --i) {
    r.emplace(A[i]);
    R[i] = R[i+1] + A[i] - r.top();
    r.pop();
  }

  LL s=-1e18;
  for(auto i=N-1; i<2*N; ++i) s=max(s, L[i]-R[i+1]);
  cout<<s<<endl;
}

Submission Info

Judge Result