Pagini recente » Cod sursa (job #79299) | Cod sursa (job #220208) | Cod sursa (job #2636668) | Cod sursa (job #1914293) | Cod sursa (job #2982788)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct Spectacle {
long long start, end;
};
constexpr size_t MAX_N = 1e5 + 1;
long long N, dp[MAX_N];
Spectacle v[MAX_N];
bool compare(Spectacle a, Spectacle b) {
if (a.end != b.end) return a.end < b.end;
return a.start < b.start;
}
int main() {
fin >> N;
for (long long i = 1; i <= N; i++)
fin >> v[i].start >> v[i].end;
sort(v + 1, v + N + 1, compare);
long long ans = 0;
for (long long i = 1; i <= N; i++) {
long long l = 1, r = N;
while (l <= r) {
long long mid = (l + r) / 2;
if (v[mid].end > v[i].start) r = mid - 1;
else l = mid + 1;
}
dp[i] = max(dp[i - 1], dp[r] + v[i].end - v[i].start);
ans = max(ans, dp[i]);
}
fout << ans;
return 0;
}