记录编号	27358	评测结果	AAAAAAAAAAAA
题目名称	最后的利益	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	C++	运行时间	0.149 s
提交时间	2011-09-17 15:16:56	内存使用	1.56 MiB

#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]);
}