Cod sursa(job #3252995)

Utilizator rockoanaOana Pasca rockoana Data 31 octombrie 2024 17:40:30
Problema Lupul Urias si Rau Scor 16
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 len = ((m - v[0].first) / l) * l;
  i64 idx = 0;
  while (idx < n) {
    while (idx < n && v[idx].first + len <= m) {
      h.push(v[idx].second);
      idx++;
    }

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

  cout << res;

  return 0;
}