Pagini recente » Cod sursa (job #1027304) | Cod sursa (job #1532108) | Cod sursa (job #2553659) | Cod sursa (job #2529590) | Cod sursa (job #2108735)
#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<<16, 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 = 0; i < n; ++i) {
cin >> v[i].second >> v[i].first;
}
sort(v, v + n);
for (int i = 0; i < n; ++i) {
d[i] = d[i - 1];
x = cb(v[i].second);
d[i] = max(d[i], d[x] + v[i].first - v[i].second);
}
cout << d[n - 1];
return 0;
}