Cod sursa(job #463734)
// Voiculescu Rafaela 321CA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <values.h>
#include <algorithm>
#include <vector>
using namespace std;
#define Max MAXINT
typedef struct{
int h; //inaltimea crengii pe care se afla gutuia
int g; //greutatea gutuii
} gutuie;
int compara(void* a,void* b)
{
unsigned int val_a,val_b;
val_a=(*((gutuie *)a)).h;
val_b=(*((gutuie *)b)).h;
if(val_a<val_b)
return 1;
else
if(val_a>val_b)
return -1;
else
return 0;
}
int main()
{
//deschidere fisier de intrare, respectiv fisier de iesire
FILE *in,*out;
in=fopen("gutui.in","r");
out=fopen("gutui.out","w");
//citim numarul de gutui, inaltimea maxima si cu cat se ridica crengile
int N,H,U;
int i,j,ord,size,ales;
unsigned long suma=0;
fscanf(in,"%d%d%d",&N,&H,&U);
//alocam spatiu
gutuie *date;
date=(gutuie*) calloc(N,sizeof(gutuie));
//citim datele despre fiecare creanga
for(i=0;i<N;i++)
{
fscanf(in,"%d%d",&date[i].h,&date[i].g);
//daca deja e prea sus
if(date[i].h>H)
{
i--;
N--;
}
}
//sortam descrescator dupa inaltimea la care se afla crengile
qsort(date,N,sizeof(gutuie),(__compar_fn_t)&compara);
vector<int> v;
//cream un heap in care vom retine practic solutia (greutatile gutuilor alese pentru a obtine suma maxima)
make_heap(v.begin(),v.end());
for(i=0;i<N;i++)
{
//calculam pentru fiecare gutuie numarul sau de ordine maxim (adica dupa cate alte gutui
//ar putea fi culeasa fara ca inaltimea crengii pe care se afla sa depaseasca valoarea H
ord=(H-date[i].h)/U+1;
if(ord<N)
ales=ord;
else
ales=N;
size=(int)v.size();
//se adauga la heap atatea elemente de Max cat e diferenta intre numarul de ordine maxim al
//gutuii si capacitatea actuala a heap-ului (in caz ca incare cea din urma e < decat prima)
//sau cat e diferenta intre numarul total de gutui si capacitatea heap-ului (in caz ca nr de
//ordine > N) -> pentru ca altfel ar putea fi risc de a se incerca alocarea unui vector de
//2 milioane de elemente.
for(j=0;j<(ales - size);j++)
{
v.push_back(Max);
push_heap(v.begin(),v.end());
}
//scoatem valoarea maxima din heap si daca e mai mare decat Max-greutatea gutuii pentru care analizam
//o inlocuim cu aceasta
if(v[0]>(Max-date[i].g))
{
pop_heap(v.begin(),v.end());
v.pop_back();
v.push_back(Max-date[i].g);
push_heap(v.begin(),v.end());
}
}
//facem suma tuturor greutatilor gutuilor alese (tinand cont ca greutatea unei gutui e Max-v[i]
//deoarece asa a fost retinuta in heap pentru a se putea scoate elementul maxim
for(i=0;i<(int)v.size();i++)
suma+=(Max-v[i]);
fprintf(out,"%lu\n",suma);
//eliberam spatiul alocat
free(date);
//inchidem fisierele
fclose(in);
fclose(out);
return 0;
}