Pagini recente » Cod sursa (job #316471) | Cod sursa (job #1421995) | Cod sursa (job #106551) | Cod sursa (job #2599862) | Cod sursa (job #783581)
Cod sursa(job #783581)
# include <cstdio>
# include <algorithm>
# define max(a, b) (a < b ? b : a)
using namespace std;
struct camp
{
int a, b;
}interv[1000005];
int cmp(camp c, camp d)
{
return c.a < d.a;
}
int cautbin(int x, int r)
{int rez;
int l = 0, mid = 0;
while (l <= r)
{
mid = (l + r) / 2;
if (interv[mid].b <= x){ rez = mid; l = mid + 1; }
else r = mid - 1;
}
return rez;
}
int n, i, poz;
long long best[100005];
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i = 1; i <= n; i++)
scanf("%d %d",&interv[i].a,&interv[i].b);
sort(interv + 1, interv + n + 1, cmp);
for (i = 1; i <= n; i++)
{
poz = cautbin(interv[i].a, i - 1);
best[i] = max(best[i - 1], best[poz] + interv[i].b - interv[i].a);
}
printf("%lld",best[n]);
return 0;
}