Pagini recente » Cod sursa (job #405843) | Cod sursa (job #293071) | Cod sursa (job #313037) | Cod sursa (job #1306619) | Cod sursa (job #607520)
Cod sursa(job #607520)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct vect
{
int st, dr;
};
int n, sol[100002];
vect v[100002];
inline int cmp (vect a, vect b)
{
return a.dr < b.dr;
}
int cautare (int x)
{
int st = 1, dr = n, m, sol = 0;
while (st <= dr)
{
m = (st + dr) >> 1;
if (v[m].dr <= x)
{
sol = m;
st = m + 1;
}
else
dr = m - 1;
}
return sol;
}
int main ()
{
freopen ("heavymetal.in", "r", stdin);
freopen ("heavymetal.out", "w", stdout);
scanf ("%d", &n);
int i, poz;
for (i = 1; i <= n; i ++)
scanf ("%d %d", &v[i].st, &v[i].dr);
sort (v + 1, v + n + 1, cmp);
sol[1] = v[1].dr - v[1].st;
for (i = 2; i <= n; i ++)
{
poz = cautare (v[i].st);
sol[i] = max (sol[i - 1], sol[poz] + v[i].dr - v[i].st);
}
printf ("%d\n", sol[n]);
return 0;
}