记录编号	162726	评测结果	AAWWWWWW
题目名称	1576.[POI 1999][SPOJ 199] 空心长方体	最终得分	25
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	0.106 s
提交时间	2015-05-19 11:35:39	内存使用	0.58 MiB

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

#define N 5010
#define LL long long
#define INF 0x3f3f3f3f

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];

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+a1[0]+1,tmp.x)-a1;
	for(int i=t;i<=tot1;i++) vt[i]=min(vt[i],tmp.y);
}

LL ask(){
	LL ans=0;
	for(int i=1;i<=tot1;i++)
		ans=max(ans,a1[i]*vt[i]);
	return ans;
}

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].y;
	}
	sort(a1+1,a1+a1[0]+1);
	a1[++a1[0]]=1000000;
	sort(a0+1,a0+a0[0]+1);
	tot0=1;
	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++){
		for(int i=v[h].size()-1;~i;i--){
			int x=v[h][i];
			addin(a[x]);
		}
		ans=max(ans,a0[h]*ask());
	}
	ans=max(ans,ask()*1000000LL);
	printf("%lld\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}