Cod sursa(job #155150)

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

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

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

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

inline 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);
	
//	for (o = 1; o <= 10; o ++)
//	{
		memset(best, 0, sizeof(best));
		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 = i; j <= n; j ++)
				if (x[j].e == x[i].e)
				{
					best[j] = best[j - 1];
					l = x[j].s;
					k = cautbin(0, i);
					best[j] = best[j] > best[k] + (x[j].e - x[j].s) ? best[j] : best[k] + (x[j].e - x[j].s);
				}
				else
					break;
			i = j - 1;
		}

		printf("%ld\n", best[n]);
//	}
	return 0;
}