Pagini recente » Cod sursa (job #3127955) | Cod sursa (job #496921) | Cod sursa (job #577482) | Cod sursa (job #1588667) | Cod sursa (job #2911521)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
#define problem "heavymetal"
int main()
{
freopen(problem ".in", "r", stdin);
freopen(problem ".out", "w", stdout);
int n;
scanf("%d", &n);
pair<int, int> v[NMAX];
for (int i = 0; i < n; ++i)
scanf("%d%d", &v[i].first, &v[i].second);
sort(v, v + n, [](pair<int, int>& a, pair<int, int>& b) {
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
});
int dp[NMAX], mx[NMAX], max_step;
dp[0] = mx[0] = v[0].second - v[0].first;
for (max_step = 1; max_step < n; max_step <<= 1);
for (int i = 1; i < n; ++i) {
int step = max_step, index = 0;
for (; step; step >>= 1)
if (index + step < i && v[index + step].second <= v[i].first)
index += step;
dp[i] = v[i].second - v[i].first;
if (v[index].second <= v[i].first)
dp[i] += mx[index];
mx[i] = max(mx[i - 1], dp[i]);
}
printf("%d\n", mx[n - 1]);
}