Cod sursa(job #2776867)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 21 septembrie 2021 14:21:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

std::vector<std::pair<long long, long long>> v;

bool compare(const std::pair<long long, long long>& left,
             const std::pair<long long, long long>& right) {
  if (left.first != right.first) return left.first < right.first;
  return left.second > right.second;
}

int main()
{
  std::ifstream in("lupu.in");
  std::ofstream out("lupu.out");

  long long n, max, step;
  in >> n >> max >> step;
  for (int i = 1; i <= n; ++i) {
    long long init, lana;
    in >> init >> lana;
    long long max_step = (init > max) ? 0 : ((max - init) / step);
    v.push_back(std::make_pair(max_step, lana));
  }

  std::sort(v.begin(), v.end(), compare);
  std::priority_queue<long long,
                      std::vector<long long>,
                      std::greater<long long>> picked;
  step = 0;
  for (int i = 0; i < v.size(); ++i) {
    if (v[i].first >= step) {
      // If you can pick it, just pick it.
      picked.push(v[i].second);
      step++;
    } else {
      // If you can replace something from earlier, do.
      if (!picked.empty() && picked.top() < v[i].second) {
        picked.pop();
        picked.push(v[i].second);
      }
    }
  }

  long long sol = 0;
  while (!picked.empty()) {
    sol += picked.top();
    picked.pop();
  }

  out << sol << std::endl;

  return 0;
}