Submission #1691725

---

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[100000];
bool flg[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;
	FOR(idx,n,2*n+1) {
		l=0,r=0;
		REP(i,n) l+=mi[i];
		REP(i,n) r+=ma[i].first;
		//REP(i,mi.size()) cout<<mi[i]<<' ';
		//cout<<endl;
		//REP(i,ma.size()) cout<<ma[i].first<<' ';
		//cout<<endl;
		//cout<<"l,r "<<l<<' '<<r<<endl<<endl;
		ans=max(ans,l-r);
		auto itr=find(ALL(ma),P(a[idx],idx));
		ma.erase(itr);
		mi.push_back(a[idx]);
		sort(mi.rbegin(),mi.rend());
	}
	cout<<ans<<endl;

	return 0;
}

Submission Info

Judge Result