Pagini recente » Rating Ioana Teodora (IoanaT) | Cod sursa (job #2309747) | Cod sursa (job #1583321) | Cod sursa (job #162511) | Cod sursa (job #2322591)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifndef DEBUG
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
#endif
int n;
cin >> n;
vector< pair<int, int> > v(n);
for (int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
v[i].second--;
}
sort(v.begin(), v.end());
vector<int> dp(n), mx(n);
int last = -1;
for (int i = 0; i < n; i++) {
while (last < n && v[max(0, last)].second < v[i].first) {
last++;
}
dp[i] = v[i].second - v[i].first + 1;
if (last >= 1) {
dp[i] += mx[last - 1];
}
mx[i] = dp[i];
if (i > 0) {
mx[i] = max(mx[i], mx[i - 1]);
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}