Cod sursa(job #2999373)

Utilizator TAhmed33Tarek Ahmed TAhmed33 Data 10 martie 2023 21:49:36
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
deque <pair <int, int>> arr;
int n;
int dp[100000];
int ans (int pos) {
	int &ret = dp[pos];
	if (ret != -1) return ret;
	if (pos == n - 1) {
		return ret = arr[pos].second - arr[pos].first + 1;
	}
	int l = pos + 1, r = n - 1;
	int mid, aa = n;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (arr[mid].first > arr[pos].second) {
			aa = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	if (aa == n) {
		return ret = max(ans(pos + 1), arr[pos].second - arr[pos].first + 1);
	}
	return ret = max(ans(pos + 1), arr[pos].second - arr[pos].first + 1 + ans(aa));
}
int main () {
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);
	memset(dp, -1, sizeof(dp));
	cin >> n;
	arr.resize(n);
	for (auto &[x, y] : arr) {
		cin >> x >> y;
		x++;
	}
	//choose set of disjoint intervals which cover maximum length
	sort(arr.begin(), arr.end());
	cout << ans(0) << endl;
}