Pagini recente » Cod sursa (job #635061) | Cod sursa (job #2906487) | Cod sursa (job #1645101) | Cod sursa (job #494956) | Cod sursa (job #160851)
Cod sursa(job #160851)
#include<stdio.h>
#include<stdlib.h>
struct interval
{
int a,b;
};
int best[1000000];
interval v[100000];
int compar(const void*p,const void*q){
interval *pp=(interval*)p, *qq=(interval*)q;
interval u=*pp,w=*qq;
if(u.b<w.b)
return -1;
if(u.b>w.b)
return 1;
return u.a-w.a;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,max=0,x,j=0,aux;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d%d",&v[i].a,&v[i].b);
}
qsort(v,n,sizeof(v[0]),compar);
/*for(i=0; i<n; i++)
{
printf("%d %d\n",v[i].a,v[i].b);
}*/
x=v[n-1].b;
for(i=1; i<=x; i++)
{
best[i]=best[i-1];
while(i==v[j].b)
{
aux=best[v[j].a]+v[j].b-v[j].a;
if(aux>best[i])
best[i]=aux;
j++;
}
if(best[i]>max)
max=best[i];
}
printf("%d\n",max);
return 0;
}