CODE THANKS FESTIVAL 2017: C - Factory

問題

C - Factory

解説

priority_queueを用いて生成時間が小さい順に時間を計算する。回分の和を取れば良い。

template<class T> using PQ_G = priority_queue<T, vector<T>, greater<T>>;
template<class T> using PQ_G = priority_queue<T, vector<T>, greater<T>>;

int main() {
  int N, K; cin >> N >> K;
  vector<int> av(N), bv(N);
  rep(i, N) cin >> av[i] >> bv[i];
  PQ_G<tuple<int64_t, int, int>> pq; // value, cnt, idx
  rep(i, N) {
    pq.emplace(av[i], 0, bv[i]);
  }
  int64_t sum = 0;
  while (!pq.empty()) {
    auto p = pq.top(); pq.pop();
    int64_t a, cnt, b; tie(a, cnt, b) = p;
    pq.emplace(a + b, cnt + 1, b);
    sum += a;
    K--;
    if (K == 0) break;
  }
  cout << sum << endl;
}