Pagini recente » Cod sursa (job #29438) | Cod sursa (job #2080183) | Cod sursa (job #1212448) | Cod sursa (job #1586143) | Cod sursa (job #3154573)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct event {
long start, end;
bool operator<(const event &other) {
return end < other.end;
}
};
int main() {
vector<event> v;
vector<int> times;
int n;
fin >> n;
for (int i = 0; i < n; i++) {
int start, finish;
fin >> start >> finish;
times.push_back(start);
times.push_back(finish);
v.push_back({start, finish});
}
sort(times.begin(), times.end());
times.erase(unique(times.begin(), times.end()), times.end());
for (event &c: v) {
c.start = lower_bound(times.begin(), times.end(), c.start) - times.begin();
c.end = lower_bound(times.begin(), times.end(), c.end) - times.begin();
}
sort(v.begin(), v.end());
vector<int> best(times.size(), 0);
int j = 0;
for (int i = 0; i < times.size(); ++i) {
if (i > 0) {
best[i] = best[i - 1];
}
for (; j < n && v[j].end == i; j++) {
best[i] = max(best[i], best[v[j].start] + times[v[j].end] - times[v[j].start]);
}
}
fout << *prev(best.end());
}