Cod sursa(job #207847)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 13 septembrie 2008 02:53:23
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 100010

int n;
int a[maxn], b[maxn], p[maxn];
int c[maxn];

int cmp(int x, int y)
{
	return b[x] < b[y];
}

int search(int x)
{
	int front = 1, middle, back = n, rez = 0;

	while (front <= back)
	{
		middle = (front + back) / 2;

		if (x >= b[p[middle]])
		{
			rez = middle;
			front = middle + 1;
		}
		else back = middle - 1;
	}

	return rez;
}

int main()
{
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);

	scanf("%d ", &n);

	int i, x;

	for (i=1; i<=n; i++)
	{
		scanf("%d %d ", &a[i], &b[i]);
		p[i] = i;
	}

	sort(p+1, p+n+1, cmp);

	for (i=1; i<=n; i++) 
	{
		x = search(a[p[i]]);

		c[i] = max(c[i-1], c[x] + b[p[i]] - a[p[i]]);
	}

	printf("%d\n", c[n]);

	return 0;
}