Cod sursa(job #2053369)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 31 octombrie 2017 18:21:10
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100002;

int n;
pair<int, int> band[MAXN];
int dp[MAXN];

void read() {
	scanf("%d ", &n);
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d %d\n", &x, &y);
		band[i] = { x, y };
	}
}

int binSearch(int left, int right, int value) {

	while (left < right) {
		int middle = (left + right + 1) / 2;
		if(band[middle].second <= value)
			left = middle;
		else right = middle - 1;
	}

	return left;
}

void solve() {
	dp[1] = band[1].second - band[1].first;

	for (int i = 2; i <= n; i++)
		dp[i] = max(dp[i - 1], dp[binSearch(0, i, band[i].first)] + band[i].second - band[i].first);

	printf("%d\n", dp[n]);
}

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}

int main() {
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);

	read();
	sort(band + 1, band + n + 1, cmp);
	solve();

	return 0;
}