首先可以观察到，假设序列中三个元素 \(a \geq b \geq c\)，那么可以得到
\[a \geq b \Rightarrow ab - bc \geq ab - ac \Rightarrow (a-c)b \geq (b-c)a
\\
b \geq c \Rightarrow ab - bc \geq ac - bc \Rightarrow (a-c)b \geq (a-b)c
\]
把原序列 X 从小到大排序，那么我们可以知道 \(A_i > C_i > B_i\)，这可以由排序不等式可以得到。不妨设 \(C_i > C_{i+1}\)，那么要最大化答案，需要 \(A_i > A_{i+1}\)，\(B_i < B_{i+1}\)。
由于 \(A_i > C_i > C_N > B_N\)，所以可以直接钦定 \(B_i\) 为前 N 个位置。剩下只需要考虑 \([N + 1, 3N]\) 上的问题。
考虑两个两个确定位置，设当前已经确定了 \(x\) 组 \((A_i, C_i)\) 的位置，那么由于 \(A_i > C_i\)，区间 \([3N - x + 1, 3N]\) 一定都被选走了，这是因为如果中间空了一个位置 \(p\)，那么总会有某个 \(A_j < A_i\) 或者 \(C_j < C_i\) 填到 \(p\) 上，不符合我们先前确定的大小关系。同样的，区间 \([N + 1, 2N - x]\) 一定都没被选走，这是因为最坏情况下，\(C_i\) 从 \(2N\) 开始填起，同时如果中间被填了某个位置，也会破坏大小关系。
所以我们实际需要维护的位置只有 \([2N - x + 1, 3N - x]\)，长度为 \(N\)，这本质上是在 \([N + 1, 3N]\) 上做滑动窗口。时间复杂度 \(O(N 2^N)\)，在滑动窗口更新答案的时候可以根据 \(C_i\) 的大小关系剪枝，跑不满所以能过。
参考实现是把 \([N + 1, 3N]\) 从大到小排序。
#include <bits/stdc++.h>
#define fi first
#define se secondusing i64 = long long;
using u64 = unsigned long long;
using PII = std::pair<int, int>;
using std::cin, std::cout, std::cerr, std::vector;int n;
char ppc[(1 << 25) + 2];void init(int n) {ppc[0] = 0;for (int s = 1; s <= n; ++s) {ppc[s] = ppc[s >> 1] + (s & 1);}
}void solve() {vector<int> c(n * 3);for (int i = 0; i < n * 3; ++i) {cin >> c[i];}std::sort(c.begin(), c.end());vector<int> b, a;for (int i = 0; i < n; ++i) {b.push_back(c[i]);}for (int i = n; i < n * 3; ++i) {a.push_back(c[i]);}std::reverse(a.begin(), a.end());vector<int> f((1 << n), 0);for (int s = 0; s < (1 << n) - 1; ++s) {int x = ppc[s];int lst = 0;while ((s >> lst) & 1) {++lst;}int ss = ((s | (1 << lst)) >> 1);for (int i = n - 1; i >= lst; i--) {if ((ss >> i) & 1) {break;}f[ss | (1 << i)] = std::max(f[ss | (1 << i)], f[s] + (a[x + lst] - b[x]) * a[x + i + 1]);}}cout << f[(1 << n) - 1] << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);init(1 << 25);int T = 1;cin >> T; cin >> n;while (T--) {solve();}return 0;
}