Submission #6438268

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
	ll x,y,z;
	cin >> x >> y >> z;
	vector<pair<ll,pair<ll,ll> > > v;
	ll sm = 0;
	rep(i,x+y+z){
		ll a,b,c;
		cin >> a >> b >> c;
		sm += c;
		a -= c;
		b -= c;
		v.push_back(MP(b-a,MP(a,b)));
	}
	sort(v.begin(),v.end());
	vector<ll>a(x+y+z),b(x+y+z);
	// cerr << sm << endl;
	// cerr << endl;
	rep(i,x+y+z){
		a[i] = v[i].second.first;
		b[i] = v[i].second.second;
		//cerr << a[i] << " " << b[i] << endl;
	}
	ll n = x+y+z;
	vector<ll>sa(n),sb(n+1);
	priority_queue<ll,vector<ll>,greater<ll> >pq,pq2;
	rep(i,n){
		if(i<x){
			if(i!=0)sa[i] = sa[i-1]+a[i];
			else sa[i] = a[i];
			pq.push(a[i]);
		}else{
			sa[i] = sa[i-1]+a[i];
			pq.push(a[i]);
			ll x = pq.top();
			pq.pop();
			sa[i]-=x;
		}
	}
	for(int i=n-1;i>=0;i--){
		if(i>=n-y){
			sb[i] = sb[i+1]+b[i];
			pq2.push(b[i]);
		}else{
			sb[i] = sb[i+1]+b[i];
			pq2.push(b[i]);
			ll x = pq2.top();
			pq2.pop();
			sb[i]-=x;
		}
	}
	// cerr << endl;
	// rep(i,n)cerr << sa[i] << " ";
	// cerr << endl;
	// rep(i,n)cerr << sb[i] << " ";
	// cerr << endl;

	ll ans = 0;
	for(int i=x-1;i<n-y;i++){
		ans = max(ans,sm+sa[i]+sb[i+1]);
		//cerr << ans <<endl;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result