Pagini recente » Cod sursa (job #2833526) | Cod sursa (job #1628526) | Cod sursa (job #1242419) | Cod sursa (job #1155899) | Cod sursa (job #2289759)
#include <iostream>
#include <fstream>
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)
{
q = d[mij];
y = mij - 1;
}
if (val > v[mij].b)
x = mij + 1;
}
return q;
}
int main()
{
int n;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].a >> v[i].b;
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (v[i].b > v[j].b)
{
swap(v[i].b, v[j].b);
swap(v[i].a, v[j].a);
}
for (int i = 1; i <= n; i++)
d[i] = max(d[i - 1], prec(1, i - 1, v[i].a) + v[i].b - v[i].a);
fout << d[n] << '\n';
return 0;
}