Cod sursa(job #439514)

Utilizator RaduXRadu Calin RaduX Data 11 aprilie 2010 16:45:51
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { //STRUCTURA GUTUI
  long hg;
  long gg;
  long lg;
} gutui;
 
long u;
long h;

int mycompare(const void* a, const void* b)
{ //FUNCTIE SORTARE DUPA GREUTATE PT QSORT
  gutui* ac=(gutui *)a;
  gutui* bc=(gutui *)b;
  return ((bc->gg)-(ac->gg));
}
 
int main()
{
  long n,j,i,maxl=0,gmax=0;
  FILE *f = fopen("gutui.in","r");
  FILE *g = fopen("gutui.out","w");
   
  fscanf(f,"%ld %ld %ld",&n, &h, &u);
  gutui *a = (gutui *)calloc(n,sizeof(gutui));
  
  for (i=0; i<n; i++) { //CITIM GUTUILE SI ALFAM NIVELUL MAXIM 
     fscanf(f,"%ld %ld",&a[i].hg, &a[i].gg);
     a[i].lg = (long)((h-(a[i].hg))/u);
     if (a[i].lg > maxl) maxl = a[i].lg;
  }
      
  qsort (a, n, sizeof(gutui), mycompare); //SORTAM DUPA GREUTATE

  long *sched = (long*)calloc(maxl+1, sizeof(long)); //VECTORUL DE SCHEDULE
  
  for (i = 0; i<n; i++)
    for (j=a[i].lg; j>=0; j--) 
       if (sched[j] == 0) {
          sched[j] = a[i].gg; //UMPLEM VECOTORUL DE SCHEDULE
          break;
       }
             

  for (i=0; i<=maxl; i++) 
    gmax+=sched[i]; //GREUTATEA MAXIMA PE CARE O POATE DUCE GIGEL
  
  fprintf(g,"%ld",gmax);
  fclose(g);
  //COMPLEXITATE MAXIMA PB -> N*NIVELUL MAXIM
  return 0;
}