Cod sursa(job #2003142)

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

const int MAXN = 1e5;

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

int heap[MAXN + 1], len;

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

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

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

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

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

inline void up(int p) {
  while (p > 0 && heap[p] < heap[father(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 (x == p) {
      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, cnt, maxd, dist;
  long long ans;
  FILE *f = fopen("lupu.in", "r");
  fscanf(f, "%d%d%d", &n, &maxd, &dist);
  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 * dist * cnt + v[i].d <= maxd) {
      add(v[i].b);
      ++cnt;        
    } else if (heap[0] <= v[i].b) {
      heap[0] = v[i].b;
      down(0);
    }
  }
  ans = 0LL;
  for (int i = 0; i < len; ++i) {
    ans += heap[i];
  }
  f = fopen("lupu.out", "w");
  fprintf(f, "%lld\n", ans);
  fclose(f);
  return 0;
}