Cod sursa(job #1981380)

Utilizator TincaMateiTinca Matei TincaMatei Data 15 mai 2017 15:44:18
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>

const int MAX_N = 100000;
struct Sheep {
  int lana, dist;
} v[MAX_N];

bool cmp(Sheep a, Sheep b) {
  return a.dist > b.dist;
}

int heap[1+MAX_N], size;

inline void swap(int &a, int &b) {
  int aux = a;
  a = b;
  b = aux;
}

inline void upheap(int p) {
  while(p > 1) {
    if(heap[p] < heap[p / 2])
      swap(heap[p], heap[p / 2]);
    p = p / 2;
  }
}

inline void downheap(int p) {
  int poz = p;
  while(p <= size) {
    if(2 * p <= size && heap[2 * p] < heap[poz])
      poz = 2 * p;
    if(2 * p + 1 <= size && heap[2 * p + 1] < heap[poz])
      poz = 2 * p + 1;

    if(poz == p)
      p = size + 1;
    else {
      swap(heap[p], heap[poz]);
      p = poz;
    }
  }
}

inline void add(int x) {
  ++size;
  heap[size] = x;
  upheap(size);
}

int main() {
  int n, dist, maxdist, selectate = 0;
  long long suma = 0LL;
  FILE *fin = fopen("lupu.in", "r");
  fscanf(fin, "%d%d%d", &n, &maxdist, &dist);
  for(int i = 0; i < n; ++i)
    fscanf(fin, "%d%d", &v[i].dist, &v[i].lana);
  fclose(fin);

  std::sort(v, v + n, cmp);
  for(int i = 0; i < n; ++i) {
    if((long long)dist * selectate + v[i].dist < maxdist) {
      add(v[i].lana);
      suma = suma + v[i].lana;
      ++selectate;
    } else if(v[i].lana > heap[1]) {
      suma = suma - heap[1] + v[i].lana;
      heap[1] = v[i].lana;
      downheap(1);
    }
  }

  FILE *fout = fopen("lupu.out", "w");
  fprintf(fout, "%lld", suma);
  fclose(fout);
  return 0;
}