比赛 |
20110729 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
最后的利益 |
最终得分 |
100 |
用户昵称 |
belong.zmx |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-29 09:17:39 |
显示代码纯文本
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
using namespace std;
int n;
int a[10001][3];
int f[10001];
int c[300001];
int i,j,p;
void sort(int l,int r)
{
int i,j,mid,p;
i=l;
j=r;
mid=a[((l+r)/2)][2];
do
{
while (a[i][2]<mid)
{
i++;
}
while (mid<a[j][2])
{
j=j-1;
}
if (i<=j)
{
p=a[i][1];
a[i][1]=a[j][1];
a[j][1]=p;
p=a[i][2];
a[i][2]=a[j][2];
a[j][2]=p;
i++;
j--;
}
}while (i<=j);
if (l<j) sort(l,j);
if (i<r) sort(i,r);
}
int max(int a,int b)
{
if (a>b)
{
return a;
}
else
{
return b;
}
}
int main()
{
freopen("9cwy.in","r",stdin);
freopen("9cwy.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i][1],&a[i][2]);
if (a[i][1]>a[i][2])
{
p=a[i][1];
a[i][1]=a[i][2];
a[i][2]=p;
}
}
sort(1,n);
for (i=1;i<=n;i++)
{
for (j=a[i][2];j<=(a[i+1][2]-1);j++)
{
c[j]=i;
}
}
for (i=1;i<=n;i++)
{
f[i]=max(f[i-1],f[c[a[i][1]]]+a[i][2]-a[i][1]);
}
printf("%d\n",f[n]);
}