Cod sursa(job #3192831)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 13 ianuarie 2024 12:13:48
Problema Lupul Urias si Rau Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 100000
#define DEBUG 0

#define PR(x) (x-1)/2
#define CH1(x) (x*2)+1
#define CH2(x) (x*2)+2

using namespace std;

vector<vector<int>> v;
int nrb = 0;

static inline int bracket(int x, int y, int z){
  return (x-z) / y;
}

int hp[MAXN], hpl = 0;
void swap(int a, int b){
  int aux = hp[a];
  hp[a] = hp[b];
  hp[b] = aux;
}

void downheap(int x){
  int chosen;

  if(CH1(x) >= hpl)
    return;
  if(CH2(x) >= hpl || hp[CH2(x)] > hp[CH1(x)]){
    chosen = CH1(x);
  } else
    chosen = CH2(x);

  if(hp[x] < hp[chosen]){
    swap(chosen, x);
    downheap(chosen);
  }
}
void upheap(int x){
  if(x == 0)
    return;

  if(hp[x] > hp[PR(x)]){
    swap(x, PR(x));
    upheap(PR(x));
  }
}
void remove(int x){
  hpl --;
  hp[x] = hp[hpl];

  if(hpl > x)
    downheap(x);
}

bool empty(){
  return hpl == 0;
}
int top(){
  return hp[0];
}
void pop(){
  remove(0);
}
void push(int x){
  hp[hpl] = x;
  hpl ++;
  upheap(hpl - 1);
}

int main(){
  int n, x, y;

  ifstream fin ("lupu.in");
  fin >> n >> x >> y;

  nrb = bracket(x, y, 0) + 1;
  v.resize(nrb);

  for(int i = 0; i < n; i ++){
    int d, l;
    fin >> d >> l;
    if(d <= x)
      v[bracket(x, y, d)].push_back(l);
  }
  fin.close();

  if(DEBUG){
    for(int i = 0; i < nrb; i ++){
      printf("%d: ", i);
      for(int j = 0; j < (int)v[i].size(); j ++){
        printf("%d ", v[i][j]);
      }
      printf("\n");
    }
    printf("\n");
  }

  long long sum = 0;
  for(int i = nrb - 1; i >= 0; i --){
    for(int j = 0; j < (int)v[i].size(); j ++)
      push(v[i][j]);

    if(!empty()){
      sum += top();
      pop();
    }
  }

  ofstream fout ("lupu.out");
  fout << sum << endl;
  fout.close();

  return 0;
}