Cod sursa(job #446821)

Utilizator c912045Marcu Florian c912045 Data 26 aprilie 2010 19:11:24
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
using namespace std;
#include<fstream>
#include<algorithm>
#define mk make_pair
#define x first
#define y second
const int MAX_N = 100007;
pair<int, int> A[MAX_N];
int N, bst[MAX_N];
struct cmp
{
	bool operator()(const pair<int, int> &a, const pair<int, int> &b)const
	{
		return (a.y == b.y)?( a.x < b.x ):(a.y < b.y);
	}
};
inline int intersect(pair<int, int> A, pair<int, int>B)
{
	if( B.y <= A.x ) return 0;
	return 1;
}
int main()
{
	ifstream in("heavymetal.in"); ofstream out("heavymetal.out");
	int i, j, a, b;
	in>>N;
	for(i = 1; i <= N; ++i)
	{
		in>>a>>b;
		A[i] = mk(a,b);
	}
	sort(A+1, A+N+1, cmp());
	bst[1] = A[1].y - A[1].x;
	for(j = 1, i = 2; i <= N; ++i)
	{
		bst[i] = max(bst[i-1], A[i].y - A[i].x );
		while(j && intersect( A[i], A[j] )) --j;
		while( !intersect( A[i], A[j] ) )
			bst[i] = max( bst[i], bst[j] + A[i].y - A[i].x ), ++j;
		
	}
	out<<bst[N]<<"\n";
	return 0;
}