Cod sursa(job #150670)

Utilizator katakunaCazacu Alexandru katakuna Data 7 martie 2008 11:17:34
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#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;
}