比赛 |
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;
}