Pagini recente » Cod sursa (job #2587545) | Cod sursa (job #802807) | Cod sursa (job #2534344) | Cod sursa (job #1680242) | Cod sursa (job #440015)
Cod sursa(job #440015)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std; //pentru folosirea heap-ului
FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,rest;
long long int max_weight;
typedef struct {
int height; //structura gutuie ce contine inaltimea si greutatea
int weight;
} gutuie;
gutuie tree[100001]; //vector de gutui
int compare (const void * a, const void * b)
{
//if( ( (*(gutuie*)a).height - (*(gutuie*)b).height ) == 0 ) //functie de comparatie
// return ( (*(gutuie*)b).weight - (*(gutuie*)a).weight ); //pentru a ordona crescator
//else
return ( (*(gutuie*)a).height - (*(gutuie*)b).height ); //gutuile dupa inaltime
}
main() {
int i, j;
vector<int> coll;
make_heap (coll.begin(), coll.end());
fs = fopen("gutui.in","r");
fd = fopen("gutui.out","w");
if (fs==NULL) {
printf("Eroare");
exit (1);
}
if (fd==NULL) {
printf("Eroare");
exit (1);
}
//maxh=0;
fscanf(fs,"%i",&N);
fscanf(fs,"%i",&max_height);
fscanf(fs,"%i",&height_inc);
rest = max_height%height_inc;
max_height=max_height/height_inc;
for(i=0;i<N;i++){
fscanf(fs,"%i",&x);
if(x%height_inc>rest)
tree[i].height = x / height_inc + 1;
else
tree[i].height = x / height_inc;
fscanf(fs,"%i",&x);
tree[i].weight = x;
}
j=0;
max_weight=0;
qsort(tree,N,sizeof(gutuie),compare);
for(i=0;i<=max_height;i++)
{
while(i == tree[j].height){
coll.push_back (tree[j].weight);
push_heap (coll.begin(), coll.end());
j++;
}
if(coll.size()>0){
max_weight = max_weight + coll.front();
pop_heap(coll.begin(), coll.end());
coll.pop_back();
}
}
fprintf(fd,"%lli",max_weight);
fclose(fs);
fclose(fd);
}