Cod sursa(job #435907)

Utilizator razielRazvan Madalin Oita raziel Data 7 aprilie 2010 22:51:17
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
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() {
    unsigned int n, h, u, dim;
    gutuie g;
    vector<gutuie> gutui;
    vector<int> nivel;
    vector<unsigned 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, niv = nivel[0];
    int ad = 0;
    while (i < n) {
        if (nivel[i] == niv && ad < niv) {
            best.push_back(gutui[i].weight);
            make_heap(best.begin(), best.end());
            ad++;
            if (nivel[i + 1] > niv) {
                if (niv > 1 && ad == niv) {
                    best.erase(best.end() - niv + 1, best.end());
                }
                niv = nivel[i + 1];
                ad = 0;
            }
            i++;
        }
        else if (nivel[i] == niv && ad == niv) {
            if (nivel[i + 1] > niv) {
                    if (niv > 1 && ad == niv) {
                        best.erase(best.end() - niv + 1, best.end());
                    }
                    niv = nivel[i + 1];
                    ad = 0;
            }
            i++;
        }
    }

    unsigned int gmax = 0;
    for (int j = 0; j < best.size(); j++) {
        gmax += best[j];
    }

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

    return 0;
}