結果
問題 | No.2957 Combo Deck Builder |
ユーザー |
![]() |
提出日時 | 2024-11-08 22:29:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 276 ms / 1,000 ms |
コード長 | 1,704 bytes |
コンパイル時間 | 1,070 ms |
コンパイル使用メモリ | 86,136 KB |
実行使用メモリ | 10,060 KB |
最終ジャッジ日時 | 2024-11-08 22:29:58 |
合計ジャッジ時間 | 11,137 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
//Zabutonみがある。#include <iostream>#include <algorithm>#include <vector>#include <queue>#define rep(i, n) for(i = 0; i < n; i++)#define int long long //これ!!!using namespace std;typedef pair<int, int> P; //(C, max(X, Y) - min(X, Y))int n;vector<P> vec1;vector<P> vec2;signed main() {int i, ans = 0;cin >> n;rep(i, n) {int c, x, y;cin >> c >> x >> y;if (x > y) { //c枚以上で使う or x - yだけ罰金vec2.push_back(P(c, x - y));}else { //c枚未満で使う or y - xだけ罰金vec1.push_back(P(c, y - x));}ans += max(x, y);}sort(vec1.begin(), vec1.end());sort(vec2.begin(), vec2.end(), greater<P>());priority_queue<int, vector<int>, greater<int>> que;rep(i, vec1.size()) {int c = vec1[i].first;int pena = vec1[i].second;//cout << "que.size(): " << que.size() << ", vec1[" << i << "]: c=" << c << ", pena=" << pena << endl;if (c == 0) {ans -= pena;}else {if (que.size() >= c) {int pena2 = que.top();if (pena2 < pena) {ans -= pena2;que.pop();que.push(pena);}else {ans -= pena;}}else {que.push(pena);}}}while (!que.empty()) que.pop();rep(i, vec2.size()) {int c = n - vec2[i].first;int pena = vec2[i].second;//cout << "que.size(): " << que.size() << ", vec2[" << i << "]: c=" << c << ", pena=" << pena << endl;if (c == 0) {ans -= pena;}else {if (que.size() >= c) {int pena2 = que.top();if (pena2 < pena) {ans -= pena2;que.pop();que.push(pena);}else {ans -= pena;}}else {que.push(pena);}}}cout << ans << endl;return 0;}