Cod sursa(job #1132123)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 2 martie 2014 18:33:20
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.06 kb
#include<algorithm>
#include<queue>
#include<cstdio>

using namespace std;

const int NMAX = 100000+5;

struct Gutuie
{
    int height,weight,fruits;

    void Set(int h,int w,int f)
    {
        height=h;
        weight=w;
        fruits=f;
    }

    bool operator()(Gutuie A,Gutuie B)
    {
        if(A.fruits==B.fruits) return A.weight>B.weight;
        return A.fruits>B.fruits;
    }
};

int N,H,U;
long long Sol;
Gutuie V[NMAX];
priority_queue<int> Q;

int main()
{
    int i,j,h,w,f;

    freopen("gutui.in","r",stdin);
    freopen("gutui.out","w",stdout);

    scanf("%d%d%d",&N,&H,&U);

    for(i=1; i<=N; i++)
    {
        scanf("%d%d",&h,&w);
        if(h>H) f=-1;
        else f=(H-h)/U;
        V[i].Set(h,w,f);
    }

    sort(V+1,V+N+1,Gutuie());
    f=V[1].fruits;

    for(i=f,j=1; i>=0; i--)
    {
        for(; V[j].fruits==i && j<=N; j++)
            Q.push(V[j].weight);
        if(Q.empty()) continue;
        Sol+=1LL*Q.top();
        Q.pop();
    }

    printf("%lld\n",Sol);

    return 0;
}