Cod sursa(job #436432)

Utilizator razielRazvan Madalin Oita raziel Data 8 aprilie 2010 16:19:30
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

struct gutuie {
    unsigned int height;
    unsigned int weight;
};

class compare {
    int hmax, nivel;
public:
    compare(int i, int j) : hmax(i), nivel(j) {};
    bool operator()(gutuie x, gutuie y) {
        return (((hmax - x.height) / nivel) + 1 < ((hmax - y.height) / nivel) + 1)
                || (!(((hmax - y.height) / nivel) + 1 < ((hmax - x.height) / nivel) + 1) && (x.weight > y.weight));
    }
};

int main() {
    int n;
    unsigned int h, u;
    gutuie g;
    vector<gutuie> gutui;
    vector<int> nivel;
    priority_queue< int, vector<int>, greater<int> > best;

    ifstream fin("gutui.in");
    fin >> n >> h >> u;
    for (int i = 0; i < n; i++) {
        fin >> g.height >> g.weight;
        gutui.push_back(g);
    }
    fin.close();

    sort(gutui.begin(), gutui.end(), compare(h, u));

    for (int i = 0; i < n; i++)
        nivel.push_back(((h - gutui[i].height) / u) + 1);
    nivel.push_back(nivel[n - 1] + 1);

    int i = 0;
    int niv = nivel[0];
    int ad = 0;
    while (i < n) {
        if (nivel[i] == niv && ad < niv) {
            best.push(gutui[i].weight);
            ad++;
            if (nivel[i + 1] > niv) {
                    while (best.size() > niv) {
                        best.pop();
                    }
                niv = nivel[i + 1];
                ad = 0;
            }
            i++;
        }
        else if (nivel[i] == niv && ad == niv) {
            if (nivel[i + 1] > niv) {
                        while (best.size() > niv) {
                            best.pop();
                        }
                    niv = nivel[i + 1];
                    ad = 0;
            }
            i++;
        }
    }

    unsigned int gmax = 0;
    while (best.size() > 0) {
        gmax += best.top();
        best.pop();
    }

    ofstream fout("gutui.out");
    fout << gmax << endl;
    fout.close();

    return 0;
}