Cod sursa(job #360541)

Utilizator funkydvdIancu David Traian funkydvd Data 31 octombrie 2009 19:59:44
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.43 kb
#include<fstream>
using namespace std;
ifstream f1 ("heavymetal.in");
ofstream f2 ("heavymetal.out");
int n,a[100001],b[100001];
int best[100001];
int main()
{
  int i,j,tmax=0;
  f1>>n;
  for (i=1; i<=n; i++) {f1>>a[i]>>b[i]; if (b[i]>tmax) tmax=b[i];}
  for (i=1; i<=tmax; i++)
  {
   best[i]=best[i-1];
   for (j=1; j<=n; j++)
    if (b[j]==i) best[i]=max(best[i], best[a[j]] + (b[j] - a[j]));
  }
  f2<<best[tmax];
  return 0;
}