Cod sursa(job #344689)

Utilizator bog29Antohi Bogdan bog29 Data 31 august 2009 13:08:23
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream>
#define dmax 100002
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
long int n,temp[dmax];
struct formatii
{	long int x;
	long int y;
}	m[dmax];
typedef int compfn(const void *,const void *);
int sf(struct formatii *a,struct formatii *b)
{	return (a->x - b->x);
}
int main()
{	int i,j;
	in>>n;
	for(i=0;i<n;i++)
		in>>m[i].x>>m[i].y;
	in.close();
	qsort((void*)&m,n,sizeof(struct formatii),(compfn*)sf);
	for(i=0;i<n;i++)
	{	if(i==0)
			temp[i]=m[i].y-m[i].x;
		else
		{	temp[i]=m[i].y-m[i].x;
			for(j=0;j<i;j++)	
				if(m[i].x>=m[j].y)
					temp[i]=max(temp[i],temp[j]+m[i].y-m[i].x);	
		}
	}
	out<<temp[n-1];	
	out.close();
	return 0;
}