Cod sursa(job #436332)

Utilizator stoikStoica George Cristian stoik Data 8 aprilie 2010 15:01:07
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.17 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>

typedef struct
{
  long h;
  long g;
  long l;
} gutui;

long u;
long h;

int compare(const void* a, const void* b)
{
  gutui* a1 = (gutui *)a;
  gutui* b1 = (gutui *)b;
  

  return (-(a1->g) + (b1->g));
}

int main()
{
  long n;
  FILE *f = fopen("gutui.in","r");
  FILE *ff = fopen("gutui.out","w");
  
  fscanf(f,"%ld %ld %ld",&n, &h, &u);
  long i;
  //long g = 0;  
  gutui *a = (gutui *)calloc(n,sizeof(gutui));
  long maxLevel = 0;
  for (i=0; i<n; i++)
  {
    fscanf(f,"%ld %ld",&a[i].h, &a[i].g);
    a[i].l = (long)((h-(a[i].h))/u);
    if (a[i].l > maxLevel) maxLevel = a[i].l;
  }
   
  qsort (a, n, sizeof(gutui), compare);
  /*for (i=0; i<n; i++)
    printf("**%ld %ld %ld\n",a[i].h,a[i].g, a[i].l);
  printf("\n");
  */
  long *sch = (long*)calloc(maxLevel+1, sizeof(long));
  long k;
  
  for (i = 0; i<n; i++)
    for (k = a[i].l; k >=0; k--)
      {
        if (sch[k] == 0) 
        {
	sch[k] = a[i].g;
	break;
        }
      }
  long g = 0;
  for (i = 0; i<maxLevel+1; i++)
  {
    g+=sch[i];
    //printf("****%ld\n", sch[i]);
  }
  fprintf(ff,"%ld",g);
  fclose(f);
  fclose(ff);

  return 0;
}