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