Cod sursa(job #3253001)

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


*/

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

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // #ifdef LOCAL
  //   ifstream cin{"input.txt"};
  //   ofstream cout{"output.txt"};
  // #endif

  ifstream cin{"lupu.in"};
  ofstream cout{"lupu.out"};

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

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

  // heap h;
  priority_queue<i64, vector<i64>, less<i64>> h;

  i64 res = 0;
  i64 t = ((m - v[0].first) / l);
  i64 idx = 0;
  while (idx < n) {
    while (idx < n && (m - v[idx].first) / l == t) {
      h.push(v[idx].second);
      idx++;
    }

    res += h.top();
    h.pop();
    i64 t2 = 0;
    if (idx < n) {
      t2 = ((m - v[idx].first) / l);
    }
    while (t - 1 > t2 && !h.empty()) {
      res += h.top();
      h.pop();
      t--;
    }
    t = t2;
  }

  cout << res;

  return 0;
}