結果
問題 | No.2957 Combo Deck Builder |
ユーザー |
![]() |
提出日時 | 2024-11-09 01:21:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 1,000 ms |
コード長 | 4,634 bytes |
コンパイル時間 | 3,805 ms |
コンパイル使用メモリ | 269,796 KB |
実行使用メモリ | 20,092 KB |
最終ジャッジ日時 | 2024-11-09 01:22:19 |
合計ジャッジ時間 | 10,223 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using ull = unsigned long long;template <class T>using max_heap = priority_queue<T>;template <class T>using min_heap = priority_queue<T, vector<T>, greater<T>>;#define rep(i, l, r) for (ll i = (l); i < (r); i++)#define rrep(i, r, l) for (ll i = (r); i-- > (l);)#define all(x) begin(x), end(x)template <class T>bool chmin(T& lhs, T rhs) {return lhs > rhs ? (lhs = rhs, true) : false;}template <class T>bool chmax(T& lhs, T rhs) {return lhs < rhs ? (lhs = rhs, true) : false;}struct IOIO {IOIO() {cin.tie(0)->sync_with_stdio(0);}} ioio;template <class S, class T>ostream& operator<<(ostream& os, const pair<S, T>& p) {os << '(' << p.first << ", " << p.second << ')';return os;}template <class T>ostream& operator<<(ostream& os, const vector<T>& vs) {os << '{';rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", ");os << '}';return os;}template <class T>ostream& operator<<(ostream& os, const set<T>& vs) {os << '{';for (auto it = vs.begin(); it != vs.end(); it++) {if (it != vs.begin()) {os << ", ";}os << *it;}os << '}';return os;}template <class T, class U>ostream& operator<<(ostream& os, const map<T, U>& vs) {os << '{';for (auto it = vs.begin(); it != vs.end(); it++) {if (it != vs.begin()) {os << ", ";}os << *it;}os << '}';return os;}#ifdef DEBUGvoid dump_func() {cerr << endl;}template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail) {cerr << head;if (sizeof...(Tail) > 0) {cerr << ", ";}dump_func(std::move(tail)...);}#define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__)#else#define dump(...) static_cast<int>(0)#endifvoid solve() {int n;cin >> n;struct Card {int i;int c;ll x, y;};vector<Card> cards(n);rep(i, 0, n) cin >> cards[i].c >> cards[i].x >> cards[i].y, cards[i].i = i;ll ans = 0;for (auto& card: cards) {ll mn = min(card.x, card.y);ans += mn;card.x -= mn;card.y -= mn;}vector<char> used(n);const char X = 'X';const char Y = 'Y';dump(used);{min_heap<pair<ll, int>> que;vector<Card> a;for (auto card: cards)if (card.x < card.y) a.push_back(card);sort(all(a), [](auto lhs, auto rhs) { return lhs.c < rhs.c; });rep(i, 0, ssize(a)) {que.emplace(a[i].y, a[i].i);if (que.size() > a[i].c) {que.pop();}}while (!que.empty()) {auto [y, i] = que.top();que.pop();ans += y;used[i] = Y;}rep(i, 0, ssize(a)) {if (used[a[i].i] == 0) {used[a[i].i] = X;ans += a[i].x;}}}dump(used);{min_heap<pair<int, int>> que;for (auto card: cards) {if (card.x == card.y) {ans += card.x;used[card.i] = Y;} else if (card.x > card.y) {que.emplace(card.c, card.i);}}int used_num = n - count(all(used), 0);while (!que.empty()) {auto [c, i] = que.top();if (c <= used_num) {que.pop();ans += cards[i].x;used[i] = X;used_num++;} else {break;}}}dump(used);{min_heap<pair<ll, int>> que;vector<Card> a;rep(i, 0, n) if (used[i] == 0) {auto card = cards[i];card.c = n - card.c;a.push_back(card);}sort(all(a), [](auto lhs, auto rhs) { return lhs.c < rhs.c; });rep(i, 0, ssize(a)) {que.emplace(a[i].x, a[i].i);if (que.size() > a[i].c) {que.pop();}}while (!que.empty()) {auto [x, i] = que.top();que.pop();ans += x;used[i] = X;}rep(i, 0, ssize(a)) {if (used[a[i].i] == 0) {used[a[i].i] = Y;ans += a[i].y;}}}dump(used);cout << ans << '\n';}int main() {int t = 1;while (t--) solve();}