Pagini recente » Cod sursa (job #1986472) | Cod sursa (job #784779) | Cod sursa (job #629913) | Cod sursa (job #3124956) | Cod sursa (job #435618)
Cod sursa(job #435618)
#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 max = v[pos];
if ( left(pos) < n && v[left(pos)] > max )
max = v[left(pos)];
if ( right(pos) < n && v[right(pos)] > max )
max = v[right(pos)];
if (max == v[pos])
return ;
if ( left(pos) < n && max == 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_max (int *heap, int *n){
int max = heap[0];
heap[0] = heap[*n-1];
heap[*n-1] = max;
(*n) --;
restore_heap (0, heap, *n);
return max;
}
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();
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++;
}
while (it != fruits.end() && tree_level((*it).height) == level)
it++;
}
make_heap (picked, index);
int sum=0;
for (int i=0; i<contor+1; i++) {
//printf("%d \n", get_max(picked, &index));
sum += get_max(picked, &index);
}
fclose (in); fclose (out);
return 0;
}