Cod sursa(job #1760526)

Utilizator antracodRadu Teodor antracod Data 20 septembrie 2016 21:49:59
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>

using namespace std;

ifstream in("gutui.in");
ofstream out("gutui.out");

const int NMAX = 200001;

struct gutuie
{
    int exp;
    int value;
};

gutuie v[NMAX];

bool cmp(const gutuie &i,const gutuie &j)
{
    return i.exp<j.exp;
}

struct comp
{
    bool operator()(const int &x,const int &y)
    {
        return x>y;
    }
};

int main()
{
    multiset <int,comp> Heap;
    int N,H,U;
    int sol=0;
    int maxexp=0;
    int i,j;
    in>>N>>H>>U;

    for(i=1; i<=N; i++)
    {
        int hg,val;
        in>>hg>>val;
        v[i].exp=(H-hg)/U;
        v[i].value=val;
        maxexp=max(maxexp,v[i].exp);
    }
    sort(v+1,v+N+1,cmp);
    v[0].exp;
    int k=N;
    for(i=maxexp; i>=0;i--)
    {
        j=k;
        for(; v[j].exp==i; j--)
        {
            Heap.insert(v[j].value);
        }
        k=j;
        if(Heap.empty()==0)
        {
            sol+=*(Heap.begin());
            Heap.erase(Heap.begin());
        }

    }
    out<<sol;
}