Pagini recente » Cod sursa (job #949876) | Cod sursa (job #2878375) | Cod sursa (job #3273755) | Cod sursa (job #1981368) | Cod sursa (job #438005)
Cod sursa(job #438005)
#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++;
}
qsort(v, size , sizeof(struct info), comp);
index = 0;
sum = 0;
groupitems = 0;
while (0 < 1) {
steps = (h - v[index].h) / u + 1;
nextindex = index;
while ((h - v[nextindex].h) / u + 1 == steps && nextindex < size)
nextindex++;
elements = nextindex - index;
quantity = min(steps - groupitems, elements);
for (i = 0 ; i < quantity; i++) {
Q.push(v[index + i].w);
sum += v[index + i].w;
groupitems++;
}
quantity = min(groupitems, elements);
for (; i < quantity; i++)
if (v[index + i].w <= Q.top()) {
break;
}
else {
//printf("%lu\n", Q.top());
sum += v[index + i].w - Q.top();
Q.pop();
Q.push(v[index + i].w);
}
if (nextindex == size)
break;
index = nextindex;
}
//for (i = 0 ; i < 9; i++) {
// printf(" Elem %lu\n", Q.top());
//Q.pop();
//}
fprintf(out, "%lu", sum);
fclose(in);
fclose(out);
return 0;
}