結果
問題 |
No.1495 パンの仕入れ
|
ユーザー |
|
提出日時 | 2021-05-01 11:23:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 857 bytes |
コンパイル時間 | 756 ms |
コンパイル使用メモリ | 80,136 KB |
最終ジャッジ日時 | 2025-01-21 05:03:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 TLE * 26 |
ソースコード
#include <iostream> #include <vector> #include <queue> template <class T> using MaxHeap = std::priority_queue<T>; using namespace std; using lint = long long; void solve() { int n, m, k; cin >> n >> m >> k; vector<lint> cnt(n, 0), first(n, 0); lint ans = 0; while (m--) { int x; lint y; cin >> x >> y; --x; ++cnt[x]; first[x] += y * 2 - 1; ans += y * y; } MaxHeap<pair<lint, int>> heap; for (int i = 0; i < n; ++i) { heap.emplace(first[i], i); } while (k--) { auto [d, i] = heap.top(); heap.pop(); ans -= d; heap.emplace(d - cnt[i] * 2, i); } cout << ans << "\n"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int q; cin >> q; while (q--) solve(); return 0; }