Submission #3015850

---

Source Code Expand

#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>

using namespace std;

long long MOD = 1000000007;

int n;
long long a[300005];
long long ma[300005];
long long mi[300005];

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

  long long total = 0LL;
  for(int i=0;i<n;i++) total+=a[i];
  ma[n-1] = total;
  priority_queue<long long> pqma;
  for(int i=0;i<n;i++) pqma.push(-a[i]);
  for(int i=n;i<2*n;i++){
    long long tmp = -pqma.top();
    if(tmp < a[i]){
      pqma.pop();
      pqma.push(-a[i]);
      total -= tmp;
      total += a[i];
    }
    ma[i] = total;
  }

  total = 0LL;
  for(int i=3*n-1;i>=2*n;i--) total += a[i];
  mi[2*n] = total;
  priority_queue<long long> pqmi;
  for(int i=3*n-1;i>=2*n;i--) pqmi.push(a[i]);
  for(int i=2*n-1;i>=n;i--){
    long long tmp = pqmi.top();
    if(tmp > a[i]){
      pqmi.pop();
      pqmi.push(a[i]);
      total -= tmp;
      total += a[i];
    }
    mi[i] = total;
  }

  long long ans = ma[n-1]-mi[n];
  for(int i=n+1;i<=2*n;i++){
    ans = max(ans, ma[i-1]-mi[i]);
  }

  //for(int i=0;i<3*n;i++)cout<<a[i]<<" ";cout<<endl;
  //for(int i=0;i<3*n;i++)cout<<ma[i]<<" ";cout<<endl;
  //for(int i=0;i<3*n;i++)cout<<mi[i]<<" ";cout<<endl;
  cout<<ans<<endl;

  return 0;
}

Submission Info

Judge Result