Pagini recente » Cod sursa (job #21507) | Cod sursa (job #2989378) | Cod sursa (job #1259756) | Cod sursa (job #1379565) | Cod sursa (job #439114)
Cod sursa(job #439114)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef struct GUT{
int h;//inaltime la care se afla gutuia
int g; // greutatea gutuii
}GUT;
int compare (const void * a, const void * b){//functie de comparare pe care o utilizez la sortarea dupa inaltime
return ( *(int*)b - *(int*)a );
}
int main(){
FILE* fisierin=fopen("gutui.in","r");
FILE* fisierout=fopen("gutui.out","w");
int n,h,u,i;
GUT* vec;
priority_queue< int, vector<int>, greater<int> > Q;
fscanf(fisierin,"%d ",&n);
fscanf(fisierin,"%d ",&h);
fscanf(fisierin,"%d ",&u);
vec=(GUT*)malloc(n*sizeof(GUT));//vector de gutui
for(i=0;i<n;i++){
fscanf(fisierin,"%d",&vec[i].h);
fscanf(fisierin,"%d",&vec[i].g);
}
qsort (vec, n, sizeof(GUT), compare);//sortez descrescator dupa inaltime
Q.push(vec[0].g);
h=h-u;//se ridica celelalte gutui cu u unitati
for(i=1;i<n;i++){ //parcurg restul de gutui
if(vec[i].h<=h){ //verific daca mai pot culege
Q.push(vec[i].g);
h=h-u;
}
else{// daca in Q am o gutuie mai usoara o inlocuiesc daca nu trec la urmatoarea
if(vec[i].g > Q.top()){
Q.pop();
Q.push(vec[i].g);
}
}
}
int cant_max=0;//cantiatea maxima de gutui pe care o pot culege
while(Q.empty()!=0){
cant_max=cant_max+Q.top();//calculez cantitatea maxima de gutui
Q.pop();
}
fprintf(fisierout,"%d \n",cant_max);
fclose(fisierin);
fclose(fisierout);
return 0;
}