记录编号	205544	评测结果	AAAWWWWWWW
题目名称	不平凡的boss	最终得分	30
用户昵称	前鬼后鬼的守护	是否通过	未通过
代码语言	C++	运行时间	1.418 s
提交时间	2015-11-05 15:53:01	内存使用	1.81 MiB

#include<cstdio>
#include<algorithm>
const int MAXN=100000,D=10;
inline int read(){
	int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x;
}
int n,ans=1<<30;
struct boss{
	int x,y,z;
}bs[MAXN+D];
void init(){
	n=read();
	for(int i=1;i<=n;i++)
		bs[i].x=read(),bs[i].y=read(),bs[i].z=read();
}
void enume(){
	for(int a=0;a<=300;a++)
		for(int b=0;b<=300;b++){
			int c=0;
			for(int i=1;i<=n;i++)
				if(a<bs[i].x&&b<bs[i].y&&bs[i].z>c)
					c=bs[i].z;
			if(a+b+c<ans)
				ans=a+b+c;
		}
}
inline bool comp(boss a,boss b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
int prev[MAXN+D];
void scan(){
	std::sort(bs+1,bs+1+n,comp);int now,p;
	for(now=1;now<=n;now++){
		while(p&&bs[now].x>=bs[p].x&&bs[now].y>=bs[p].y)p=prev[p];
		prev[now]=p;p=now;
	}
	ans=bs[now].x;
	for(now=n;now;now=prev[now])
		if(bs[now].y+bs[prev[now]].x<ans)
			ans=bs[now].y+bs[prev[now]].x;
}
int main(){
	freopen("playwithboss.in","r",stdin);
	freopen("playwithboss.out","w",stdout);
	init();
	if(n<=300)enume();
	else scan();
	printf("%d",ans);
	return 0;
}