Description
有X+Y+Z个三元组(x[i],y[i],z[i])，请你从每个三元组中挑数，并满足以下条件：
1、每个三元组中可以且仅可以选择一个数（即x[i],y[i],z[i]中的一个）
2、选择x[i]的三元组个数恰好为X
3、选择y[i]的三元组个数恰好为Y
4、选择z[i]的三元组个数恰好为Z问选出的数的和最大是多少
问选出的数的和最大是多少
Input
第一行三个非负整数分别表示X,Y,Z
接下来X+Y+Z行每行三个非负整数描述一个三元组(x[i],y[i],z[i])
Output
一行一个整数表示选出的数的和最大是多少
Sample Input
输入1：
1 2 1
2 4 4
3 2 1
7 6 7
5 2 3
输入2：
3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2
Sample Output
输出1：
18
输出2：
110
Data Constraint
对于10%的数据满足，1<=X+Y+Z<=15
对于30%的数据满足，1<=X+Y+Z<=100
对于另外10%的数据满足，X=0
对于另外20%的数据满足，所有三元组中的x[i]=0
对于另外20%的数据满足，1<=X+Y+Z<=100000
对于100%的数据满足，1<=X+Y+Z<=500000，0<=x[i],y[i],z[i]<=500000
赛时
30分直接秒了。
想了想10%，突然想到一个神奇的方法，直接全部选y，然后把y-z排序，选最小的z个即可。
完美地解决。
然后想了想剩下的20%，傻乎乎地以为像10%一样贪心即可。
然而似乎挂了。
还是太菜了。
题解
题解的方法看不懂？
倒是网上有一个神奇的堆的做法。
利用的是差分思想。
首先把所有的y-x，z-x，于是三元组就变成另外20%的情况了。
这20分这么做？
由于有些组可以不用，就有点头疼了。
但是！堆的某些性质很有用！！
首先同样按照y-z排序。
设(ansy_{[i]})表示在前i个里面，选出了y个y的最大值。
设(ansz_{[i]})表示在后i个里面，选出了z个z的最大值。
利用堆来维护这两个东东，就可以完美解决~
最后答案+(sum x)即可
标程
话说带log比没带log跑得还快好多，自打的堆就是吼。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn=500010;
struct node{
long long x,y,z;
};
node a[maxn];
long long X,Y,Z,x[maxn],y[maxn],z[maxn],tot,d[maxn];
long long ansy[maxn],ansz[maxn],answer,sum;
__attribute__((optimize("-O3")))
inline int read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
__attribute__((optimize("-O3")))
void qsort(int l,int r)
{
int i=l;int j=r;
int m=a[(i+j)/2].x;
while (i<=j)
{
while (a[i].x>m) i++;
while (a[j].x<m) j--;
if (i<=j)
{
swap(a[i],a[j]);
i++;j--;
}
}
if (l<j) qsort(l,j);
if (r>i) qsort(i,r);
}
__attribute__((optimize("-O3")))
void up(int x)
{
while (x>1 && d[x/2]>d[x])
{
swap(d[x/2],d[x]);
x/=2;
}
}
__attribute__((optimize("-O3")))
void down(int x)
{
int mb=0;
while (x<tot)
{
if (x*2<=tot)
{
if (x*2+1<=tot)
{
if (d[x*2]>d[x*2+1]) mb=x*2+1; else mb=x*2;
}
else
{
mb=x*2;
}
}
else break;
if (d[x]>d[mb])
{
swap(d[x],d[mb]);x=mb;
}
else break;
}
}
int main()
{
freopen("triple.in","r",stdin);
freopen("triple.out","w",stdout);
scanf("%lld%lld%lld",&X,&Y,&Z);
for (int i=1;i<=X+Y+Z;i++)
{
x[i]=read();y[i]=read();z[i]=read();
sum+=x[i];
a[i].y=y[i]-x[i];
a[i].z=z[i]-x[i];
a[i].x=a[i].y-a[i].z;
}
qsort(1,X+Y+Z);
tot=0;
for (int i=1;i<=Y;i++)
{
d[++tot]=a[i].y;
up(tot);
ansy[Y]+=a[i].y;
}
int n=X+Y+Z;
for (int i=Y+1;i<=n;i++)
{
ansy[i]=ansy[i-1];
if (d[1]<a[i].y)
{
ansy[i]=ansy[i]-d[1]+a[i].y;
d[1]=a[i].y;
down(1);
}
}
tot=0;
for (int i=n;i>=n-Z+1;i--)
{
d[++tot]=a[i].z;
up(tot);
ansz[n-Z+1]+=a[i].z;
}
for (int i=n-Z;i>=1;i--)
{
ansz[i]=ansz[i+1];
if (d[1]<a[i].z)
{
ansz[i]=ansz[i]-d[1]+a[i].z;
d[1]=a[i].z;
down(1);
}
}
answer=0;
for (int i=Y;i<=n-Z;i++)
{
answer=max(answer,sum+ansy[i]+ansz[i+1]);
}
printf("%lld
",answer);
}