Pagini recente » Cod sursa (job #1261178) | Cod sursa (job #249022) | Cod sursa (job #3287503) | Cod sursa (job #544243) | Cod sursa (job #440242)
Cod sursa(job #440242)
//Claudiu Coman 322 CA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
unsigned long h, w;
} *v;
unsigned long u, h;
int comp(const void *a, const void *b)
{
struct info l1, l2;
l1 = *((struct info *) a);
l2 = *((struct info *) b);
if ((h - l2.h) / u <= (h - l1.h) / u) {
if ((h - l2.h) / u < (h - l1.h) / u)
return 1;
else
return l2.w - l1.w;
}
else {
return -1;
}
}
struct cmp {
bool operator()(unsigned long const& a, unsigned long const& b) const {
return a > b;
}
};
inline unsigned long min(unsigned long a, unsigned long b)
{
return ((a < b) ? a : b);
}
inline unsigned long max(unsigned long a, unsigned long b)
{
return ((a > b) ? a : b);
}
int main()
{
priority_queue<unsigned long, vector<unsigned long>, cmp> Q;
unsigned long n, index, size, sum, steps, quantity, nextindex, groupitems, elements;
unsigned long i;
FILE *in, *out;
in = fopen("gutui.in", "rt");
out = fopen("gutui.out", "wt");
fscanf(in, "%lu %lu %lu\n", &n, &h, &u);
v = (struct info *) malloc(n * sizeof(struct info));
for (i = 0, size = 0; i < n; i++) {
fscanf(in , "%lu %lu\n", &v[size].h, &v[size].w);
if (v[size].h <= h)
size++;
}
//sorting the array
qsort(v, size , sizeof(struct info), comp);
index = 0;
sum = 0;
groupitems = 0;
while (0 < 1) {
steps = (h - v[index].h) / u + 1;
//calculating the first index for the next group and the number of elements for the current group
nextindex = index;
while ((h - v[nextindex].h) / u + 1 == steps && nextindex < size)
nextindex++;
elements = nextindex - index;
quantity = min(steps - groupitems, elements);
//filling the heap
for (i = 0 ; i < quantity; i++) {
Q.push(v[index + i].w);
groupitems++;
}
//replacing elements if needed
quantity = min(groupitems, elements);
for (; i < quantity; i++)
if (v[index + i].w <= Q.top()) {
break;
}
else {
Q.pop();
Q.push(v[index + i].w);
}
if (nextindex == size)
break;
index = nextindex;
}
//calculating the weight of the elements in the heap
for (i = 0 , sum = 0; i < groupitems; i++) {
sum += Q.top();
Q.pop();
}
fprintf(out, "%lu", sum);
free(v);
fclose(in);
fclose(out);
return 0;
}