Submission #2126251

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<ll, P> E;
#define cost first
#define from second.first
#define to second.second
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

int main(void){
	int n,i;
	ll a,m[123456],mx[123456],mn[123456],ans=-INFLL;
	priority_queue<ll, vector<ll>, greater<ll> > pqf;
	priority_queue<ll> pql;
	mx[0] = 0ll;
	mx[n] = 0ll;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a;
		pqf.push(a);
		mx[0] += a;
	}
	for(i=0; i<n; ++i){
		cin >> m[i];
	}
	for(i=0; i<n; ++i){
		cin >> a;
		pql.push(a);
		mn[n] += a;
	}
	for(i=0; i<n; ++i){
		mx[i+1] = mx[i];
		if(m[i] > pqf.top()){
			mx[i+1] -= pqf.top();
			pqf.pop();
			mx[i+1] += m[i];
			pqf.push(m[i]);
		}
	}
	for(i=(n-1); i>=0; --i){
		mn[i] = mn[i+1];
		if(m[i] < pql.top()){
			mn[i] -= pql.top();
			pql.pop();
			mn[i] += m[i];
			pql.push(m[i]);
		}
	}
	for(i=0; i<=n; ++i){
		ans = max(ans,mx[i]-mn[i]);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result