Cod sursa(job #3192207)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 11 ianuarie 2024 19:40:56
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 100000

#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;

struct Option {
  int x;
  int id, pos;
};

Option hp[MAXN];
int hpl = 0;

void downheap(int x){
  int chosen;

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

  if(hp[x].x < hp[chosen].x){
    Option aux = hp[chosen];
    hp[chosen] = hp[x];
    hp[x] = aux;
    downheap(chosen);
  }
}
void upheap(int x){
  if(x > 0 && hp[x].x < hp[PR(x)].x){
    Option aux = hp[x];
    hp[x] = hp[PR(x)];
    hp[PR(x)] = aux;
    upheap(PR(x));
  }
}

static inline int bracket(int x, int y){
  if(x % y == 0)
    return x / y;
  return x / y + 1;
}

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

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

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

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

  for(int i = 0; i < nrb; i ++)
    sort(v[i].begin(), v[i].end());

  // for(int i = 0; i < nrb; i ++){
  //   printf("%d: ", i);
  //   for(int j = 0; j < v[i].size(); j ++){
  //     printf("%d ", v[i][j]);
  //   }
  //   printf("\n");
  // }
  // printf("\n");
  
  int sum = 0;
  for(int i = 0; i < nrb; i ++){
    Option o = {v[i][ v[i].size() - 1] , i, (int)v[i].size() - 1};
    hp[hpl ++] = o;
    upheap(hpl - 1);

    // cout << hp[0].x << " " << hp[0].id << " " << hp[0].pos << "\n";
    sum += hp[0].x;
    if(hp[0].pos != 0){
      hp[0].pos --;
      hp[0].x = v[hp[0].id][hp[0].pos];

    } else{
      hp[0] = hp[hpl - 1];
      hpl --;
    }
    downheap(0);
  }

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

  return 0;
}