记录编号	611345	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[THUPC 2025 Final] 图，距离，最优化	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	24.061 s
提交时间	2026-01-28 12:26:33	内存使用	12.81 MiB

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int _ = 6e5 + 7;
ll dp[_], tmp[_], x[_], sumx[_]; int T, N;

int main(){
  freopen("thupc2025_gradistoptimiz.in", "r", stdin);
  freopen("thupc2025_gradistoptimiz.out", "w", stdout);
	cin >> T;
	for(int _ = 1 ; _ <= T ; ++_){
		cin >> N; for(int i = 1 ; i <= N ; ++i) cin >> x[i];
		sort(x + 1, x + N + 1);
		for(int i = 1 ; i <= N ; ++i) sumx[i] = sumx[i - 1] + x[i];
		memset(dp, -0x3f, sizeof(dp)); dp[0] = 0;
		for(int i = N ; i > 1 ; --i){
			memset(tmp, -0x3f, sizeof(tmp));
			for(int j = 0 ; j <= sumx[N] - sumx[i] ; ++j)
				if(dp[j] != tmp[_ - 1]){
					tmp[j] = max(tmp[j], dp[j] + (sumx[N] - sumx[i - 1] - j) * (sumx[i - 1] + j));
					tmp[j + x[i]] = max(tmp[j + x[i]], dp[j] + (j + x[i]) * (sumx[N] - j - x[i]));
				}
			memcpy(dp, tmp, sizeof(dp));
		}
		ll mx = 0; for(int i = 0 ; i <= sumx[N] ; ++i) mx = max(mx, dp[i]);
		cout << mx << endl;
	}
	return 0;
}