Cod sursa(job #154403)

Utilizator slayer4uVictor Popescu slayer4u Data 11 martie 2008 10:16:04
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

long i, j, n, k, l, best[36010], tmax;

struct lol
{
	long s, e;
};
lol x[36010];

int main()
{
	freopen ("heavymetal.in", "rt", stdin);
	freopen ("heavymetal.out", "wt", stdout);
	
	scanf("%ld", &n);
	
	for (i = 1; i <= n; i ++)
		scanf("%ld %ld", &x[i].s, &x[i].e), tmax = x[i].e > tmax ? x[i].e : tmax;
	
	for (i = 1; i <= tmax; i ++)
	{
		best[i] = best[i - 1];
		for (j = 1; j <= n; j ++)
			if (x[j].e == i)
				best[i] = best[i] > best[x[j].s] + (x[j].e - x[j].s) ? best[i] : best[x[j].s] + (x[j].e - x[j].s);
	}
	
	printf("%ld\n", best[tmax]);
	return 0;
}