Pagini recente » Cod sursa (job #1765070) | Cod sursa (job #764397) | Cod sursa (job #1780664) | Borderou de evaluare (job #1036886) | Cod sursa (job #177616)
Cod sursa(job #177616)
#include <stdio.h>
#include <stdlib.h>
#define INF 2000000000
#define N 100005
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 maxim(int x, int y){
if(x>y) return x;
return y;
}
int main(){
int n,i,best[N]={0},j,max=0;
interval v[N];
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);
v[n+1].b=INF;
qsort(v,n+1,sizeof(v[0]),comp);
for(i=1;i<=n;i++){
max=0;
best[v[i].b]=best[v[i-1].b];
for(j=1;v[j].b<=v[i].a;j++)
// best[v[i].b]=maxim(best[v[i].b],best[v[j].a]+(v[j].b-v[j].a));
max=maxim(max,best[v[j].b]);
best[v[i].b]=maxim(max+v[i].b-v[i].a,best[v[i].b]);
}
printf("%d\n\n",best[v[n].b]);
/*for(i=1;i<=n;i++)
printf("%d ",v[i].b);
printf("\n");
for(i=1;i<=n;i++)
printf("%d ",best[v[i].b]);
*/
return 0;
}