Cod sursa(job #1760572)

Utilizator antracodRadu Teodor antracod Data 20 septembrie 2016 23:15:48
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>

using namespace std;
/// Cod gutui Antracod
ifstream in("lupu.in");
ofstream out("lupu.out");

const int NMAX = 100001;

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;
    long long int N,H,U;
    long long int sol=0;
    long long int maxexp=-1;
    long long int i,j;
    in>>N>>H>>U;

    for(i=1; i<=N; i++)
    {
        long long 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;
    long long 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;
}