Cod sursa(job #487517)

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

int n,mx,sol[dmax];

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

struct metal
{	int x;
	int y;
	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;
}