Cod sursa(job #361003)

Utilizator funkydvdIancu David Traian funkydvd Data 3 noiembrie 2009 11:50:54
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<fstream>
#define N 1<<17
using namespace std;ifstream f1 ("heavymetal.in");ofstream f2 ("heavymetal.out");
struct trupa {int a,b;}; 
int tmax=0,n,best[N];
trupa t[N];
int cmp(trupa a, trupa b)
{
	return a.b<b.b;
}
int main()
{
  int i,j;
  f1>>n;
  for (i=1; i<=n; i++) {f1>>t[i].a>>t[i].b; if (t[i].b>tmax) tmax=t[i].b;}
  sort (t+1,t+n+1,cmp);
  int k=1;
  best[0]=0;
  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;
}