Cod sursa(job #3252977)

Utilizator rockoanaOana Pasca rockoana Data 31 octombrie 2024 17:07:26
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
/*
                    __
                   /\ \
 _ __   ___     ___\ \ \/'\     ___      __      ___     ___      __
/\`'__\/ __`\  /'___\ \ , <    / __`\  /'__`\  /' _ `\ /' _ `\  /'__`\
\ \ \//\ \L\ \/\ \__/\ \ \\`\ /\ \L\ \/\ \L\.\_/\ \/\ \/\ \/\ \/\ \L\.\_
 \ \_\\ \____/\ \____\\ \_\ \_\ \____/\ \__/.\_\ \_\ \_\ \_\ \_\ \__/.\_\
  \/_/ \/___/  \/____/ \/_/\/_/\/___/  \/__/\/_/\/_/\/_/\/_/\/_/\/__/\/_/


*/

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
using i64 = int64_t;

class heap {
 private:
  int len = 0;
  i64 heap[400004];

  void swamp(i64 a, i64 b) { swap(heap[a], heap[b]); }

  void up(int pos) {
    while (pos > 1 && heap[pos / 2] < heap[pos]) {
      swamp(pos, pos / 2);
      pos /= 2;
    }
  }
  void down(int pos) {
    while (pos * 2 <= len) {
      int t = pos * 2;
      if (pos * 2 + 1 <= len && heap[pos * 2 + 1] > heap[pos * 2]) {
        t++;
      }
      if (heap[pos] < heap[t]) {
        swamp(pos, t);
        pos = t;
      } else
        break;
    }
  }

 public:
  bool empty() { return (len == 0); }

  void erase(int pos) {
    if (pos == len) {
      len--;
    } else {
      swamp(pos, len);
      len--;
      up(pos);
      down(pos);
    }
  }

  i64 max() {
    i64 tmp = heap[1];
    erase(1);
    return tmp;
  }

  void add(i64 val) {
    len++;
    heap[len] = val;
    up(len);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // #ifdef LOCAL
  ifstream cin{"lupu.in"};
  ofstream cout{"lupu.out"};
  // #endif

  i64 n, m, l;
  cin >> n >> m >> l;

  vector<pair<i64, i64>> v(n);
  int x, y;
  for (int i = 0; i < n; i++) {
    cin >> x >> y;
    v[i] = {x, y};
  }
  sort(v.begin(), v.end());

  heap h;

  int res = 0;
  int len = ((m - v[0].first) / l) * 2;
  int idx = 0;
  while (idx < n) {
    while (idx < n && v[idx].first + len <= m) {
      h.add(v[idx].second);
      idx++;
    }

    res += h.max();
    if (idx < n) {
      int len2 = ((m - v[idx].first) / l) * l;
      while (len + l < len2 && !h.empty()) {
        res += h.max();
        len += l;
      }
      len = len2;
    }
  }

  cout << res;

  return 0;
}