Pagini recente » Cod sursa (job #2480590) | Cod sursa (job #1198837) | Cod sursa (job #37859) | Cod sursa (job #3143542) | Cod sursa (job #2778173)
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
//4
//3 5
//5 10
//3 4
//1 2
const int maxN = (int)1e5;
int n;
int maxLen[maxN + 5];
pair<int, int> segments[maxN + 5];
bool rev(const pair<int, int> &st, const pair<int, int> &snd) {
return st.second < snd.second;
}
int main() {
in >> n;
for (int i = 1; i <= n; i++) {
in >> segments[i].first >> segments[i].second;
}
sort(segments + 1, segments + n + 1, rev);
maxLen[1] = segments[1].second - segments[1].first;
for (int i = 2; i <= n; i++) {
maxLen[i] = maxLen[i - 1];
if (segments[i].first >= segments[i - 1].second) {
maxLen[i] = maxLen[i - 1] + segments[i].second - segments[i].first;
} else {
int l = 1, r = i - 2, pos = 0;
while (l <= r) {
int m = (l + r) / 2;
if (segments[m].second <= segments[i].first) {
pos = m;
l = m + 1;
} else {
r = m - 1;
}
}
maxLen[i] = max(maxLen[i], maxLen[pos] + segments[i].second - segments[i].first);
}
}
out << maxLen[n] << "\n";
return 0;
}