Cod sursa(job #436905)

Utilizator cristianbercaruCristian Bercaru cristianbercaru Data 9 aprilie 2010 00:52:15
Problema Gutui Scor 30
Compilator cpp Status done
Runda teme_upb Marime 2.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define print_vector() \
    for (itv = gutui_vector.begin(); itv != gutui_vector.end(); itv++) \
        printf("(%d %d)  ", (*itv).value, (*itv).time); \
    printf("\n\n")

#define print_list() \
    for (itl = gutui_list.begin(); itl != gutui_list.end(); itl++) \
        printf("(%d %d)  ", (*itl).value, (*itl).time); \
    printf("\n\n")

typedef struct _gutuie_t {
    int value;
    int time;
} gutuie_t;

bool comparator(const gutuie_t &, const gutuie_t &);

int main(void) {

    FILE *input = fopen("gutui.in", "r");
    FILE *output;
    int N, H, U;
    int i, temp, j;
    int sum = 0;
    int max = 0;

    gutuie_t gutuie;
    vector<gutuie_t> gutui_vector;
    vector<gutuie_t> :: iterator itv;
    list<gutuie_t> gutui_list;
    list<gutuie_t> :: iterator itl;
    priority_queue<int> maxheap;

    fscanf(input, "%d%d%d", &N, &H, &U);
    gutui_vector.reserve(N);
    gutui_list.clear();
    for (i = 0; i < N; i++) {
        fscanf(input, "%d%d", &temp, &gutuie.value);
        if ((temp = H - temp) >= 0) {
            gutuie.time = U != 0 ? temp / U : 0;
            if (temp > max) max = temp;
            gutui_vector.push_back(gutuie);
        }
    }
    fclose(input);
    N = gutui_vector.size();
    sort(gutui_vector.begin(), gutui_vector.end(), comparator);

    if (U != 0) N = H / U + 1;
    if (max < N) N = max;
    for (itv = gutui_vector.begin(); itv != gutui_vector.end(); itv++)
        gutui_list.push_back(*itv);
    gutui_vector.clear();

    for (i = 0; i < N; i++) {
        if (!gutui_list.empty()) {
            temp = gutui_list.front().time;
            for (j = 0; j <= temp && !gutui_list.empty() && gutui_list.front().time == temp; j++) {
                maxheap.push(gutui_list.front().value);
                gutui_list.pop_front();
            }
            while (!gutui_list.empty() && gutui_list.front().time == temp)
                gutui_list.pop_front();
        }
        if (!maxheap.empty()) {
            sum += maxheap.top();
            maxheap.pop();
        }
    }
    gutui_list.clear();

    output = fopen("gutui.out", "w");
    fprintf(output, "%d\n", sum);
    fclose(output);

    return 0;
}

bool comparator(const gutuie_t &a, const gutuie_t &b) {

    if (a.time > b.time)
        return true;
    if (a.time == b.time) {
        if (a.value > b.value)
            return true;
        else
            return false;
    }
    return false;
}