Cod sursa(job #435286)

Utilizator stoikStoica George Cristian stoik Data 7 aprilie 2010 10:55:57
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 1.65 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
typedef struct
{
  long h;
  long g;
  long l;
  long poz;
} gutui;

long u;
long h;

int compare(const void* a, const void* b)
{
  gutui* a1 = (gutui *)a;
  gutui* b1 = (gutui *)b;
  
  long k = a1->l;
  long t = b1->l;
  //printf("%ld %ld (%ld) (%ld)\n",k, t, a1->h, b1->h);
  if (k == t) return (-(a1->g) + (b1->g));
    else return (k - t);
}

int compare1(const void* a, const void* b)
{
  gutui* a1 = (gutui *)a;
  gutui* b1 = (gutui *)b;
  
  long k = a1->l - a1->poz;
  long t = b1->l - b1->poz;
  //printf("%ld %ld (%ld) (%ld)\n",k, t, a1->h, b1->h);
  if (k == t) return (-(a1->g) + (b1->g));
    else return (k - t);
}

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;
  gutui *a = (gutui *)calloc(n,sizeof(gutui));

  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);

  }

  qsort (a, n, sizeof(gutui), compare);

  a[0].poz = 0;
  
  for (i=1 ; i<n ; i++)
    {
      if (a[i].l == a[i-1].l) a[i].poz = a[i-1].poz + 1;
      else a[i].poz = 0;      
    }
    
  qsort (a, n, sizeof(gutui), compare1);
  
  /*for (i=0; i<n; i++)
    printf("**%ld %ld %ld %ld\n",a[i].h,a[i].g, a[i].l, a[i].poz);
  printf("\n");
  */
  
  //long g = a[0].g;
  //long k = a[0].l - a[0].poz;
  long g =0;
  long t = 0;
  
  for (i = 0; i<n; i++)
    if (a[i].l - a[i].poz - t >= 0)
    {
      //k = a[i].l - a[i].poz;
      g += a[i].g;
      t+=1;
    }
  fprintf(ff,"%ld",g);
  
  //printf("%d %d %d %d\n",n,h,u,a[n-1].g);
  fclose(f);
  fclose(ff);
  return 0;
}