Cod sursa(job #520206)

Utilizator loginLogin Iustin Anca login Data 7 ianuarie 2011 15:28:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define max(a,b) a>b?a:b
using namespace std;
struct nod{
	int a, b, x, y;
	nod(){}
	nod(int A, int B, int X, int Y){
		a=A;b=B;x=X;y=Y;}
	};
int n, B[2*DIM], p[2*DIM], tmp;
nod v[DIM];

bool inline cmp(int i, int j)
{
	if (i%2)i=v[i/2].a;
	else i=v[i/2].b;
	if (j%2)j=v[j/2].a;
	else j=v[j/2].b;
	if (i<j)return true;
	return false;
}

void read ()
{
	ifstream fin ("heavymetal.in");
	fin>>n;
	int a, b;
	for(int i=1;i<=n;++i)
	{
		fin>>a>>b;
		v[i]=nod(a, b, 0, 0);
		p[2*i-1]=2*i-1;
		p[2*i]=2*i;
	}
	sort(p+1, p+2*n+1, cmp);
}

void solve ()
{
	int u=0, a, b;
	for(int i=1;i<=2*n;++i)
	{
		if (p[i]%2)a=v[p[i]/2].a;
		else a=v[p[i]/2].b;
		if ((p[i-1])%2)b=v[(p[i-1])/2].a;
		else b=v[(p[i-1])/2].b;
		if (a!=b)++tmp;
		if (p[i]%2)
			v[p[i]/2].x=tmp;
		else
		{
			v[p[i]/2].y=tmp;
			for(int j=u+1;j<tmp;++j)
				B[j]=B[j-1];
			B[tmp]=max(B[tmp-1],B[tmp]);
			B[tmp]=max(B[tmp],B[v[p[i]/2].x]+v[p[i]/2].b-v[p[i]/2].a);
			u=tmp;
		}
	}
}

int main ()
{
	read ();
	solve ();
	ofstream fout ("heavymetal.out");
	fout<<B[tmp];
	return 0;
}