Pagini recente » Cod sursa (job #405127) | Cod sursa (job #979930) | Cod sursa (job #996403) | Cod sursa (job #1077241) | Cod sursa (job #2999373)
#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;
}