Cod sursa(job #461729)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 8 iunie 2010 14:22:23
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>

long int dist[100005],lana[100005],T[100005],sol[100000];
long int N,X,L;

long int poz(long int li,long int ls){
   long int c,i=1,j=0;
   while(li<ls){
     if(lana[li]<lana[ls]){
	  /*c=dist[li];
	  dist[li]=dist[ls];
	  dist[ls]=c;
	 */
	  c=T[li];
	  T[li]=T[ls];
	  T[ls]=c;

	  c=lana[li];
	  lana[li]=lana[ls];
	  lana[ls]=c;

	  c=i;
	  i=-j;
	  j=-c;
       }
   li+=i;
   ls+=j;
   }
   return li;
}

void sortare(long int li, long int ls){
   long int k;
   if(li<ls){
     k=poz(li,ls);
     sortare(li,k-1);
     sortare(k+1,ls);
   }
}

long int transa(long int d){
   long int dif=X-d;
   return dif/L;
}

/*int loc(long int li, long int ls, int transa){

}*/


int main(){
 
  long int i,j;
  long int k=0;
  FILE *fin=fopen("lupu.in","r");
  fscanf(fin,"%ld%ld%ld",&N,&X,&L);
  for(i=0;i<N;i++){
    fscanf(fin,"%ld%ld",&dist[k],&lana[k]);
    if(dist[k]<=X){
       T[k]=transa(dist[k]);
       k++;
    }
    //indice[i]=i+1;
  }
  N=k;
  //sortez decrescator dupa lana
  sortare(0,N-1);
  //o afisare
 
  /* for(i=0;i<N;i++){
     printf("%2d ",i+1);
  }
  printf("\n");
   
  for(i=0;i<N;i++){
     printf("%2d ",lana[i]);
  }
  printf("\n");

  for(i=0;i<N;i++){
     printf("%2d ",T[i]);
  }
  printf("\n");
  */
  //parcurg vectorul...
  int ok;
   long int nr_oii=0;
   long long int g=0;
   for(i=0;i<N;i++){
     ok=1; 
     for(j=T[i];j>=0 &&ok;j--){
     if(sol[j]==0){
        ok=0;
        nr_oii++;
        //printf("aleg oaia");
        //printf("%d\n",i+1);
        sol[j]=1;
        g+=lana[i];
     }
     }
   }
   FILE *fout=fopen("lupu.out","w");
   fprintf(fout,"%ld\n",g);
    
}