Pagini recente » Cod sursa (job #2366268) | Cod sursa (job #700659) | Cod sursa (job #1973360) | Cod sursa (job #1084164) | Cod sursa (job #150670)
Cod sursa(job #150670)
#include<stdio.h>
int val,u,mij,sol,v[100001],n,i,k,c,p;
struct heavy{int a,b;};
heavy s[100001],aux;
void sort(){
for(i=2;i<=k;i++){
c=i;
p=c>>1;
while((p)&&(s[c].b>s[p].b)){
aux=s[c];
s[c]=s[p];
s[p]=aux;
c=p;
p=c>>1;
}
}
for(i=k;i>1;i--){
aux=s[i];
s[i]=s[1];
s[1]=aux;
p=1;
c=p<<1;
k--;
while(c<=k){
if((s[c].b<s[c+1].b)&&c<k){c++;}
if(s[p].b<s[c].b){
aux=s[p];
s[p]=s[c];
s[c]=aux;
p=c;
c=p<<1;
}
else{break;}
}
}
}
int main(){
FILE *f=fopen("heavymetal.in","r");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++){
fscanf(f,"%d %d",&s[i].a,&s[i].b);
}
fclose(f);
k=n;
sort();
for(i=1;i<=n;i++){
val=s[i].a;
v[i]=v[i-1];
p=0;
u=i;
while(p<=u){
mij=(p+u)/2;
if(s[mij].b<=val)
p=mij+1;
else
u=mij-1;
}
if( (v[u]+(s[i].b-s[i].a)) > v[i] )
v[i]=v[u]+(s[i].b-s[i].a);
}
FILE *g=fopen("heavymetal.out","w");
fprintf(g,"%d",v[n]);
fclose(g);
return 0;
}