Cod sursa(job #437942)

Utilizator GaussClaudiu Coman Gauss Data 10 aprilie 2010 12:01:51
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.42 kb
#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;

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;
    }
}

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, h, index, size, sum, steps, quantity, nextindex, groupitems, elements;
    unsigned int i;
    FILE *in, *out;

    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++;
    }

    qsort(v, size , sizeof(struct info), comp);

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

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

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

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

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

        quantity = min(steps - quantity, elements);
        for (; i < quantity; i++)
            if (v[index + i].w <= Q.top())
                break;
            else {
                sum += v[index + i].w - Q.top();
                Q.pop();
                Q.push(v[index + i].w);
            }

        if (nextindex == size)
            break;

        index = nextindex;
    }

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

    fclose(in);
    fclose(out);

    return 0;
}