Cod sursa(job #2839783)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 26 ianuarie 2022 16:18:18
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 5;

struct oaie {
  int d;
  int a;
  bool operator<(const oaie& o) const {
    return d > o.d;
  }
};

oaie v[N];

class Heap {
private:
  vector<int> h;
  void up(int nod) {
    while (nod > 1 && v[h[nod]].a < v[h[nod / 2]].a) {
      swap(h[nod], h[nod / 2]);
      nod /= 2;
    }
  }
  void down(int nod) {
    while (nod * 2 < h.size()) {
      int fiu = nod * 2;
      if (fiu + 1 < h.size() && v[h[fiu + 1]].a < v[h[fiu]].a)
        fiu = fiu + 1;
      if (v[h[nod]].a <= v[h[fiu]].a)
        break;
      swap(h[nod], h[fiu]);
      nod = fiu;
    }
  }
public:
  Heap() {
    h.push_back(0);
  }
  void push(int x) {
    h.push_back(x);
    up(h.size() - 1);
  }
  int top() {
    if (empty())
      return -1;
    return h[1];
  }
  void pop() {
    h[1] = h.back();
    h.pop_back();
    down(1);
  }
  bool empty() {
    return h.size() <= 1;
  }
};

int main() {
  ifstream cin("lupu.in");
  ofstream cout("lupu.out");
  int n, x, l;
  cin >> n >> x >> l;
  for (int i = 0; i < n; ++i)
    cin >> v[i].d >> v[i].a;
  cin.close();
  sort(v, v + n);
  Heap h;
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    if (v[i].d <= x) {
      h.push(i);
      ans += v[i].a;
      x -= l;
    } else {
      int poz = h.top();
      if (v[poz].a < v[i].a) {
        ans += v[i].a - v[poz].a;
        h.pop();
        h.push(i);
      }
    }
  }
  cout << ans << "\n";
  cout.close();
  return 0;
}