結果
問題 | No.2957 Combo Deck Builder |
ユーザー |
![]() |
提出日時 | 2024-11-11 16:35:05 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 1,000 ms |
コード長 | 2,004 bytes |
コンパイル時間 | 2,733 ms |
コンパイル使用メモリ | 207,088 KB |
実行使用メモリ | 19,964 KB |
最終ジャッジ日時 | 2024-11-11 16:35:16 |
合計ジャッジ時間 | 11,256 ms |
ジャッジサーバーID (参考情報) |
judge1 / 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 queueX>=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;}