Pagini recente » Cod sursa (job #800740) | Cod sursa (job #2027311) | Cod sursa (job #2784173) | Cod sursa (job #2739092) | Cod sursa (job #154357)
Cod sursa(job #154357)
#include <stdio.h>
#include <stdlib.h>
#define INF 2000000000
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;
else if(aaa.b==bbb.b && aaa.a<bbb.a) return -1;
if(aaa.b>bbb.b) return 1;
return 0;
}
int main(){
int n,i,best[100000]={0},j,max=0,t=1;
interval v[100005];
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;
}
v[n+1].b=INF;
qsort(v,n+1,sizeof(v[0]),comp);
for(i=1;i<=max;i++)
if(v[t].b==i) {
best[i]=best[i-1];
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;
}