Cod sursa(job #219910)

Utilizator ProtomanAndrei Purice Protoman Data 8 noiembrie 2008 19:56:58
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#include <algorithm>
#define mx 110000

using namespace std;

pair <int, int> a[mx];
int vm[mx];
int n;

int cauta(int p, int u, int lim)
{
	if (p > u)
		return 0;
	int m = (p + u) / 2;
	if (a[m].first <= lim && a[m + 1].first > lim)
		return m;
	else if (a[m].first <= lim)
		return (cauta(m + 1, u, lim));
	else return (cauta(p, m - 1, lim));
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%ld", &n);
	for (int i = 1; i <= n; i++)
		scanf("%ld %ld", &a[i].second, &a[i].first);
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
		vm[i] = max(vm[cauta(0, i - 1, a[i].second)] + a[i].first - a[i].second, vm[i - 1]);
	printf("%ld\n", vm[n]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}