Pagini recente » Cod sursa (job #2499285) | Cod sursa (job #2731753) | Cod sursa (job #510495) | Cod sursa (job #474302) | Cod sursa (job #2108754)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n;
pair < int, int > v[100010];
int d[100010];
int cb(int val) {
int pas = 1<<17, r = 0;
while (pas > 0) {
if (pas + r <= n && v[r + pas].first <= val) {
r += pas;
}
pas /= 2;
}
return r;
}
int main()
{
int x;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> v[i].second >> v[i].first;
}
sort(v + 1, v + n + 1);
for (int i = 1; i <= n; ++i) {
d[i] = d[i - 1];
x = cb(v[i].second);
//cout << x << " " << i << "\n";
d[i] = max(d[i], d[x] + v[i].first - v[i].second);
}
cout << d[n - 1];
return 0;
}