Cod sursa(job #881930)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 18 februarie 2013 19:24:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<cstdio>
#include<algorithm>
#include <utility>
#include <queue>
#define INF 2147483647
#define dist first
#define profit second
using namespace std;
pair <int,int> oaie[100005];
int n,x,l;
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d %d %d",&n,&x,&l);
    int i,k;long long s=0;
    for(i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        oaie[i].dist=(x-a)/l+1;
        oaie[i].profit=b;
    }
    sort(oaie+1,oaie+n+1);
    reverse(oaie+1,oaie+n+1);
    k=oaie[1].dist;
    i=1;
    priority_queue <int> best;
    while(k)
    {
        while(i<=n && k==oaie[i].dist)
        {
            best.push(oaie[i].profit);
            i++;
        }
        if(!best.empty())
        {
            s+=best.top();
            best.pop();
        }
        k--;
    }
    printf("%lld\n",s);
    return 0;
}