Cod sursa(job #593462)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 2 iunie 2011 23:28:56
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

struct sheep
{
    int t,w;
};

struct cmp
{
    bool operator()(sheep i,sheep j)
    {
        return i.t<j.t;
    }
};

priority_queue <int> h;
sheep v[100001];
long long sol;

int main()
{
    int n,x,l,i,j;
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d %d %d\n",&n,&x,&l);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d\n",&v[i].t,&v[i].w);
        v[i].t=(x-v[i].t)/l+1;
    }
    sort(v+1,v+n+1,cmp());
    for (i=v[n].t,j=n;i>0;--i)
    {
        while (j>0&&v[j].t==i)
        {
            h.push(v[j].w);
            --j;
        }
        if (!h.empty())
        {
            sol+=h.top();
            h.pop();
        }
    }
    printf("%lld\n",sol);
    return 0;
}