結果
問題 | No.2957 Combo Deck Builder |
ユーザー |
![]() |
提出日時 | 2024-11-11 16:35:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 1,000 ms |
コード長 | 2,004 bytes |
コンパイル時間 | 2,242 ms |
コンパイル使用メモリ | 200,764 KB |
最終ジャッジ日時 | 2025-02-25 03:54:44 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/modint> using namespace std; //using namespace atcoder; using ll = long long; //using mint = modint998244353; template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* X>=Yであるカードはできるだけ後ろに回す。 X<Yであるカードのみ考える。 Cの昇順にY-Xが大きい(Xにした時の損失が大きい)ものから順に使っていく。 ただし、使ったカード枚数がCになった時点でXにする。 C+1のカードを追加する時は、Y-Xが小さいカードから捨てていく。 ->priority queue X>=Yであるカードについて考える。 Cの降順にX-Yが大きいものから順に使っていく。 ただし、使ったカード枚数がN-Cになった時点でYにする。 C-1のカードを追加するときは、X-Yが小さいカードから捨てていく。 */ ll N, S=0, C, X, Y; cin >> N; vector<vector<ll>> v(N+1), v2(N+1); for (int i=1; i<=N; i++){ cin >> C >> X >> Y; if (X<Y){ v[C].push_back(Y-X); S += X; //とりあえずXにしておく。 } else{ v2[C].push_back(X-Y); S += Y; //とりあえずYにしておく。 } } pq<ll> que, que2; for (int C=0; C<=N; C++){ for (auto z : v[C]){ que.push(z); S += z; if (que.size() > C){ ll w = que.top(); que.pop(); S -= w; } } } for (int C=N; C>=0; C--){ for (auto z : v2[C]){ que2.push(z); S += z; if (que2.size() > N-C){ ll w = que2.top(); que2.pop(); S -= w; } } } cout << S << endl; return 0; }