记录编号	266549	评测结果	AAAAAAAAAA
题目名称	[POI 1997] 阶梯教室设备利用	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.391 s
提交时间	2016-06-07 23:40:02	内存使用	0.22 MiB

#include<stdio.h>
#include<stdlib.h>
struct rez{
	int st,en,ti;
}r[10010]={0,0};
int f[10010]={0};
int cmp(const void*a,const void*b)
{
	struct rez *c=(rez*)a;
	struct rez *d=(rez*)b;
	if(c->st!=d->st) return c->st-d->st;
	return c->en-d->en;
}
int max(int x,int y){return x>y?x:y;}
int _521()
{
	freopen("rez.in","r",stdin);
	freopen("rez.out","w",stdout);
	int n,i,j,Max=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	  scanf("%d%d",&r[i].st,&r[i].en),r[i].ti=r[i].en-r[i].st;
	qsort(r+1,n,sizeof(rez),cmp);
	f[1]=r[1].ti;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		if(r[i].st>=r[i-j].en)
		  f[i]=max(f[i],f[i-j]+r[i].ti);
		Max=max(Max,f[i]);
	}
	printf("%d\n",Max);
	return 0;
}
int _520=_521();
int main(){;}