Cod sursa(job #437580)

Utilizator GaussClaudiu Coman Gauss Data 9 aprilie 2010 22:22:06
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 4.1 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;
    }
}

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()
{
    unsigned long n, h, index, size, sum, steps, lastquantity, quantity, nextindex, groupitems;
    unsigned int i, j, k;
    FILE *in, *out;
    unsigned long *a;

    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(((h - v[size - 1].h) / u + 1 + 1) * sizeof(unsigned long));
    qsort(v, size , sizeof(struct info), comp);
    for (i = 0 ; i < ((h - v[size - 1].h) / u + 1 + 1); i++) a[i] = 0;

    a[0] = 0;

    steps = (h - v[0].h) / u + 1;
    nextindex = 0;
    while (((h - v[nextindex].h) / u  + 1) == steps && nextindex < size)
        nextindex++;
    lastquantity = min(steps, nextindex);
    quantity = lastquantity;

    for (i = 1, sum = 0; i <= lastquantity; i++) {
        a[i] = v[i - 1].w + sum;
        sum += v[i - 1].w;
    }

    index = nextindex;
    if (index < size)
        while (0 < 1) {
            steps = (h - v[index].h) / u + 1;

            //calculate where the next group starts and finding the number of elements for the current group
            nextindex = index;
            while (((h - v[nextindex].h) / u + 1) == steps && nextindex < size)
                nextindex++;
            groupitems = nextindex - index;

            quantity = lastquantity + min(steps - lastquantity, groupitems);

            //printf("Checking : indexes from %lu - %lu , quantity %lu\n", index, nextindex, quantity);

            //determine maximum weight for quantity > lastquantity

            if (quantity > lastquantity) {
                for (i = 0; i < min(quantity - lastquantity, groupitems); i++) {
                    //printf("Intra in bucla\n");
                    for (j = 0, sum = 0 ; j < i; j++) sum += v[index + j].w;
                    for (k = 0; k <= min(lastquantity , groupitems - 1 - i); j++, k++) {
                        //printf("Intra in a doua bucla\n");
                        //printf("a[%lu] ( = %lu) = max (a[%lu] ( = %lu), a[%lu] ( = %lu) + %lu + v[%lu].w ( = %lu)\n", lastquantity + i + 1, a[lastquantity + i + 1], lastquantity + i + 1, a[lastquantity + i + 1], lastquantity - k, a[lastquantity - k], sum, index + j, v[index + j].w);
                        a[lastquantity + i + 1] = max(a[lastquantity + i + 1], a[lastquantity - k] + sum + v[index + j].w);
                        //printf("%lu\n", a[lastquantity + i + 1]);
                        sum += v[index + j].w;
                    }
                }
            }

            for (i = lastquantity; i > 0; i--) {
                for (k = 0, sum = 0; k <= min(i - 1, groupitems - 1); k++) {
                    a[i] = max(a[i], a[i - k - 1] + sum + v[index + k].w);
                    sum += v[index + k].w;
                }
            }

            if (nextindex == size)
                break;

            lastquantity = max(lastquantity, quantity);
            index = nextindex;

            //for (i = 0; i <= lastquantity; i++) printf("%lu ", a[i]);
            //printf("\n");
        }

    fprintf(out, "%lu", a[quantity]);


/*    for (i = 0; i < n; i++)
        printf("(%lu %lu)", v[i].h, v[i].w);*/

    free(a);
    free(v);

    fclose(in);
    fclose(out);

    return 0;
}