Cod sursa(job #487518)

Utilizator bog29Antohi Bogdan bog29 Data 25 septembrie 2010 14:11:59
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define dmax 200004
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

int n;
long int sol[dmax],mx;

vector<long int>v;
vector<long int>::iterator it;

struct metal
{	long int x;
	long int y;
	long int dif;
}	k[dmax];

bool sf(const metal& a , const metal& b)
{	if(a.y != b.y)
		return a.y < b.y;
	return a.x <= b.x;
}	

void norm()
{	int i;

	sort(v.begin(),v.end());
	unique(v.begin(),v.end()+1);

	for(i=1;i<=n;i++)
	{	it=lower_bound(v.begin(),v.end(),k[i].x);
		k[i].x = it-v.begin();
		it=lower_bound(v.begin(),v.end(),k[i].y);
		k[i].y = it-v.begin();
		mx=max(mx,k[i].y);
	}
}	

int main()
{	int i,j;
	in>>n;
	for(i=1;i<=n;i++)
	{	in>>k[i].x>>k[i].y;
		k[i].dif=k[i].y-k[i].x;
		v.push_back(k[i].x);
		v.push_back(k[i].y);
	}	
	in.close();
	
	norm();
	sort(k+1,k+n+1,sf);
	
	sol[1]=k[1].dif;
	j=1;
	for(i=0;i<=mx;i++)
	{	sol[i]=sol[i-1];
		
		while(k[j].y <= i && j<n)
		{	sol[i]=max(sol[i],sol[k[j].x]+k[j].dif);	
			j++;
		}
	}	
	
	out<<sol[mx];
	out.close();
	return 0;
}