Pagini recente » Cod sursa (job #1179954) | Cod sursa (job #2405907) | Cod sursa (job #1577703) | Cod sursa (job #2059707) | Cod sursa (job #1708858)
#include <algorithm>
#include <fstream>
#define N 100010
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct z
{
int x,y;
}v[N];
int n, sol[N], maxx;
bool cmp(z a, z b)
{
return a.x < b.x;
}
int binsearch(int st, int dr, int val)
{
int poz, mid;
while(st <= dr)
{
mid = (st + dr)/2;
if(v[mid].y <= val) st = mid + 1, poz = mid;
else dr = mid - 1;
}
return st-1;
}
int main()
{
int res = 0;
f >> n;
for(int i = 1; i <= n; ++i)
{
sol[i] = -1;
f >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cmp);
sol[0] = 0;
for(int i = 1; i <= n; ++i)
{
int last = binsearch(0, i - 1, v[i].x);
sol[i] = max(sol[i-1], sol[last] + v[i].y - v[i].x);
res = max(res, sol[i]);
}
g << res << '\n';
return 0;
}