Cod sursa(job #2003143)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 21 iulie 2017 22:44:22
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <algorithm>

const int MAXN = 1e5;

struct S {
  int b, d;
} v[MAXN + 1];

int heap[MAXN + 1], len;

inline bool cmp(S a, S b) {
  return a.d > b.d;
}

inline int father(int p) {
  return p / 2;
}

inline int leftson(int p) {
  return 2 * p;
} 

inline int rightson(int p) {
  return 2 * p + 1;
}

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

inline void up(int p) {
  while (p > 1 && heap[father(p)] > heap[p]) {
    swap(heap[p], heap[father(p)]);
    p = father(p);
  }
}

inline void down(int p) {
  int x = p;
  while (p <= len) {
    if (leftson(p) <= len && heap[leftson(p)] < heap[x]) {
      x = leftson(p);
    }
    if (rightson(p) <= len && heap[rightson(p)] < heap[x]) {
      x = rightson(p);
    }
    if (p == x) {
      p = len + 1;
    } else {
      swap(heap[p], heap[x]);
      p = x;
    }
  }
}

inline void add(int p) {
  ++len;
  heap[len] = p;
  up(len);
}

int main() {
  int n, d, maxd, cnt;
  long long ans;
  FILE *f = fopen("lupu.in", "r");
  fscanf(f, "%d%d%d", &n, &maxd, &d);
  for (int i = 0; i < n; ++i) {
    fscanf(f, "%d%d", &v[i].d, &v[i].b);
  }
  fclose(f);
  std::sort(v, v + n, cmp);
  cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (1LL * d * cnt + v[i].d <= maxd) {
      add(v[i].b);
      ++cnt;
    } else if (v[i].b >= heap[1]) {
      heap[1] = v[i].b;
      down(1);
    }
  }
  ans = 0LL;
  for (int i = 1; i <= len; ++i) {
    ans += heap[i];
  }
  f = fopen("lupu.out", "w");
  fprintf(f, "%lld\n", ans);
  fclose(f);
  return 0;
}