Cod sursa(job #435541)

Utilizator GaussClaudiu Coman Gauss Data 7 aprilie 2010 16:18:49
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 1.94 kb
#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;
}