Cod sursa(job #1824091)

Utilizator silkMarin Dragos silk Data 7 decembrie 2016 12:20:47
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#define NMax 100000
using namespace std;

priority_queue<int> Q;
pair<int, int> v[NMax+1];

int main(){
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

    int i,j,t,N,M,X,L,a,b,lim;
    long long ans = 0;

    scanf("%d %d %d",&N,&X,&L);
    for(lim = 2*NMax+1, M = 0, i = 1; i <= N; ++i)
    {
        scanf("%d %d",&a,&b);
        if(a <= X && b)
        {
            if( (X-a)/L >= lim ) { ans = ans + b; ++lim; }
            else{
                if( (X-a)/L >= 2*NMax+1 ) a = 2*NMax;
                else a = (X-a)/L;
                v[++M] = make_pair( a,b);
            }
        }
    }
    N = M;
    sort(v+1,v+N+1);
    for(i = N, t = v[N].first; t >= 0; --t)
    {
        for(; i >= 1 && v[i].first==t; --i) Q.push( v[i].second );
        if( !Q.empty() )
        {
            ans = ans + Q.top();
            Q.pop();
        }
    }

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



return 0;
}