Pagini recente » Cod sursa (job #1433062) | Cod sursa (job #2497078) | Cod sursa (job #2464049) | Cod sursa (job #1986010) | Cod sursa (job #435697)
Cod sursa(job #435697)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int h,u, rest;
typedef struct height_weight_fruit {
int height;
int weight;
} fruit;
int tree_level (int height) {
return (height-rest)/u;
}
bool compare_fruits (fruit f1, fruit f2) {
if (tree_level(f1.height) == tree_level(f2.height))
return (f1.weight > f2.weight);
return (tree_level(f1.height) > tree_level(f2.height));
}
int left (int i) {
int son = 2*i +1;
return son;
}
int right (int i) {
int son = 2*i +2;
return son;
}
int parent (int i, int n) {
int father = (i-1)/2;
if (father < 0)
return -1;
return father;
}
void restore_heap (int pos, int *v, int n) {
int desc;
while (1) {
int min = v[pos];
if ( left(pos) < n && v[left(pos)] < min )
min = v[left(pos)];
if ( right(pos) < n && v[right(pos)] < min )
min = v[right(pos)];
if (min == v[pos])
return ;
if ( left(pos) < n && min == v[left(pos)]) {
desc = left(pos);
}
else {
desc = right(pos);
}
// interschimb valori pos, desc
int aux = v[pos];
v[pos] = v[desc];
v[desc] = aux;
pos = desc;
}
}
void make_heap (int *v, int n) {
for (int i=n/2; i>=0; i--) {
restore_heap(i, v, n);
}
}
int get_min (int *heap, int *n){
int min = heap[0];
heap[0] = heap[*n-1];
heap[*n-1] = min;
(*n) --;
restore_heap (0, heap, *n);
return min;
}
int main() {
FILE *in, *out;
in = fopen ("gutui.in", "r");
out = fopen ("gutui.out", "w");
int n;
fruit *quince;
fscanf (in, "%d %d %d", &n, &h, &u);
rest = h%u + 1;
quince = (fruit *)calloc(n, sizeof(fruit));
for (int i=0; i<n; i++) {
fscanf (in, "%d %d", &(quince[i].height), &(quince[i].weight));
}
vector<fruit> fruits (quince, quince+n);
vector<fruit>::iterator it;
sort (fruits.begin(), fruits.end(), compare_fruits);
for (it = fruits.begin (); it != fruits.end(); it++){
printf ("%d %d \n", (*it).height, (*it).weight);
}
it = fruits.begin();
while (it != fruits.end() && (*it).height > h) {
it ++;
}
int contor, index=0, max=0, max2;
int *picked = (int *)calloc(n, sizeof(int));
while (it != fruits.end()) {
// pentru fiecare nivel
picked[index] = (*it).weight;
max2 = picked[index++];
int level = tree_level((*it).height);
contor = tree_level(h) - level;
it ++;
int i=0;
while (it != fruits.end() && i< contor && tree_level((*it).height) == level) {
picked[index++] = (*it). weight;
it ++;
i++;
}
make_heap (picked, index);
for (int j=0; j< index - contor -1; j++) {
get_min (picked, &index);
}
printf("level : %d\n", contor);
for (int j=0; j<= contor; j++) {
printf("%d ", picked[j]);
}
printf("\n");
while (it != fruits.end() && tree_level((*it).height) == level)
it++;
}
make_heap (picked, index);
/*ATENTIE LA CATE SE CULEG!!*/
int sum=0;
for (int i=0; i<index; i++) {
int nr = picked[i];
sum = sum +nr;
}
fprintf(out, "%d\n", sum);
fclose (in); fclose (out);
return 0;
}