Pagini recente » Cod sursa (job #1074596) | Cod sursa (job #1227439) | Cod sursa (job #2443443) | Cod sursa (job #2417815) | Cod sursa (job #2674437)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct spectacol {
long long int inceput;
long long int final;
} v[100001];
bool comp(spectacol a, spectacol b) {
return (a.final < b.final) || (a.final == b.final && a.inceput < b.inceput);
}
int n, dis[100001], maxim[100001], solutie;
int main() {
ios::sync_with_stdio(false);
in.tie(NULL), out.tie(NULL);
in >> n;
for (int i = 1; i <= n; i++) {
in >> v[i].inceput >> v[i].final;
}
sort(v + 1, v + n + 1, comp);
for (int i = 1; i <= n; i++) {
int left = 1, right = i - 1, sol = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (v[i].inceput >= v[mid].final) {
sol = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
dis[i] = maxim[sol] + v[i].final - v[i].inceput;
maxim[i] = max(maxim[i - 1], dis[i]);
}
for (int i = 1; i <= n; i++) solutie = max(solutie, maxim[i]);
out << solutie;
return 0;
}