結果

問題 No.3459 Defeat Slimes
コンテスト
ユーザー startcpp
提出日時 2026-02-28 15:11:00
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 451 ms / 3,000 ms
コード長 2,116 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,283 ms
コンパイル使用メモリ 107,880 KB
実行使用メモリ 21,836 KB
最終ジャッジ日時 2026-02-28 15:11:25
合計ジャッジ時間 15,199 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int n, Y, Z;
int C[200001], L[200001], X[200001];

signed main() {
	int i;

	cin >> n >> Y >> Z;
	vector<T> vecT;
	rep(i, n) {
		cin >> C[i] >> L[i] >> X[i];
		vecT.push_back(T(L[i], C[i], X[i]));
	}
	sort(vecT.begin(), vecT.end());
	rep(i, n) {
		L[i] = get<0>(vecT[i]);
		C[i] = get<1>(vecT[i]);
		X[i] = get<2>(vecT[i]);
	}
	L[n] = (1LL << 60);

	int cor = 0;
	priority_queue<P> que;	//(level_up, count)
	while (cor < n && L[cor] <= Y) {
		que.push(P(X[cor], C[cor]));
		cor++;
	}

	int level = Y, ans = 0;
	while (!que.empty()) {
		P now = que.top(); que.pop();
		int cnt1 = (Z - level + now.first - 1) / now.first;
		int cnt2 = (L[cor] - level + now.first - 1) / now.first;

		/*cout << "level: " << level << ", ans: " << ans << ", cnt1: " << cnt1 << ", cnt2: " << cnt2 << endl;
		priority_queue<P> que2 = que;
		cout << "now = " << now.first << ", " << now.second << endl;
		cout << "que2:" << endl;
		while (!que2.empty()) {
			P now2 = que2.top(); que2.pop();
			cout << "  " << now2.first << ", " << now2.second << endl;
		}
		cout << endl;*/

		if (cnt1 <= cnt2) { //新しいスライムが追加される前に終了する
			if (cnt1 <= now.second) { //今のスライムで終わる
				ans += cnt1;
				level += now.first * cnt1;
				break;
			}
			else { //今のスライムが全て倒される
				ans += now.second;
				level += now.first * now.second;
			}
		}
		else {
			if (cnt2 <= now.second) {
				ans += cnt2;
				level += now.first * cnt2;
				//スライムの追加
				if (now.second - cnt2 >= 1) {
					que.push(P(now.first, now.second - cnt2));
				}
				que.push(P(X[cor], C[cor]));
				cor++;
			}
			else {
				ans += now.second;
				level += now.first * now.second;
			}
		}
	}
	//cout << "level: " << level << ", ans: " << ans << endl;

	if (level < Z) { cout << -1 << endl; }
	else { cout << ans << endl; }
	return 0;
}
0