Cod sursa(job #1405257)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 28 martie 2015 23:24:11
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
#define f first
#define s second
#define DIM 100010
using namespace std;

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

int N, M, i, j, K, ok, minim;
pair <int, int> V[DIM];
int Heap[DIM], L, X, sum;

void SetUp(){
     fin >> N >> L >> X;
     for(i = 1; i <= N; i ++)
          fin >> V[i].f >> V[i].s;
     sort(V + 1, V + N + 1);
     return;
}

void Swap(int a, int b){
     int c;
     c = Heap[a];
     Heap[a] = Heap[b];
     Heap[b] = c;
     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 HeapExpert(){
     i = N;
     while(V[i].f > L)
          i --;
     while(i != 0){
          for(j = 1; j <= M; j ++)
               Heap[j] = 0;
          M = 0; L -= X;
          while(i != 0 && V[i].f > L){
               Heap[++M] = V[i--].s;
               Shift(M);
          }
          sum += Heap[1];
     }
     fout << sum;
     return;
}

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