Submission #1481200

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define val first
#define pos second
using namespace std;
typedef pair<int,int> P;

inline int read(){
	char ch = getchar(); int x = 0; while (ch < '0' || '9' < ch) ch = getchar();
	while ('0' <= ch && ch <= '9') { x = x*10 + ch-'0'; ch = getchar(); } return x;
}
const int maxn = 300009;
int a[maxn], f[maxn], n;
priority_queue<int, vector<int>, greater<int> > L;
priority_queue<P, vector<P>, greater<P> > R;
long long Lsum, Rsum, best;
P tmp;

int main(){
	n = read();
	for (int i=1; i<=3*n; i++) a[i] = read();
	for (int i=1; i<=n; i++) { Lsum += a[i]; L.push(a[i]); }
	for (int i=n+1; i<=3*n; i++) R.push(make_pair(a[i], i));
	for (int i=1; i<=n; i++){
		tmp = R.top(); R.pop();
		Rsum += tmp.val; f[tmp.pos] = 1;
	}
	best = Lsum - Rsum;
	for (int i=n+1; i<=2*n; i++){
		if (L.top() < a[i]){ Lsum += a[i]-L.top(); L.pop(); L.push(a[i]); }
		if (f[i]){
			Rsum -= a[i];
			while (1){
				tmp = R.top(); R.pop();
				if (tmp.pos <= i) continue;
				Rsum += tmp.val; f[tmp.pos] = 1;
				break;
			}
		}
		best = max(best, Lsum-Rsum);
	}
	printf("%lld\n", best);
	return 0;
}

Submission Info

Judge Result