Cod sursa(job #436775)

Utilizator stoikStoica George Cristian stoik Data 8 aprilie 2010 23:06:37
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.24 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

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

long u;
long h;

typedef struct
{
  long l;
  long poz;
} level;

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 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 nr = 0;
  long max = -1;

  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 > max) 
      max = a[i].l;
  }
  
  qsort (a, n, sizeof(gutui), compare);
  long t=-1;
  for (i=0; i<n; i++)
    if (a[i].l>t)
      {
        nr++;
        t = a[i].l;
      }
 /* for (i=0; i<n; i++)
    printf("**%ld %ld %ld\n",a[i].h,a[i].g, a[i].l);
  printf("^^^^ %ld %ld\n\n", max, nr);
  */
  
  
  level * b = (level *) calloc (nr, sizeof(level));
  long l = -1;
  long j = 0;
  
  for (i=0; i<n; i++)
    if (a[i].l > l)
      {
        b[j].l = a[i].l;
        b[j].poz = i;
        j++;
        l = a[i].l;
      }
      
  //for (i=0; i<nr; i++)
    //printf("*%ld  %ld\n", b[i].l, b[i].poz);
  long *heap = (long *) calloc(max, sizeof(long));
  //heap[0] = a[0].g
  //make_heap(heap, heap+1);
  long size = 0;

  for (i = 0; i<nr; i++)
  {
    long l = b[i].l;
    long j = b[i].poz;
    int ok = 1;
    while (ok)
      {
        if (j-b[i].poz>l) break; 
        if (a[j].l == l)
	{
	  if (size <l+1)
	    {
	      heap[size++] = -a[j].g;
	      push_heap(heap, heap+size);	      
	    }
	  else
	    if (-a[j].g < heap[0])
	      {
	        pop_heap(heap,heap+size);
	        heap[size-1] = -a[j].g;
	        push_heap(heap,heap+size);
	      }
	 }
        else ok = 0;
        j++;
      }
  }
  for (i=0; i<size; i++)
    {
      //printf("---%ld\n",heap[i]);
      g+= (-heap[i]);
    }  
  fprintf(ff,"%ld",g);
  
  fclose(f);

  fclose(ff);
  return 0;
}