Cod sursa(job #462992)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 12:36:26
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.76 kb
//Claudiu Coman 322 CA

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct info {
    unsigned long h, w;
} *v;

unsigned long u, h;

int comp(const void *a, const void *b)
{
    struct info l1, l2;
    l1 = *((struct info *) a);
    l2 = *((struct info *) b);

    if ((h - l2.h) / u <= (h - l1.h) / u) {
        if ((h - l2.h) / u < (h - l1.h) / u)
            return 1;
        else
            return l2.w - l1.w;
    }
    else {
        return -1;
    }
}

struct cmp {
    bool operator()(unsigned long const& a, unsigned long const& b) const {
        return a > b;
    }
};


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()
{
    priority_queue<unsigned long, vector<unsigned long>, cmp> Q;
    unsigned long n, index, size, sum, steps, quantity, nextindex, groupitems, elements;
    unsigned long i;
    FILE *in, *out;

    in = fopen("gutui.in", "rt");
    out = fopen("gutui.out", "wt");

    fscanf(in, "%lu %lu %lu\n", &n, &h, &u);

    v = (struct info *) malloc(n * sizeof(struct info));

    for (i = 0, size = 0; i < n; i++) {
        fscanf(in , "%lu %lu\n", &v[size].h, &v[size].w);
        if (v[size].h <= h)
            size++;
    }

    //sorting the array
    qsort(v, size , sizeof(struct info), comp);

    index = 0;
    sum = 0;
    groupitems = 0;

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

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

        elements = nextindex - index;
        quantity = min(steps - groupitems, elements);

        //filling the heap
        for (i = 0 ; i < quantity; i++) {
            Q.push(v[index + i].w);
            groupitems++;
        }

        //replacing elements if needed
        quantity = min(groupitems, elements);
        for (; i < quantity; i++)
            if (v[index + i].w <= Q.top()) {
                break;
            }
            else {
                Q.pop();
                Q.push(v[index + i].w);
            }

        if (nextindex == size)
            break;

        index = nextindex;
    }

    //calculating the weight of the elements in the heap
    for (i = 0 , sum = 0; i < groupitems; i++) {
        sum += Q.top();
        Q.pop();
    }

    fprintf(out, "%lu", sum);

    free(v);

    fclose(in);
    fclose(out);

    return 0;
}