Cod sursa(job #147545)

Utilizator slayer4uVictor Popescu slayer4u Data 3 martie 2008 09:51:41
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

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

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

int cmpf(lol a, lol b)
{
	return a.e < b.e;
}

long cautbin(long st, long dr)
{
	long m = (st + dr) / 2;
	if (st > dr || st == dr || dr - st == 1)
		return m;
	else
	if (x[m].e <= l)
		return cautbin(m, dr);
	else
		return cautbin(st, m);
}

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);
	
	sort(x + 1, x + n + 1, cmpf);
	
	//best[1] = x[1].e - x[1].s;
	for (i = 1; i <= n; i ++)
	{
		best[i] = best[i - 1];
		for (j = 1; j <= n; j ++)
			if (x[j].e == x[i].e)
			{
				l = x[j].s;
				k = cautbin(1, i);
				best[i] = best[i] > best[k] + (x[j].e - x[j].s) ? best[i] : best[k] + (x[j].e - x[j].s);
			}
	}
	
	printf("%ld\n", best[n]);
	return 0;
}