Submission #3012272

---

Source Code Expand

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=1000000000000;/*10^12*/
#define rep(i,l,r) for(ll i=l;i<=r;i++)
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}


//////////////////////////////////////

int main(){
    int n;cin>>n;
    int a[3*n];rep(i,0,3*n-1)cin>>a[i];
    priority_queue<ll,vector<ll>,greater<ll>>q;
    ll dp[2][3*n];memset(dp,0,sizeof(dp));
    ll sum=0;
    rep(i,0,n-1){
        sum+=a[i];
        q.push(a[i]);
    }
    dp[0][n-1]=sum;
    rep(i,n,2*n-1){
        sum+=a[i];
        q.push(a[i]);
        ll t=q.top();q.pop();
        sum-=t;
        dp[0][i]=sum;
    }
    sum=0;
    priority_queue<ll>p;
    for(int i=3*n-1;i>=2*n;i--){
        sum+=a[i];
        p.push(a[i]);
    }
    dp[1][2*n]=sum;
    for(int i=2*n-1;i>=n;i--){
        sum+=a[i];
        p.push(a[i]);
        ll t=p.top();p.pop();
        sum-=t;
        dp[1][i]=sum;
    }
    ll ans=dp[0][n-1]-dp[1][n];
    rep(i,n,2*n-1){
        ans=max(ans,dp[0][i]-dp[1][i+1]);
    }
    
 /*   rep(i,0,1){
        rep(j,0,3*n-1){
            cout<<dp[i][j]<<" ";
        }cout<<endl;
    }*/
    cout<<ans<<endl;
    
    return 0;
}

Submission Info

Judge Result