Cod sursa(job #837654)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 18 decembrie 2012 12:52:25
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;

const int NMAX=100073;

pair <int,int> V[NMAX];
set <int,greater <int> > Heap;

int N,X,L,TMAX;
long long lana;

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

    scanf ("%d%d%d",&N,&X,&L);
    for (int i=1; i<=N; ++i) {
        int D,A;

        scanf ("%d%d",&D,&A);
        V[i]=make_pair ((X-D)/L+1,A);
        TMAX=max (TMAX,(X-D)/L+1);
    }

    sort (V+1,V+N+1);

    int current=N;
    for (int i=TMAX; i>0; --i) {

        while (current>0 && V[current].first==i) {
            Heap.insert (V[current].second);
            --current;
        }

        if (Heap.size ()>0) {
            lana+=*(Heap.begin ());
            Heap.erase (Heap.begin ());
        }
    }

//    for (int i=1; i<=N; ++i)
//        printf ("(%d, %d) ",V[i].first,V[i].second);

    printf ("%lld",lana);

    return 0;
}