Submission #3772473

---

Source Code Expand

#include<bits/stdc++.h>


#include <bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define inf 10000000000000000
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;


int main(){


	int n;
	cin>>n;
	ll	 arr[3*n];

	ll csum=0;


	for(int i=0;i<3*n;i++){

		cin>>arr[i];
	}	
	ll l_sum[3*n+1],r_sum[3*n+1];

	priority_queue<int> pq;
	priority_queue<int ,vector<int>,greater<int> > min_pq;

	for(int i=0;i<3*n;i++){
		min_pq.push(arr[i]);
		csum+=arr[i];

		if(min_pq.size()>n){
			csum-=min_pq.top();min_pq.pop();

		}
		if(min_pq.size()==n) l_sum[i]=csum;
		else{
			l_sum[i]=-inf;
		}

	}
	csum=0;
	for(int i=3*n-1;i>=0;i--){
		pq.push(arr[i]);
		csum+=arr[i];

		if(pq.size()>n){
			csum-=pq.top();pq.pop();
		}
		if(pq.size()==n) r_sum[i]=csum; 
		else{
			r_sum[i]=inf;
		}
	}


	ll ans=-inf;

	for(int i=0;i<2*n+1;i++){
		// cout<<l_sum[i]<<"	"<<r_sum[i]<<endl;
		ans=max(ans,l_sum[i]-r_sum[i+1]);
	}
	cout<<ans<<endl;

	return 0;

}

Submission Info

Judge Result