Cod sursa(job #614531)

Utilizator andra23Laura Draghici andra23 Data 6 octombrie 2011 19:27:53
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
#include<algorithm>

using namespace std;

const int maxn = 100005;

pair <int,int> segm[maxn];
long long maxim[maxn], c[maxn];

int cmp(pair <int,int> a, pair <int,int> b) {
	return (a.second == b.second && a.first < b.first) ||
		(a.second < b.second);
}

int bsearch(int left, int right, int x) {
	int m, pos = 0;
	while (left <= right) {
		m = (left+right)/2;
		if (segm[m].second <= x) {
			pos = m;
			left = m+1;
		} else {
			right = m-1;
		}
	}
	return pos;
}

int main() {
	ifstream f("heavymetal.in");
	ofstream g("heavymetal.out");

	int n, x, y;
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> x >> y;
		segm[i] = make_pair(x, y);
	}

	sort(segm+1, segm+n+1, cmp); 

	c[1] = segm[1].second-segm[1].first;
	maxim[1] = c[1];
	
	for (int i = 2; i <= n; i++) {
		int pos = bsearch(1, i-1, segm[i].first);
		c[i] = maxim[pos] + segm[i].second - segm[i].first;
		maxim[i] = maxim[i-1];
		if (c[i] > maxim[i-1]) {
			maxim[i] = c[i];
		}
	}

	g << maxim[n] << '\n';

	return 0;
}