Cod sursa(job #2053349)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 31 octombrie 2017 18:08:57
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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) {
	int result = -1;

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

	return result;
}

void solve() {
	int result = 0;
	for (int i = 1; i <= n; i++) {
		int pos = binSearch(1, n, band[i].first);
		dp[i] = max(dp[i - 1], dp[pos] + band[pos].second - band[pos].first);
		result = max(result, dp[i]);
	}
	cerr << result << endl;
}

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

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

	return 0;
}