Pagini recente » Cod sursa (job #1235174) | Cod sursa (job #1918327) | Cod sursa (job #2328772) | Cod sursa (job #2143406) | Cod sursa (job #2106328)
#include <fstream>
#include <algorithm>
#define LIM 16
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
long long dp[100001], f[100001];
int n, m;
pair <long long, long long> v[100001];
int cautbin(int x) {
int r = 0, pas = 1 << LIM;
while (pas != 0) {
if (r + pas <= m && f[r + pas] <= x) {
r += pas;
}
pas >>= 1;
}
return r;
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++) {
in >> v[i].second >> v[i].first;
f[i] = v[i].first;
}
sort(v + 1, v + n + 1);
sort(f + 1, f + n + 1);
for (int i = 2, j = 1; i <= n; i++) {
if (f[i] != f[i - 1]) f[++j] = f[i];
m = j;
}
for (int i = 1; i <= n; i++) {
int st = cautbin(v[i].second), dr = cautbin(v[i].first);
dp[dr] = max(dp[dr], dp[st] - v[i].second + v[i].first);
dp[dr] = max(dp[dr], dp[dr - 1]);
}
out << dp[n];
}