Cod sursa(job #607520)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 12 august 2011 14:22:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>

#include <algorithm>

using namespace std;

struct vect
{
	int st, dr;
};

int n, sol[100002];
vect v[100002];

inline int cmp (vect a, vect b)
{
	return a.dr < b.dr;
}

int cautare (int x)
{
	int st = 1, dr = n, m, sol = 0;
	
	while (st <= dr)
	{
		m = (st + dr) >> 1;
		if (v[m].dr <= x)
		{
			sol = m;
			st = m + 1;
		}
		else
			dr = m - 1;
	}
	return sol;
}

int main ()
{
	freopen ("heavymetal.in", "r", stdin);
	freopen ("heavymetal.out", "w", stdout);
	
	scanf ("%d", &n);
	
	int i, poz;
	
	for (i = 1; i <= n; i ++)
		scanf ("%d %d", &v[i].st, &v[i].dr);
	sort (v + 1, v + n + 1, cmp);
	
	sol[1] = v[1].dr - v[1].st;
	for (i = 2; i <= n; i ++)
	{
		poz = cautare (v[i].st);
		sol[i] = max (sol[i - 1], sol[poz] + v[i].dr - v[i].st);
	}
	printf ("%d\n", sol[n]);
	return 0;
}