Cod sursa(job #435557)

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