比赛 |
20110729 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
最后的利益 |
最终得分 |
100 |
用户昵称 |
donny |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-29 10:37:45 |
显示代码纯文本
#include <iostream>
#include <fstream>
using namespace std;
int i,j,k,l,n;
int a[10001][3];
int f[30001];
void Sort(int x,int y)
{
int i,j,k,l;
i=x;
j=y;
k=a[(x+y)/2][2];
do
{
while (a[i][2]<k) i++;
while (a[j][2]>k) j--;
if (i<=j)
{
l=a[i][1];
a[i][1]=a[j][1];
a[j][1]=l;
l=a[i][2];
a[i][2]=a[j][2];
a[j][2]=l;
i++;
j--;
}
}
while (i<=j);
if (i<y) Sort(i,y);
if (x<j) Sort(x,j);
}
int main()
{
ifstream fin("9cwy.in");
ofstream fout("9cwy.out");
fin>>n;
for (i=1;i<=n;i++)
{
fin>>a[i][1];
fin>>a[i][2];
}
Sort(1,n);
f[0]=0;
j=1;
k=0;
for (i=1;i<=30000;i++)
{
f[i]=f[i-1];
while (a[j][2]==i)
{
if (f[a[j][1]]+a[j][2]-a[j][1]>f[i])
f[i]=f[a[j][1]]+a[j][2]-a[j][1];
j++;
}
if (j>n)
{
k=i;
break;
}
}
fout<<f[k]<<endl;
fin.close();
fout.close();
return 0;
}