Pagini recente » Cod sursa (job #1605814) | Cod sursa (job #952987) | Cod sursa (job #979856) | Cod sursa (job #1733150) | Cod sursa (job #2289769)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct costi
{
int a, b;
}v[100005];
long long d[100005];
int prec(int x, int y, int val)
{
int q = 0;
while (x <= y)
{
int mij = (x + y) / 2;
if (val < v[mij].b)
y = mij - 1;
else
{
x = mij + 1;
q = mij;
}
}
return q;
}
inline bool gicu (costi c, costi d)
{
return c.b < d.b;
}
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].a >> v[i].b;
sort(v + 1, v + n + 1, gicu);
for (int i = 1; i <= n; i++)
d[i] = max(d[i - 1], d[prec(1, i - 1, v[i].a)] + v[i].b - v[i].a);
fout << d[n] << '\n';
return 0;
}