結果

問題 No.3459 Defeat Slimes
コンテスト
ユーザー cho435
提出日時 2026-02-28 14:44:29
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 316 ms / 3,000 ms
コード長 1,386 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,529 ms
コンパイル使用メモリ 388,800 KB
実行使用メモリ 23,796 KB
最終ジャッジ日時 2026-02-28 14:44:49
合計ジャッジ時間 16,073 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:34:35: warning: '((std::array<long long int, 3>::value_type*)<unknown>)[2305843009213693950]' may be used uninitialized [-Wmaybe-uninitialized]
   34 |                         mp[ar[2]] += ar[1];
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/string:51,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bitset:54,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:1:
In member function 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = long long int]',
    inlined from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(_Base_ptr, _Base_ptr, const _Key&) const [with _Key = long long int; _Val = std::pair<const long long int, __int128>; _KeyOfValue = std::_Select1st<std::pair<const long long int, __int128> >; _Compare = std::less<long long int>; _Alloc = std::allocator<std::pair<const long long int, __int128> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_tree.h:2604:29,
    inlined from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = long long int; _Val = std::pair<const long long int, __int128>; _KeyOfValue = std::_Select1st<std::pair<const long long int, __int128> >; _Compare = std::less<long long int>; _Alloc = std::allocator<std::pair<const long long int, __int128> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_tree.h:1894:16,
    inlined from 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = long long int; _Tp = __int128; _Compare = std::less<long long int>; _Alloc = std::all

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

using mint = atcoder::modint998244353;
using i128 = __int128_t;

void solve() {
	ll n, y, z;
	cin >> n >> y >> z;
	vector<array<ll, 3>> lcx(n);
	rep(i, 0, n) {
		cin >> lcx[i][1] >> lcx[i][0] >> lcx[i][2];
	}
	sort(all(lcx));
	reverse(all(lcx));
	map<ll, i128> mp;
	ll next_lv = -1;
	auto pop_lv = [&]() {
		while (!lcx.empty()) {
			auto& ar = lcx.back();
			if (ar[0] > y) break;
			lcx.pop_back();
			mp[ar[2]] += ar[1];
		}
		if (!lcx.empty()) next_lv = min(z, lcx.back()[0]);
		else next_lv = z;
	};
	pop_lv();
	ll ans = 0;
	while (!mp.empty() && y < z) {
		auto itr = --mp.end();
		auto [ad, cnt] = *itr;
		ll nd = (next_lv - y + ad - 1) / ad;
		if (nd >= cnt) {
			y += ad * cnt;
			ans += cnt;
			mp.erase(itr);
			if (y >= next_lv) pop_lv();
			continue;
		}
		itr->second -= nd;
		y += ad * nd;
		ans += nd;
		pop_lv();
	}
	if (y < z) cout << "-1\n";
	else cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0