Cod sursa(job #520176)

Utilizator loginLogin Iustin Anca login Data 7 ianuarie 2011 14:43:26
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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;}
	};
struct str{
	int v, i, t;
	str(){}
	str(int V, int I, int T){
		v=V;i=I;t=T;}
	};
int n, b[DIM], p[2*DIM], tmp;
nod v[DIM];
str w[DIM];

bool inline cmp(int i, int j)
{
	if (w[i].v<w[j].v)return true;
	return false;
}

bool inline comp (int i, int j)
{
	if (v[i].b<v[j].b)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);
		w[2*i-1]=str(a, i, 0);
		w[2*i]=str(b, i, 1);
		p[2*i-1]=2*i-1;
		p[2*i]=2*i;
	}
	sort(p+1, p+2*n+1, cmp);
	for(int i=1;i<=2*n;++i)
	{
		if (w[p[i]].v!=w[p[i-1]].v)
			++tmp;
		if (w[p[i]].t)
			v[w[p[i]].i].y=tmp;
		else
			v[w[p[i]].i].x=tmp;
	}
	for(int i=1;i<=n;++i)
		p[i]=i;
	sort(p+1, p+n+1, comp);
}
int main ()
{
	read ();
	int u=v[p[1]].y;
	for(int i=1;i<=n;++i)
	{
		for(int j=u+1;j<v[p[i]].y;++j)
			b[j]=b[j-1];
		b[v[p[i]].y]=max(b[v[p[i]].y],b[v[p[i]].y-1]);
		b[v[p[i]].y]=max(b[v[p[i]].y],b[v[p[i]].x]+v[p[i]].b-v[p[i]].a);
		u=v[p[i]].y;
	}
	ofstream fout ("heavymetal.out");
	fout<<b[tmp];
	return 0;
}