Cod sursa(job #359107)

Utilizator funkydvdIancu David Traian funkydvd Data 25 octombrie 2009 19:14:19
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
#define T 1<<17
using namespace std;
ifstream f1 ("heavymetal.in");
ofstream f2 ("heavymetal.out");
int n,best[T];
struct trupa {int a,b;};
trupa t[100001];
int cmp(const void *p,const void *q)
{
	trupa x=*(trupa*)p,y=*(trupa*)q;
	if(x.b<y.b)
		return -1;
	if(x.b>y.b)
		return 1;
	return 0;
}
int main()
{
  int i,j,tmax=0;
  f1>>n;
  for (i=1; i<=n; i++) {f1>>t[i].a>>t[i].b; if (t[i].b>tmax) tmax=t[i].b;}
  qsort (t+1,n,sizeof(t[0]),cmp);
  int k=1;
  for (i=1; i<=tmax; i++)
  {
   best[i]=best[i-1];
   if (t[k].b==i) 
   {
	   best[i]=max(best[i], best[t[k].a] + (t[k].b - t[k].a));
		k++;
   }
  }
  f2<<best[tmax];
  return 0;
}