Cod sursa(job #1410222)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 30 martie 2015 22:31:31
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <algorithm>
#define DIM 120000
#define f first
#define s second
using namespace std;

ifstream fin ("lupu.in" );
ofstream fout("lupu.out");

int N, M, i, j, K, ok, maxim, sum;
int L, Heap[DIM], X, a, b, k, aux;

pair <int, int> V[DIM];

void SetUp(){
     fin >> N >> L >> X;
     for(i = 1; i <= N; i ++){
          fin >> a >> b;
          if(a <= L){
               a = L - a;
               a /= X;
               if(maxim < a)
                    maxim = a;
          }
          else{
               a = -a;
          }
          V[i].f = a;
          V[i].s = b;
     }
     sort(V + 1, V + N + 1);
     for(i = 1; i <= N / 2; i ++){
          aux = V[i].f;
          V[i].f = V[N-i+1].f;
          V[N-i+1].f = aux;
          aux = V[i].s;
          V[i].s = V[N-i+1].s;
          V[N-i+1].s = aux;
     }
     return;
}

void Swap(int a, int b){
     int aux;
     aux = Heap[a];
     Heap[a] = Heap[b];
     Heap[b] = aux;
     return;
}

void Shift(int c){
     int p = c / 2;
     while(p != 0){
          if(Heap[p] < Heap[c]){
               Swap(p, c);
               c = p;
               p /= 2;
          }
          else
               break;
     }
     return;
}

void Percolate(int p){
     int c = p * 2;
     while(c <= M){
          if(c + 1 <= M && Heap[c] < Heap[c+1])
               c ++;
          if(Heap[p] < Heap[c]){
               Swap(p, c);
               p = c;
               c *= 2;
          }
          else
               break;
     }
     return;
}

void HeapExpert(){
     i = 1;
     for(k = maxim; k >= 0; k --){
          while(V[i].f == k){
               M ++;
               Heap[M] = V[i].s;
               Shift(M);
               i ++;
          }
          sum += Heap[1];
          Heap[1] = Heap[M];
          Heap[M--] = 0;
          Percolate(1);
     }
     fout << sum;
     return;
}

int main(){
     SetUp();
     HeapExpert();
     return 0;
}