Pagini recente » Cod sursa (job #2267461) | Cod sursa (job #1720147) | Cod sursa (job #2092249) | Cod sursa (job #1004865) | Cod sursa (job #185871)
Cod sursa(job #185871)
#include <stdio.h>
#include <stdlib.h>
int n,ord[100000],d[1000000],i,j,x,aux,max;
typedef struct
{
int a, b;
} interval;
interval a[100000], b[100000];
int cmp(const void *j, const void *k)
{
int x=*(int*)j, y=*(int*)k;
if (a[x].b==a[y].b) return a[x].a-a[y].a;
return a[x].b-a[y].b;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i=0; i<n; ++i) { scanf("%d%d",&a[i].a,&a[i].b);ord[i]=i; }
qsort(ord, n, sizeof(int), cmp);
for (i=1; i<=n; ++i) b[i]=a[ord[i-1]];
x=b[n].b;
j=1;
for (i=1; i<=x; ++i)
{
d[i]=d[i-1];
while ( i == b[ j ].b)
{ aux = d[b[j].a] + b[j].b - b[j].a;
if(aux > d[i]) d[i] = aux;
j++;
}
if (d[i] > max) max=d[i];
}
printf("%d",max);
return 0;
}