Submission #8419455

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll read(){
	ll w=0;
	bool s=0;
	char c=getchar();
	while(!isdigit(c)){
		s=(c=='-');
		c=getchar();
	}
	while(isdigit(c)){
		w=w*10+c-'0';
		c=getchar();
	}
	return s?-w:w;
}
const int N=1000005;
const ll inf=1e15;
int x,y,z,n;
struct Data{
	ll a,b,c;
	friend bool operator < (Data a,Data b){
		return a.a-a.b>b.a-b.b;
	}
};
Data a[N];
ll sum,ans;
ll f[N],g[N];
struct Heap{
	#define fa (root>>1)
	#define ls (root<<1)
	#define rs (root<<1|1)
	ll h[N<<3];
	int siz;
	void clear(){
		siz=0;
		h[0]=-inf;
	}
	void insert(ll x){
		h[++siz]=x;
		int root=siz;
		while(root){
			if(h[root]<h[fa]){
				swap(h[root],h[fa]);
				root=fa;
			}
			else{
				return;
			}
		}
	}
	void remove(){
		swap(h[1],h[siz]);
		siz--;
		int root=1;
		while(ls<=siz){
			int son=ls;
			if(rs<=siz&&h[rs]<h[ls]){
				son=rs;
			}
			if(h[son]<h[root]){
				swap(h[son],h[root]);
				root=son;
			}
			else{
				return;
			}
		}
	}
	bool empty(){
		return !siz;
	}
	int size(){
		return siz;
	}
	void push(int x){
		insert(x);
	}
	void pop(){
		remove();
	}
	ll top(){
		return h[1];
	}
	#undef fa
	#undef ls
	#undef rs
};
Heap que;
int main(){
	x=read(),y=read(),z=read();
	n=x+y+z;
	ll u,v,w;
	for(int i=1;i<=n;i++){
		u=read(),v=read(),w=read();
		ans+=w;
		a[i]=(Data){u,v,w};
	}
	sort(a+1,a+1+n);
	que.clear();
	sum=0;
	for(int i=1;i<=n;i++){
		ll dt=a[i].a-a[i].c;
		que.push(dt);
		sum+=dt;
		if(que.size()>x){
			dt=que.top();
			que.pop();
			sum-=dt;
		}
		f[i]=sum;
	}
	que.clear();
	sum=0;
	for(int i=n;i>=1;i--){
		ll dt=a[i].b-a[i].c;
		que.push(dt);
		sum+=dt;
		if(que.size()>y){
			dt=que.top();
			que.pop();
			sum-=dt;
		}
		g[i]=sum;
	}
	sum=-inf;
	for(int i=x;i<=n-y;i++){
		sum=max(sum,f[i]+g[i+1]);
	}
	ans+=sum;
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Judge Result