Pagini recente » Cod sursa (job #1971646) | Cod sursa (job #2362911) | Cod sursa (job #2135288) | Cod sursa (job #2858812) | Cod sursa (job #782768)
Cod sursa(job #782768)
# include <cstdio>
# include <algorithm>
# define max(a, b) (a < b ? b : a)
using namespace std;
struct camp
{
long long a, b;
}interv[100005];
int cmp(camp c, camp d)
{
return c.a < d.a;
}
int cautbin(int x, int r)
{int rez;
int l = 0, mid;
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, best[100005];
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i = 1; i <= n; i++)
scanf("%lld %lld",&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("%d",best[n]);
return 0;
}