Pagini recente » Cod sursa (job #2034237) | Cod sursa (job #1295763) | Cod sursa (job #1101412) | Cod sursa (job #3150313) | Cod sursa (job #154313)
Cod sursa(job #154313)
#include <stdio.h>
#include <stdlib.h>
struct interval{
int a,b;
};
int comp(const void*a,const void*b){
interval *aa=(interval*)a,*bb=(interval*)b;
interval aaa=*aa,bbb=*bb;
if(aaa.b>bbb.b) return 1;
if(aaa.b<bbb.b) return -1;
return 0;
}
int main(){
int n,i,best[1000000000]={0},j,max=0,t=1;
interval v[100001];
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
v[0].a=0;v[0].b=0;
for(i=1;i<=n;i++){
scanf("%d%d",&v[i].a,&v[i].b);
if(v[i].b>max) max=v[i].b;
}
qsort(v,n+1,sizeof(v[0]),comp);
for(i=1;i<=max;i++){
best[i]=best[i-1];
if(v[t].b==i) {
for(j=1;v[j].b<=i;j++)
if(best[i]<best[v[j].a]+(v[j].b-v[j].a)) best[i]=best[v[j].a]+(v[j].b-v[j].a);
t++;
}
}
printf("%d",best[max]);
return 0;
}