不明白为什么 WA
查看原帖
不明白为什么 WA
767561
Ascnbeta楼主2025/2/4 17:01

思路感觉没问题,看了官方 python 题解也没问题,但是就是 WA 了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5+10;
int n,k;
int a[maxn],b[maxn],c[maxn];
struct Pair{
	int i,j,k;
	bool operator < (const Pair &y) const{
		int sumx = a[i]*b[j]+b[j]*c[k]+c[k]*a[i];
		int sumy = a[y.i]*b[y.j]+b[y.j]*c[y.k]+c[y.k]*a[y.i];
		return sumx < sumy;
	}
};
inline int ret(const Pair y) {
	return a[y.i]*b[y.j]+b[y.j]*c[y.k]+c[y.k]*a[y.i];
}
priority_queue<Pair> q;
set<Pair> s;
signed main () {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1,greater<int>());
	for (int i = 1; i <= n; i++) cin >> b[i];
	sort(b+1,b+n+1,greater<int>());
	for (int i = 1; i <= n; i++) cin >> c[i];
	sort(c+1,c+n+1,greater<int>());
	q.push({1,1,1});
	for (int i = 1; i <= k; i++) {
		Pair t = q.top();
		if (i == k) {
			cout << ret(t) << '\n';
		}
		// cout << ret(t) << '\n';
		q.pop();
		if (t.i < n && s.find({t.i+1,t.j,t.k}) == s.end()) q.push({t.i+1,t.j,t.k}),s.insert({t.i+1,t.j,t.k});
		if (t.j < n && s.find({t.i,t.j+1,t.k}) == s.end()) q.push({t.i,t.j+1,t.k}),s.insert({t.i,t.j+1,t.k});
		if (t.k < n && s.find({t.i,t.j,t.k+1}) == s.end()) q.push({t.i,t.j,t.k+1}),s.insert({t.i,t.j,t.k+1});
	}
	return 0;
}
2025/2/4 17:01
加载中...