Cod sursa(job #437759)

Utilizator dragos_dDiaconescu Dragos dragos_d Data 10 aprilie 2010 01:21:37
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.9 kb
#include<stdio.h>
#include<stdlib.h>

#define N 100000
typedef struct gutui
{
   int inaltime;
   int greutate;
   int moment;   //momentul la care poate fi culeasa
}gutuie;
int compare(const void *p1,const void *p2)  //functia de comparare folosita pentru qsort pentru a sorta in functie de greutate
{
   gutuie *g1,*g2;
   g1=(gutuie*)p1; 
   g2=(gutuie*)p2;        
   return g2->greutate-g1->greutate;
}  
int maxim(int a,int b)
{
   if(a>b)
     return a;
   return b;
}
int culege[N];  //vectorul in care avem 1 daca la momentul i a fost culeasa o gutuie si 0 daca momentul este liber
int main()
{
  int i,n,h,u;
  int max=0;
  int aux,maxgutui=0; //maxgutui reprezinta numarul maxim de gutui ce pot fi culese
  int nrcules=0; //nr de gutui culese
  FILE *in,*out;
  in=fopen("gutui.in","r");
  out=fopen("gutui.out","w");
  gutuie gut[N];
  fscanf(in,"%d",&n);
  fscanf(in,"%d",&h);
  fscanf(in,"%d",&u);
  for(i=0;i<n;i++){
        fscanf(in,"%d",&gut[i].inaltime);
        fscanf(in,"%d",&gut[i].greutate);
        gut[i].moment=(h-gut[i].inaltime)/u; //calculam momentul maxim la care poate fi culeasa gutuia
        if(gut[i].moment > maxgutui)
                 maxgutui=gut[i].moment;
  }
  qsort(gut,n,sizeof(gutuie),compare);
  for(i=0;i<n;i++){
     if(culege[gut[i].moment]==0){   //plasam gutuia la momentul maxim cand trebuie culeasa
            culege[gut[i].moment]=1;
            max=max+gut[i].greutate;nrcules++;
     } 
     else{  
       if(nrcules <= maxgutui){
                                    //daca acest moment este ocupat deja cautam un moment liber mai devreme pentru a o culege
         aux=gut[i].moment;         //culegem gutuia la primul moment gasit liber
         while(aux>=0 && culege[aux]==1)
                 aux--;
         if(aux>=0){
            max=max+gut[i].greutate;
            culege[aux]=1;nrcules++;
          }
      }     
     }
 }
    
  fprintf(out,"%d",max);
  return 0;
}