Cod sursa(job #447155)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 27 aprilie 2010 20:47:35
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long

priority_queue<ll> heap;

struct oaie
{
    ll x,y;
};
oaie v[100006];
ll s=0;
ll d,l,n;

int cmp(const oaie& a,const oaie& b)
{
    return (a.x<b.x);
}

int main ()
{
    ll i,lim,val;
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%lld%lld%lld",&n,&d,&l);
    for(i=1;i<=n;i++)
        scanf("%lld%lld",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    i=1;
    for(lim=0;lim<=d && i<=n;lim+=l)
    {
        for(i=i;i<=n && v[i].x<=lim;i++)
            heap.push(v[i].y);
        if(!heap.empty())
        {
            val=heap.top();
            s+=val;
            heap.pop();
        }
    }
    printf("%lld\n",s);
    return 0;
}