Cod sursa(job #519358)

Utilizator Addy.Adrian Draghici Addy. Data 5 ianuarie 2011 09:11:54
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

using namespace std;

#define NMAX 100050

struct inter {
	int x, y;
} V[NMAX];

int S[NMAX], mid, n, p, u, i, j;

bool cmp (inter a, inter b) {
	return a.x < b.y;
}

int main () {
	
	ifstream f ("heavymetal.in");
	ofstream g ("heavymetal.out");
	
	f >> n;
	
	for (i = 1; i <= n; i++)
		f >> V[i].x >> V[i].y;
	
	sort (V + 1, V + 1 + n, cmp);
	
	for (i = 1; i <= n; i++) {
		
		p = 1, u = i - 1, j = 0;
		while (p <= u) {
			mid = (u - p) / 2 + p;
			if (V[mid].y > V[i].x)
				u = mid - 1;
			else
				p = mid + 1, j = mid;
		}
		
		S[i] = max (S[i-1], S[j] + V[i].y - V[i].x);
	}
	
	g << S[n];
	
	f.close (); g.close ();
	
	return 0;
}