Cod sursa(job #463577)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 16 iunie 2010 14:29:36
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 3.14 kb
//STOICA GEORGE CRISTIAN 325CA

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;


//structura pentru gutui cu inaltimea, greutatea si nivelul pe care se afla
typedef struct
{
  long h;
  long g;
  long l;
} gutui;

long u;
long h;

//structura pentru retinerea pozitiei la care incepe fiecare nivel si numarul nivelului
typedef struct
{
  long l;
  long poz;
} level;

//ordonez vectorul de gutui in functie de nivel, si pe acelasi nivel in functie de greutate
int compare(const void* a, const void* b)
{
  gutui* a1 = (gutui *)a;
  gutui* b1 = (gutui *)b;
  
  long k = a1->l;
  long t = b1->l;

  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 maxLevel = -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);  //retin nivelul pe care se afla gutuia
    if (a[i].l > maxLevel) 
      maxLevel = a[i].l; //retin nivelul maxim pe care se gaseste minim o gutuie
  }
  
  qsort (a, n, sizeof(gutui), compare); //ordonez vector a cu functia compare
  long t=-1;
  for (i=0; i<n; i++)
    if (a[i].l>t)
      {
        nr++; //calculez numarul total de nivele pe care se gasesc gutui
        t = a[i].l;
      }

  
  level * b = (level *) calloc (nr, sizeof(level)); //vectorul care imi retine pentru fiecare nivel pe care se afla
					 //minim o gutuie, nivelul respectiv si pozitia sa de inceput in vectorul de gutui 
  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;  //completez vectorul b
        j++;
        l = a[i].l; 
      }
  
  //heapul in care voi avea maxim maxLevel+1 gutui, cele care vor fi culese (primul nivel fiind 0)
  long *heap = (long *) calloc(maxLevel+1, sizeof(long));

  //marimea heapului, care la un nivel L poate fi maxim L+1 
  long size = 0;
  
  for (i = 0; i<nr; i++)
  {
    long l = b[i].l;
    long j = b[i].poz;
    int ok = 1;
    
    //pentru fiecare nivel L, adaug in heap pana cand am L+1 elemente,
    //pentru urmatoarele gutui de pe nivelul respectiv, le compar cu varful heapului si , in caz
    //ca sunt mai bune, scot varful heapului, si adaug gutuia respectiva in heap, cu actualizarea acestuia
    while (ok)
      {
        if (j-b[i].poz>l) break; //pentru un nivel L, ma intereseaza doar primele L+1 gutui in ordinea descrescatoare a greutatii
        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++)    
      g+= (-heap[i]); //la sfarsit adaug gutuile din heap la greutatea totala

  fprintf(ff,"%ld",g);
  
  fclose(f);

  fclose(ff);
  return 0;
}