Pagini recente » Cod sursa (job #2712877) | Cod sursa (job #2401443) | Cod sursa (job #2878427) | Cod sursa (job #2600672) | Cod sursa (job #2737835)
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct P {
int x;
int y;
};
P v[100001];
int sol[100001];
int n;
int main()
{
in >> n;
for (int i = 1; i <= n; i++) {
int a, b;
in >> a >> b;
v[i] = { a,b };
}
sort(v + 1, v + n + 1, [](P a, P b) {
if (a.x > b.x) return false;
else if (a.x < b.x) return true;
else return a.y < b.y;
});
int j = 1;
for (int i = 1; i <= v[n].y; i++) {
sol[i] = sol[i - 1];
while (v[j].y == i) {
sol[i] = max(sol[i], sol[v[j].x] + v[j].y - v[j].x);
j++;
}
}
out << sol[v[n].y];
return 0;
}