Pagini recente » Cod sursa (job #1060942) | Cod sursa (job #3293142) | Cod sursa (job #2188874) | Cod sursa (job #889583) | Cod sursa (job #2911504)
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
const int max_size = 1e6 + 1;
pair <int, int> v[max_size];
int dp[max_size];
bool cmp (pair <int, int> x, pair <int, int> y)
{
if (x.second != y.second)
{
return x.second < y.second;
}
return x.first < y.first;
}
int main ()
{
int n;
in >> n;
for (int i = 1; i <= n; i++)
{
in >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int x = v[i].first, y = v[i].second, r = i - 1, l = 1;
while (l <= r)
{
int m = (l + r) / 2;
if (v[m].second <= x)
{
l = m + 1;
}
else
{
r = m - 1;
}
}
dp[i] = max(dp[i - 1], dp[r] + y - x);
}
out << dp[n];
in.close();
out.close();
return 0;
}