Submission #1693439

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000;

int X,Y,Z,n;LL ans,now,C;
struct data {int a,b,c;bool operator < (const data &c) const {return b-a<c.b-c.a;}};
data a[maxn+5];bool vis[maxn+5];
int ss,sb,Hs[maxn+5];pair<int,int> Hb[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc()
{
	static char buf[100000],*l=buf,*r=buf;
	if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
	if (l==r) return EOF;return *l++;
}
inline int readi(int &x)
{
	int tot=0,f=1;char ch=readc(),lst='+';
	while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	if (lst=='-') f=-f;
	while ('0'<=ch&&ch<='9') tot=(tot<<1)+(tot<<3)+ch-48,ch=readc();
	return x=tot*f,Eoln(ch);
}
#define Push_s(x) Hs[++ss]=(x),push_heap(Hs+1,Hs+1+ss)
#define Pop_s() pop_heap(Hs+1,Hs+1+ss--)
#define Push_b(x,ID) Hb[++sb]=mp((x),(ID)),push_heap(Hb+1,Hb+1+sb)
#define Pop_b() pop_heap(Hb+1,Hb+1+sb--)
int main()
{
	readi(X);readi(Y);readi(Z);n=X+Y+Z;
	for (int i=1;i<=n;i++) readi(a[i].a),readi(a[i].b),readi(a[i].c),C+=a[i].c;
	sort(a+1,a+1+n);for (int i=X+1;i<=n;i++) Push_b(a[i].b-a[i].c,i);
	for (int i=1;i<=Y;i++) now+=Hb[1].fr,vis[Hb[1].sc]=true,Pop_b();
	for (int i=1;i<=X;i++) now+=a[i].a-a[i].c,Push_s(a[i].c-a[i].a);ans=now;
	for (int i=X+1;i<=n-Y;i++)
	{
		if (a[i].c-a[i].a<Hs[1]) now+=(LL)Hs[1]+a[i].a-a[i].c,Pop_s(),Push_s(a[i].c-a[i].a);
		if (vis[i])
		{
			while (vis[Hb[1].sc]) Pop_b();vis[Hb[1].sc]=true;Pop_b();
			now+=(LL)Hb[1].fr-a[i].b+a[i].c;
		}
		vis[i]=true;ans=max(ans,now);
	}
	return printf("%lld\n",ans+C),0;
}

Submission Info

Judge Result