Cod sursa(job #440641)

Utilizator sdnxptVasiliu Radu sdnxpt Data 12 aprilie 2010 12:16:06
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.27 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Gutuie{
    public:
        unsigned int greutate, nivel;
};

bool comp1(const Gutuie &a, const Gutuie &b){
    return a.nivel < b.nivel;
}

inline unsigned int nivel( const unsigned int &a, const unsigned int &u, const unsigned int &hmax ){
    return (hmax - a) / u + 1;
}

int main(){
    unsigned int n, u, hmax;
    ifstream fin("gutui.in");
    ofstream fout("gutui.out");
    fin >> n >> hmax >> u;
    unsigned int i, x;
    vector<Gutuie> v(n);
    for(i = 0; i < n; i++){
        fin >> x >> v[i].greutate;
        v[i].nivel = nivel(x, u, hmax);
    }
    sort( v.begin(), v.end(), comp1 );
    unsigned int gmax = 0;
    priority_queue< unsigned int, vector<unsigned int>, greater<unsigned int> > greutate;
    for(i = 0; i < n; i++){
        if( greutate.size() < v[i].nivel ){
            gmax += v[i].greutate;
            greutate.push( v[i].greutate );
        }
        else
            if( greutate.top() < v[i].greutate ){
                gmax -= greutate.top();
                gmax += v[i].greutate;
                greutate.pop();
                greutate.push( v[i].greutate );
            }
    }
    fout << gmax;
    fin.close();
    fout.close();
    return 0;
}