Cod sursa(job #819026)

Utilizator Kira96Denis Mita Kira96 Data 18 noiembrie 2012 14:01:59
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct el
{
	int A,B;
}v[100001];
int cmp(el a,el b)
{
	if(a.B!=b.B)
	return a.B>b.B;
	else
		return a.A>b.A;
}
int maxi(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int ma,i,m,D[100000000],n,j,OK;
int main ()
{
	f>>n;
	for(i=1;i<=n;++i)
	{
		f>>v[i].A>>v[i].B;
		if(v[i].B>m)
			m=v[i].B;
	}
	sort(v+1,v+n+1,cmp);
	j=n;
	for(i=0;i<=m;++i)
	{
	D[i]=D[i-1];
	if(v[j].B<=i)
		for(;j>=1&&v[j].B<=i;--j)
		{
			if(v[j].B==i)
			{
			D[i]=maxi(D[v[j].A]+(v[j].B-v[j].A),D[i]);
			}
		}
	}
	for(i=1;i<=m;++i)
	{
		if(D[i]>ma)
			ma=D[i];
	}
	g<<ma;
	return 0;
}