Submission #8416466

---

Source Code Expand

/***************************************************************
	File name: b.cpp
	Author: huhao
	Create time: Wed 13 Nov 2019 09:23:26 AM CST
***************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
	int r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=r*10+c-48;
		c=getchar();
	}
	return r*t;
}
#include<queue>
#define i64 long long
const int N=100010;
i64 na,nb,nc,n;
struct piii
{
	i64 a,b,c;
	piii(i64 A=0,i64 B=0,i64 C=0){a=A; b=B; c=C;}
}p[N];
inline i64& Max(i64& a,i64 b){return a<b?a=b:a;}
namespace bf
{
	const int N=110;
	i64 f[N][N][N];
	int main()
	{
		fr(i,0,na) fr(j,0,nb) fr(k,0,nc)
		{
			if(i) Max(f[i][j][k],f[i-1][j][k]+p[i+j+k].a);
			if(j) Max(f[i][j][k],f[i][j-1][k]+p[i+j+k].b);
			if(k) Max(f[i][j][k],f[i][j][k-1]+p[i+j+k].c);
		}
		printf("%lld\n",f[na][nb][nc]);
		return 0;
	}
}
namespace thinking_peach
{
	int cmp(piii a,piii b){return a.a-a.b>b.a-b.b;}
	i64 spre[N],ssuf[N],ans,pre[N],suf[N],d;
	priority_queue<i64> q;
	int main()
	{
		sort(p+1,p+n+1,cmp);
		fr(i,1,n) spre[i]=spre[i-1]+p[i].a;
		fd(i,n,1) ssuf[i]=ssuf[i+1]+p[i].b;
		while(!q.empty()) q.pop();
		d=0;
		fr(i,1,na) q.push(p[i].c-p[i].a);
		fr(i,na+1,n)
		{
			q.push(p[i].c-p[i].a);
			d+=q.top();
			q.pop();
			pre[i]=spre[i]+d;
		}
		while(!q.empty()) q.pop();
		d=0;
		fd(i,n,n-nb+1) q.push(p[i].c-p[i].b);
		fd(i,n-nb,1)
		{
			q.push(p[i].c-p[i].b);
			d+=q.top();
			q.pop();
			suf[i]=ssuf[i]+d;
		}
		pre[na]=spre[na]; suf[n-nb+1]=ssuf[n-nb+1];
		fr(i,na,n-nb) Max(ans,pre[i]+suf[i+1]);
		printf("%lld\n",ans);
		return 0;
	}
}
int main()
{
	na=read(); nb=read(); nc=read(); n=na+nb+nc;
	fr(i,1,n)
	{
		i64 a=read(),b=read(),c=read();
		p[i]=piii(a,b,c);
	}
	return thinking_peach::main();
}

Submission Info

Judge Result