Pagini recente » Cod sursa (job #36309) | Cod sursa (job #2737407) | Cod sursa (job #1802307) | Cod sursa (job #1162977) | Cod sursa (job #1891223)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct concert{
int start, end;
} c[100001];
int n;
long long best[100001];
const int L = 1 << 17;
bool compare(concert a, concert b) {
return a.end < b.end;
}
int binary_search(int val) {
int step = L;
int pos = 0;
while (step != 0) {
if (pos + step <= n && c[pos + step].end <= val) {
pos += step;
}
step /= 2;
}
return pos;
}
int main()
{
in >> n;
for (int i = 1; i <= n; ++i) {
in >> c[i].start >> c[i].end;
}
sort(c + 1, c + n + 1, compare);
best[1] = c[1].end - c[1].start;
for (int i = 2; i <= n; ++i) {
int before = binary_search(c[i].start);
best[i] = max(
(c[i].end - c[i].start) + best[before],
best[i - 1]
);
}
out << best[n];
return 0;
}