Cod sursa(job #439384)

Utilizator RaduXRadu Calin RaduX Data 11 aprilie 2010 15:49:17
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int mycompare(const void* a, const void* b)
{
  gutui* a1=(gutui *)a;
  gutui* b1=(gutui *)b;
  return ((b1->gg)-(a1->gg));
}
 
int main()
{
  long n,j,i,maxl=0,nrg=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++) {
     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);

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

  for (i = 0; i<maxl+1; i++) 
    nrg+=sched[i];
  
  fprintf(g,"%ld",nrg);
  fclose(g);

  return 0;
}