Pagini recente » Cod sursa (job #2489331) | Cod sursa (job #364057) | Cod sursa (job #2069984) | Arhiva de probleme | Cod sursa (job #147545)
Cod sursa(job #147545)
#include <stdio.h>
#include <algorithm>
using namespace std;
long i, j, n, k, l, best[36010];
struct lol
{
long s, e;
};
lol x[36010];
int cmpf(lol a, lol b)
{
return a.e < b.e;
}
long cautbin(long st, long dr)
{
long m = (st + dr) / 2;
if (st > dr || st == dr || dr - st == 1)
return m;
else
if (x[m].e <= l)
return cautbin(m, dr);
else
return cautbin(st, m);
}
int main()
{
freopen ("heavymetal.in", "rt", stdin);
freopen ("heavymetal.out", "wt", stdout);
scanf("%ld", &n);
for (i = 1; i <= n; i ++)
scanf("%ld %ld", &x[i].s, &x[i].e);
sort(x + 1, x + n + 1, cmpf);
//best[1] = x[1].e - x[1].s;
for (i = 1; i <= n; i ++)
{
best[i] = best[i - 1];
for (j = 1; j <= n; j ++)
if (x[j].e == x[i].e)
{
l = x[j].s;
k = cautbin(1, i);
best[i] = best[i] > best[k] + (x[j].e - x[j].s) ? best[i] : best[k] + (x[j].e - x[j].s);
}
}
printf("%ld\n", best[n]);
return 0;
}