Submission #1691789

---

Source Code Expand

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;

#define INF 2147483647
#define LINF 9223372036854775807
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<ll, int> P;

int n;
ll a[3*100000];
vector<ll> mi;
vector<P> ma;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>n;
	REP(i,3*n) {
		cin>>a[i];
		if(i<n) mi.push_back(a[i]);
		else ma.push_back(P(a[i],i));
	}
	sort(ALL(ma)); sort(mi.rbegin(),mi.rend());

	ll ans=-LINF,l=0,r=0;
	ll lx=mi[n-1];
	vector<ll> rx;
	bool lflg=false,rflg=false;

	REP(i,n) l+=mi[i];
	REP(i,n) {
		r+=ma[i].first;
		rx.push_back(ma[i].second);
	}

	FOR(idx,n,2*n+1) {
		if(lflg) {
			l-=lx,lflg=false,l+=a[idx-1],lx=min(lx,a[idx-1]);
		}
		if(rflg) {
			r+=ma[n-1].first,rflg=false;
		}
		ans=max(ans,l-r);
		auto tmp=find(ALL(rx),idx);
		if(tmp!=rx.end()) {
			r-=a[idx],rflg=true;
			rx.erase(tmp);
		}

		if(a[idx]>lx) lflg=true;

		auto itr=find(ALL(ma),P(a[idx],idx));
		ma.erase(itr);
	}
	cout<<ans<<endl;

	return 0;
}

Submission Info

Judge Result