Cod sursa(job #595138)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 11 iunie 2011 12:04:47
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
# include <fstream>
# include <algorithm>
using namespace std;

struct T {int i, j;} a[100001];
int i, n, best[100001];

template <typename name>
	inline name bs (name find, name left)
	{
		name i, cnt = 1 << 18;
		for (i = 1; cnt > 0; cnt >>= 1)
			if (i + cnt <= left)
				if (a[i + cnt].j <= find) i += cnt;
		return i;
	}

inline bool cmp (T a, T b)
{
	return a.j < b.j;
}

template <class name>
	inline name MAX (name a, name b)
	{
		return a > b ? a : b;
	}

int main ()
{
	ifstream f ("heavymetal.in");
	ofstream g ("heavymetal.out");
	
	f >> n;
	
	for (i = 1; i <= n; ++i)
		f >> a[i].i >> a[i].j;
	
	sort (a + 1, a + n + 1, cmp);
	
	best[1] = a[1].j - a[1].i;
	for (i = 2; i <= n; ++i)
	{
		best[i] = MAX (best[i], best[bs (a[i].i, i)] + (a[i].j - a[i].i));
	}
	
	g << best[n] << '\n';
	g.close ();
	return 0;
}