Submission #69370920

---

Source Code Expand

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

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, k;
  cin >> n >> k;

  vector<long long> a(n);
  vector<int> b(n), c(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i) >> b.at(i) >> c.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  vector<long long> result(n,0);

  //////////////////// 処理 ////////////////////

  // 店内の客の数
  int num = 0;

  // 現在時刻
  long long time = 0;

  // 退出予定一覧
  priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> que;

  // 早く来た客から順に処理
  for (int i=0; i<n; i++) {

    // 空き席数が足りなければ、空くまで待つ
    while (c.at(i)+num>k) {
      time = max(time,que.top().first);
      num -= que.top().second;
      que.pop();
    }

    // まだ客が到着していなければ、到着を待つ
    time = max(time,a.at(i));

    // 入店時刻を記録
    result.at(i) = time;

    // 客数と退出予定の更新
    num += c.at(i);
    que.emplace(time+b.at(i),c.at(i));

  }

  //////////////////// 出力 ////////////////////

  for (size_t i=0; i<result.size(); i++) {
    cout << result.at(i) << endl;
  }

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result