Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/fasined | Profil Alina_Caprioara | Cod sursa (job #207846)
Cod sursa(job #207846)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 100010
int n;
int a[maxn], b[maxn], p[maxn];
int c[maxn];
int cmp(int x, int y)
{
return b[x] < b[y];
}
int search(int x)
{
int front = 1, middle, back = n, rez = 0;
while (front <= back)
{
middle = (front + back) / 2;
if (x <= b[p[middle]])
{
rez = middle;
back = middle - 1;
}
else front = middle + 1;
}
return rez;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d ", &n);
int i, x;
for (i=1; i<=n; i++)
{
scanf("%d %d ", &a[i], &b[i]);
p[i] = i;
}
sort(p+1, p+n+1, cmp);
for (i=1; i<=n; i++)
{
x = search(a[p[i]]);
c[i] = max(c[i-1], c[x] + b[p[i]] - a[p[i]]);
}
printf("%d\n", c[n]);
return 0;
}