记录编号	162742	评测结果	AAAAAAAA
题目名称	[POI 1999][SPOJ 199] 空心长方体	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2015-05-19 15:51:50	内存使用	0.58 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define N 5010
#define LL long long

using namespace std;

void file(){
	freopen("emptycuboids.in","r",stdin);
	freopen("emptycuboids.out","w",stdout);
}

inline int min(const int &a,const int &b){if(a<b) return a;return b;}

struct node{
	LL x,y,z;
	void scan(){
		scanf("%lld%lld%lld",&x,&y,&z);
	}
}a[N],ansv;

int n,tot0,tot1,vt[N];
LL a0[N],ans,a1[N];
vector<int> v[N];

void addin(node tmp){
	int t=lower_bound(a1+1,a1+tot1+1,tmp.x)-a1;
	for(int i=t;i<=tot1;i++) vt[i]=min(vt[i],tmp.y);
}

void ask(LL h){
	for(int i=1;i<=tot1;i++)
		if(a1[i]*vt[i-1]*h>ans){
			ans=a1[i]*vt[i-1]*h;
			ansv=(node){a1[i],vt[i-1],h};
		}
}

int main(){
	file();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) a[i].scan();
	for(int i=1;i<=n;i++){
		a0[++a0[0]]=a[i].z;
		a1[++a1[0]]=a[i].x;
	}
	sort(a1+1,a1+a1[0]+1);
	a1[++a1[0]]=1000000;
	sort(a0+1,a0+a0[0]+1);
	tot0=tot1=1;
	for(int i=2;i<=a0[0];i++)
		if(a0[i]!=a0[i-1]) a0[++tot0]=a0[i];
	for(int i=2;i<=a1[0];i++)
		if(a1[i]!=a1[i-1]) a1[++tot1]=a1[i];
	for(int i=1;i<=n;i++) v[lower_bound(a0+1,a0+tot0+1,a[i].z)-a0].push_back(i);
	for(int i=0;i<=tot1;i++) vt[i]=1000000;
	for(int h=1;h<=tot0;h++){
		ask(a0[h]);
		for(int i=v[h].size()-1;~i;i--){
			int x=v[h][i];
			addin(a[x]);
		}
	}
	ask(1000000);
	printf("%lld\n",ansv.x*ansv.y*ansv.z);
	return 0;
}