Pagini recente » Cod sursa (job #2663369) | Cod sursa (job #1619228) | Cod sursa (job #1817051) | Cod sursa (job #2633734) | Cod sursa (job #435541)
Cod sursa(job #435541)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct info {
unsigned long h, w;
} *v;
unsigned long comp(const void *a, const void *b)
{
return (((struct info *)b) -> h - ((struct info *) a) -> h);
}
int main()
{
unsigned long n, h, u, 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++;
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;
}