Cod sursa(job #782462)

Utilizator oana_popfmi - pop oana oana_pop Data 27 august 2012 22:47:27
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <algorithm>
#define distanta first
#define profit second
#define NMAX 100100
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
pair <int , int> V[NMAX];
int N,X,L,Vf,Heap[NMAX];
long long sol;

inline int father(int k)
{
       return k/2;
}

inline int left(int k)
{
       return 2*k;
}

inline int right(int k)
{
       return 2*k+1;
}

inline int cmp(int a,int b)
{
       if(V[Heap[a]].profit>V[Heap[b]].profit) return 1;
       else return 0;
}

void up(int nod)
{
     while(nod>1 && cmp(nod,father(nod)))
     {
                 swap(Heap[nod],Heap[father(nod)]);
                 nod=father(nod);
     }
}

void down(int nod)
{
     int son;
     do
     {
         son=0;
         if(left(nod)<=Vf)
         {
                          son=left(nod);
                          if(right(nod)<=Vf && cmp(right(nod),left(nod)))
                          son=right(nod);
                          if(cmp(nod,son)) son=0;
         }
         if(son)
         {
                swap(Heap[nod],Heap[son]);
                nod=son;
         }
     }
     while(son);
     
}

void citire()
{
     f>>N>>X>>L;
     for(int i=1; i<=N; i++)
     {
             f>>V[i].distanta>>V[i].profit;
             V[i].distanta=(X-V[i].distanta)/L+1;
     }
}

int main()
{
    int i , k;
    citire();
    sort(V+1,V+N+1);
    reverse(V+1,V+N+1);
    for(k=V[1].distanta,i=1;k>=1;k--)
    {
        for(;V[i].distanta==k && i<=N;i++)
    
        {
                              Heap[++Vf]=i;
                              up(Vf);
        }
        if(Vf)
        {
              sol+=V[Heap[1]].profit;
              Heap[1]=Heap[Vf--];
              down(1);
        } 
    }
    g<<sol<<"\n";
}