Cod sursa(job #435026)

Utilizator VladTVlad Tudose VladT Data 6 aprilie 2010 20:15:22
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.34 kb
#include <stdio.h>
#include <stdlib.h>
#define ALLOC(n,type) (type*)malloc(n*sizeof(type))
#define LEVEL(g,H,U) ((H-g.inaltime)/U)


typedef struct{
        int greutate;
        int inaltime;
}gutuie;


int compare (const void * a, const void * b)
{
    gutuie *g1=(gutuie *)a;
    gutuie *g2=(gutuie *)b;
  return (g2->inaltime) - (g1->inaltime);
}


int main ()
{
  int N,H,U,i,max,sum,rounds,j,pick;
  FILE* in,*out;
  gutuie *g;
  in=fopen("gutui.in","r");
  fscanf(in,"%d %d %d\n",&N,&H,&U);
  g=ALLOC(N,gutuie);
  rounds=H;
  for(i=0;i<N;i++)
   fscanf(in,"%d %d\n",&g[i].inaltime,&g[i].greutate);
  fclose(in);
  qsort (g, N, sizeof(gutuie), compare);
  rounds=(H-g[N-1].inaltime)/U + 1;
  sum=0;
  for(i=0;i<rounds;i++)
  {
    j=0;
    while(g[j].greutate==-1)
    j++;
    gutuie first=g[j];
    max=first.greutate;
    pick=j;
    j=1;
    while(j<N&&((LEVEL(first,H,U)==LEVEL(g[j],H,U))||g[j].greutate==-1))
    {
     if(g[j].greutate>max)
         {
          max=g[j].greutate;
          pick=j;  
         }
      g[j].inaltime+=U;
     j++;
    }
    sum+=max;
    g[pick].greutate=-1;
   while(j<N)
             g[j++].inaltime+=U;                       
  }
  out=fopen("gutui.out","w");
  fprintf(out,"%d",sum);
  fclose(out);                   
  //printf("%d\n",sum);
  return 0;
}