Cod sursa(job #388377)

Utilizator bog29Antohi Bogdan bog29 Data 29 ianuarie 2010 22:30:08
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#define dmax 100003
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

int n;
long long dn[dmax],pr[dmax];
struct sp
{	long long p1;
	long long p2;
}	s[dmax]	;
typedef int (*compfn)(const void*,const void*);

int sf(struct sp *a,struct sp *b)
{	return a->p2 - b->p2;	
}

int main()
{	int i,j,ok;
	in>>n;
	for(i=0;i<n;i++)
		in>>s[i].p1>>s[i].p2;
	in.close();
	qsort((void*)&s, n, sizeof(struct sp), (compfn)sf);
	for(i=n-1;i>0;i--)
	{	ok=1;
		for(j=i-1;j>=0 && ok;j--)
			if(s[j].p2<=s[i].p1)
			{	ok=0;
				pr[i]=j;
			}
	}		
	for(i=0;i<n;i++)
	{	if(i==0)
			dn[i]=s[i].p2-s[i].p1;
		else
			dn[i]=s[i].p2-s[i].p1+dn[pr[i]];
	}
	out<<dn[n-1];	
	out.close();
	return 0;
}