Submission #19272586

---

Source Code Expand

#include <iostream>
#include <queue>
#include <functional>
// #include <cstdint>

struct MachineState {
  int64_t cur_cost;
  int64_t increase;
};

bool operator>(const MachineState &state1, const MachineState &state2) {
  return state1.cur_cost > state2.cur_cost;
}

int main() {
  int64_t cur_cost, increase;
  size_t n_machine, n_present;
  std::cin >> n_machine >> n_present;

  std::priority_queue<MachineState, std::vector<MachineState>, std::greater<MachineState>> queue;
  for (size_t i = 0; i < n_machine; i++) {
    std::cin >> cur_cost >> increase;
    queue.push(MachineState{cur_cost, increase});
  }

  int64_t time = 0;
  for (size_t i = 0; i < n_present; i++) {
    MachineState state = queue.top();
    queue.pop();

    time += state.cur_cost;
    queue.push(MachineState{state.cur_cost + state.increase, state.increase});
  }

  std::cout << time << std::endl;
}

Submission Info

Judge Result