Submission #64560363

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
void solve() {
	int n, k;
	cin >> n >> k;
	priority_queue<tuple<int, int, int>> px, py, pz;
	vector<bool> v(n);
	for (int i = 0; i < n; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		px.emplace(x, -y-z, i);
		py.emplace(y, -x-z, i);
		pz.emplace(z, -x-y, i);
	}
	auto t2 = [&] (priority_queue<tuple<int,int,int>> & pq, bool drop) -> pair<ll,ll> {
		while (v[get<2>(pq.top())]) pq.pop();
		auto p1 = pq.top();
		pq.pop();
		while (v[get<2>(pq.top())]) pq.pop();
		auto p2 = pq.top();
		pq.pop();
		if (!drop) {
			pq.push(p1);
			pq.push(p2);
		} else {
			v[get<2>(p1)] = true;
			v[get<2>(p2)] = true;
		}
		return {get<0>(p1) + get<0>(p2), get<1>(p1) + get<1>(p2)};
	};
	ll ans = 0;
	while (k--) {
		auto ax = t2(px, false);
		auto ay = t2(py, false);
		auto az = t2(pz, false);
		if (ax >= ay && ax >= az) {
			ans += ax.first;
			t2(px, true);
		} else if (ay >= ax && ay >= az) {
			ans += ay.first;
			t2(py, true);
		} else {
			ans += az.first;
			t2(pz, true);
		}
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) solve();
}

Submission Info

Judge Result