Cod sursa(job #358397)

Utilizator funkydvdIancu David Traian funkydvd Data 22 octombrie 2009 22:22:07
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream f1 ("heavymetal.in");
ofstream f2 ("heavymetal.out");
int n,best[1000001];
struct trupa {int a,b;};
trupa t[100001];
int max(int a, int b)
{
	if (a>b) return a;
	return b;
}
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;
}