Pagini recente » Cod sursa (job #2915588) | Cod sursa (job #2341813) | Cod sursa (job #2819457) | Cod sursa (job #2957337) | Cod sursa (job #435557)
Cod sursa(job #435557)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct info {
unsigned long h, w;
} *v;
unsigned long u;
int comp(const void *a, const void *b)
{
struct info l1, l2;
l1 = *((struct info *) a);
l2 = *((struct info *) b);
if (l2.h / u >= l1.h / u) {
if (l2.h / u > l1.h / u)
return 1;
else
return l2.w - l1.w;
}
else {
return -1;
}
}
int main()
{
unsigned long n, h, i, maxindex, size, extraheight;
FILE *in, *out;
unsigned long *a, *b;
in = fopen("gutui.in", "rt");
out = fopen("gutui.out", "wt");
fscanf(in, "%lu %lu %lu", &n, &h, &u);
v = (struct info *) malloc(n * sizeof(struct info));
for (i = 0, size = 0; i < n; i++) {
fscanf(in , "%lu %lu", &v[size].h, &v[size].w);
if (v[size].h <= h)
size++;
}
a = (unsigned long *) malloc(size * sizeof(unsigned long));
b = (unsigned long *) malloc(size * sizeof(unsigned long));
qsort(v, size , sizeof(struct info), comp);
maxindex = 1;
a[0] = v[0].w;
i = maxindex;
for ( ; i < size ; i++)
if (v[i].w > a[i - 1])
a[i] = v[i].w;
else
a[i] = a[i - 1];
extraheight = u;
while (v[maxindex].h + extraheight > h && maxindex < size)
maxindex++;
if (maxindex >= size)
b[size - 1] = a[size - 1];
else
while (0 < 1) {
b[maxindex] = a[maxindex - 1] + v[maxindex].w;
for (i = maxindex + 1; i < size; i++)
if (a[i - 1] + v[i].w > b[i - 1])
b[i] = a[i-1] + v[i].w;
else
b[i] = b[i - 1];
maxindex++;
if (maxindex >= size)
break;
extraheight += u;
while (v[maxindex].h + extraheight > h && maxindex < size)
maxindex++;
if (maxindex >= size)
break;
memcpy(a + (maxindex - 1), b + (maxindex - 1), size - maxindex + 1);
}
fprintf(out, "%lu", b[size - 1]);
/*
for (i = 0; i < n; i++)
printf("%lu ", v[i].h);
*/
free(a);
free(b);
free(v);
fclose(in);
fclose(out);
return 0;
}