Cod sursa(job #360531)

Utilizator funkydvdIancu David Traian funkydvd Data 31 octombrie 2009 19:32:40
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<cstdio>
#include<fstream>
#define N 1<<17
using namespace std;
int n,best[N];
struct tru {int a,b;};
tru t[N];
int cmp(const void *p,const void *q)
{
	tru x=*(tru*)p,y=*(tru*)q;
	if(x.b<y.b)
		return -1;
	if(x.b>y.b)
		return 1;
	return 0;
}
int main()
{
  freopen ("bridge.in", "r", stdin);
  freopen ("bridge.out", "w", stdout);
  int i,j,tmax=0;
  scanf ("%d", &n);
  for (i=1; i<=n; i++) {scanf ("%d %d", &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++;
   }
  }
  printf ("%d", best[tmax]);
  return 0;
}