#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* Structura heap_vector_struct retine max-heap-ul avand drept camp un vector de intregi, si alte trei campuri
* reprezentand capacitatea, dimensiunea heap-ului, respectiv nivelul pe care se afla fructele retinute in heap-ul respectiv .
*/
typedef struct heap_vector_struct
{
int *values;
int dimVect;
int capVect;
int niv;
} HeapVector;
// Strunctura gutui retine entitatea gutuie cu campurile h - inaltime si g - greutate
typedef struct gutui{
int h;
int g;
} gutui;
// Functie care returneaza indexul descendentului stang al unui nod din heap
int DescS(HeapVector *h, int poz){
if ((2*poz+1)>=h->dimVect)
return -1;
else
return (2*poz+1);
}
// Functie care returneaza indexul descendentului drept al unui nod din heap
int DescD(HeapVector *h, int poz) {
if ((2*poz+2)>=h->dimVect)
return -1;
else
return (2*poz+2);
}
// Functie care returneaza indexul parintelui unui nod din heap
int Parinte(HeapVector *h, int poz)
{
if (poz==0)
return -1;
else
return (poz-1)/2;
}
// Functie care aloca memorie pentru o entitate heap .
HeapVector* CV(int capVect){
HeapVector *h;
h=(HeapVector*)malloc(sizeof(HeapVector));
h->values=(int*)calloc(capVect,sizeof(int));
h->dimVect=0;
h->capVect=capVect;
h->niv=-1;
return h;
}
// Functie care elibereaza memoria alocata unei entitati heap
void ElibereazaVector(HeapVector *h)
{
free(h->values);
free(h);
}
// Functie care coboara o valoare in heap astfel incat heap-ul sa-si pastreze calitatile in ceea ce priveste relatiile dintre chei
void CoboaraValoare(HeapVector *h, int poz)
{
int pozdesc=0;
int valmax,aux;
for (;;)
{
valmax=h->values[poz];
if (DescS(h,poz)!=-1)
if (h->values[DescS(h,poz)]>valmax)
valmax=h->values[DescS(h,poz)];
if (DescD(h,poz)!=-1)
if (h->values[DescD(h,poz)]>valmax)
valmax=h->values[DescD(h,poz)];
if (valmax==h->values[poz])
return;
if (DescS(h,poz)!=-1&&valmax==h->values[DescS(h,poz)])
pozdesc=DescS(h,poz);
else if (DescD(h,poz)!=-1)
pozdesc=DescD(h,poz);
aux=h->values[pozdesc];
h->values[pozdesc]=h->values[poz];
h->values[poz]=aux;
poz=pozdesc;
}
}
// Functie care urca o valoare in heap astfel incat heap-ul sa-si pastreze calitatile in ceea ce priveste relatiile dintre chei
void UrcaValoare(HeapVector *h,int poz){
int aux;
while (poz>0&&h->values[poz]>h->values[Parinte(h,poz)]){
aux=h->values[Parinte(h,poz)];
h->values[Parinte(h,poz)]=h->values[poz];
h->values[poz]=aux;
poz=Parinte(h,poz);
}
}
// Functie care returneaza elementul cu cheia maxima din heap
int Maxim(HeapVector *h){
assert(h->dimVect>0) ;
return h->values[0];
}
// Functie care extrage elementul maxim din heap astfel incat heap-ul sa-si pastreze calitatile in ceea ce priveste relatiile dintre chei
int ExtrageMaxim(HeapVector *h){
assert(h->dimVect>0);
int max,aux;
max=h->values[0];
aux=h->values[0];
h->values[0]=h->values[h->dimVect-1];
h->values[h->dimVect-1]=aux;
h->dimVect--;
CoboaraValoare(h,0);
return max;
}
// Functie care adauga o valoare in heap astfel incat heap-ul sa-si pastreze calitatile in ceea ce priveste relatiile dintre chei.
// In cazul in care heap-ul ajunge la capacitate maxima se aloca un spatiu de memorie de capacitate dubla
void AdaugaValoare(HeapVector *h,int val){
if (h->dimVect==h->capVect){
h->capVect=2*h->capVect;
h->values=(int*)realloc(h->values,h->capVect*sizeof(int));
}
h->dimVect++;
h->values[h->dimVect-1] = val;
UrcaValoare(h,h->dimVect-1);
}
// Functie care returneaza dimensiunea heap-ului
int size(HeapVector *h){
return h->dimVect;
}
// Functie care partitioneaza un vector de structuri gutui, fiind folosita pentru a sorta vectorul prin tehnica quicksort
int partitie(gutui x[],int s,int d){
int piv=x[s].h;
int j=d+1,i=s-1;
gutui aux;
while(1){
do{j--;} while(x[j].h>piv);
do{i++;} while(x[i].h<piv);
if (i<j){
aux=x[i];
x[i]=x[j];
x[j]=aux;
}
else return j;
}
}
// functie care sorteaza un vector de structuri gutui in ordinea descrescatoare a inaltimilor folosind tehnica quicksort
void quicksort(gutui x[],int s,int d){
if(s<d){
int p=partitie(x,s,d);
quicksort(x,s,p);
quicksort(x,p+1,d);
}
}
int main(){
FILE *f=fopen("gutui.in","r");
FILE *g=fopen("gutui.out","w");
int u,h,n,i,j=1,max,poz,s=0;
int k=h/u+1,niv,nr=-1,r=-1;
gutui *fr;
HeapVector** zona;
// citire date din fisierul de intrare
fscanf(f,"%d%d%d",&n,&h,&u);
fr=(gutui*)malloc(n*sizeof(gutui));
for (i=0;i<n;i++)
fscanf(f,"%d%d",&fr[i].h,&fr[i].g);
//sortarea vectorului de structuri gutui in ordinea descrescatoare a inaltimilor
quicksort(fr,0,n-1);
//formarea unui vector de heap-uri in care se retin greutatile gutuilor aflate pe acelasi nivel in ordine descrescatoare;un nivel se
//prin faptul ca toate fructele de pe nivelul respectiv devin la un moment dat inaccesibile simultan
zona=(HeapVector**)calloc(k,sizeof(HeapVector*));
for (i=0;i<n;i++){
niv=k-1-(h-fr[i].h)/u;
if(r==niv)
AdaugaValoare(zona[nr],fr[i].g);
else{
nr++;
zona[nr]=CV(1);
AdaugaValoare(zona[nr],fr[i].g);
zona[nr]->niv=niv;
r=niv;
}
}
nr++;
j=1;
//la fiecare pas k se alege gutuia de greutate maxima aflata pe nivelurile 1..k; dupa un numar de h/u+1 alegeri nicio gutuie nu mai
//este accesibila
while (1){
max=-1;
poz=-1;
for (i=0;i<nr;i++)
if(zona[i]->niv>=j)
break;
else
if (size(zona[i])!=0&&Maxim(zona[i])>max){
max=Maxim(zona[i]);
poz=i;
}
if (poz!=-1){
s+=max;
ExtrageMaxim(zona[poz]);
}
j++;
if (j==k+1) break;
}
//se elibereaza memoria alocata pentru retinerea fructelor
for (i=0;i<nr;i++)
ElibereazaVector(zona[i]);
free(fr);
free(zona);
//se scrie rezultatul obtinut in fisierul de iesire
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}