比赛 2008haoi模拟训练3 评测结果 AAAAAAAAAT
题目名称 阶梯教室设备利用 最终得分 90
用户昵称 BYVoid 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2008-04-24 10:48:28
显示代码纯文本
#include <iostream>
#include <fstream>

using namespace std;

typedef struct
{
	long s,t;
} seg;

ifstream fi("rez.in");
ofstream fo("rez.out");

long n;

seg *q;
long f[30001],a[30001];

inline int cmp(const void *a,const void *b)
{
	return ((seg *)a)->t < ((seg *)b)->t?-1:1;
}

void init()
{
	long i;
	fi >> n;
	q=(seg *)malloc((n+2)*sizeof(seg));
	q++;
	for (i=1;i<=n;i++)
		fi >> q[i].s >> q[i].t;
	qsort(q+1,n,sizeof(seg),cmp);
}

void print()
{
	long M=0,i;
    for (i=n;i>=1;i--)
		if (f[q[i].t]>M)
			M=f[q[i].t];
	fo << M;
	fi.close();
	fo.close();
}

void count()
{
	long i,j;
	f[q[1].t]=q[1].t-q[1].s;
	for (i=1;i<=n;i++)
		a[q[i].t]=-1;
	for (i=2;i<=n;i++)
	{
		j=i-1;
		while (q[j].t>a[q[i].t] && j>=0)
		{
			if (f[q[j].t]+q[i].t-q[i].s>f[q[i].t] && q[i].s >=q[j].t )
			{
				f[q[i].t]=f[q[j].t]+q[i].t-q[i].s;
				a[q[i].t]=q[j].s;
			}
			j--;
		}
	}
}

int main()
{
	init();
	count();
	print();
	return 0;
}