Pagini recente » Cod sursa (job #2463621) | Cod sursa (job #777126) | Cod sursa (job #2463408) | Cod sursa (job #1360634) | Cod sursa (job #437605)
Cod sursa(job #437605)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct quince_fruit {
int height;
int weight;
} qfruit;
int h, u;
unsigned int get_level (int height) {
return (h - height)/u;
}
bool compare_quinces (qfruit q1, qfruit q2) {
if (get_level(q1.height) == get_level(q2.height))
return (q1.weight > q2.weight);
return (get_level(q1.height) < get_level(q2.height));
}
//return true if fisrt goes before second
bool min_heap_compare (qfruit q1, qfruit q2) {
return (q1.weight > q2.weight);
}
int main() {
FILE *in, *out;
in = fopen ("gutui.in", "r");
out = fopen ("gutui.out", "w");
int n;
qfruit *data;
fscanf (in, "%d %d %d", &n, &h, &u);
data = (qfruit *) calloc (n, sizeof(qfruit));
for (int i=0; i<n; i++) {
fscanf(in, "%d %d", &(data[i].height), &(data[i].weight));
}
vector<qfruit> fruit (data, data+n);
vector<qfruit>::iterator it;
// sortare dupa nivel si greutate
sort (fruit.begin(), fruit.end(), compare_quinces);
//TODO afisare
for (it=fruit.begin(); it!=fruit.end(); it++) {
printf("%d %d\n", (*it).height, (*it).weight);
}
printf("\n");
vector<qfruit> fruitheap;
vector<qfruit>::iterator it2;
it = fruit.begin();
while (it != fruit.end()) {
unsigned int l = get_level ((*it).height) +1 ;
//printf("nivel %d\n", l);
unsigned int added =1;
int min = 0;
if (fruitheap.size() != 0) {
min = (fruitheap.front()).weight;
}
while (get_level ((*it).height) +1 == l && it!=fruit.end()) {
if (added <= l) {
fruitheap.push_back (*it);
push_heap (fruitheap.begin(), fruitheap.end(), min_heap_compare);
added ++;
}
//printf ("%d \n", (*it).height);
it ++;
}
while (fruitheap.size() > l) {
pop_heap (fruitheap.begin(), fruitheap.end(), min_heap_compare);
fruitheap.pop_back();
}
//for (it2=fruitheap.begin(); it2!=fruitheap.end(); it2++) {
//printf("%d %d\n", (*it2).height, (*it2).weight);
//}
}
unsigned int sum =0;
for (it=fruitheap.begin(); it!=fruitheap.end(); it++) {
//printf("%d %d\n", (*it).height, (*it).weight);
sum += (*it).weight;
}
fprintf (out, "%u", sum);
fclose (in); fclose (out);
return 0;
}