Cod sursa(job #552576)

Utilizator HoriaClementHoriaC HoriaClement Data 12 martie 2011 16:29:51
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.5 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

struct timp
{int x,y;}; 

timp f[100005];
	
bool cmp(timp a,timp b)
{
	return a.y<b.y;
}

int v[100005],n,pas=1;

int main()
{
	in>>n;
	for(int i=1;i<=n;i++)
		in>>f[i].x>>f[i].y;
	sort(f+1,f+n+1,cmp);
	for(int i=1;i<=f[n].y;++i)
	{
		v[i]=v[i-1];
		for(;f[pas].y==i;)
		{
			if(v[i]<v[f[pas].x]+i-f[pas].x)
				v[i]=v[f[pas].x]+i-f[pas].x;
			++pas;
		}
	}
	out<<v[f[n].y];
	return 0;
}