Cod sursa(job #1319539)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 17 ianuarie 2015 02:15:10
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I 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;
}