testcase-data/Ours/test_cpp_code.cpp

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names

Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const ll INF=1e12;
const int LIM=6;
const int LIM_DEP=6;
struct Node
{
	int d,S[LIM+1];
	ll c;
};

bool cmp(Node x,Node y)
{
	if(x.d!=y.d) return x.d<y.d;
	if(x.c!=y.c) return x.c<y.c;
	for(int i=LIM;i>=0;i--) if(x.S[i]!=y.S[i]||!i) return x.S[i]<y.S[i];

}
bool chk(Node A,Node B) // check B<A
{
	if(A.d<B.d) return 0;
	if(A.c<B.c) return 0;
	for(int i=LIM,sa=0,sb=0;i>=0;i--)
	{
		sa+=A.S[i],sb+=B.S[i];
		if(sa<sb) return 0;
	}
	return 1;
}
Node merge(Node A,Node B) // move A to B
{
	Node C;
	C.c=A.c+B.c+(1LL<<A.d)+(1LL<<B.d)-2;
	if(A.d>=LIM_DEP)
	{
		C.c=2LL*INF;
		return C;
	}

	C.d=max(A.d,B.d)+1;
	for(int i=0;i<=LIM;i++) C.S[i]=B.S[i]+(i?A.S[i-1]:0);

	return C;
}
vector <Node> vec[105],now;
void print(Node x)
{
	cout<<x.c<<" "<<x.d<<"\n";
	for(int i=0;i<=LIM;i++) cout<<x.S[i]<<" ";
	cout<<"\n";
}
int n,a[105];
ll sum[105];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n),reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+1LL*a[i];
	ll ans=INF;
	for(int i=0;i<vec[n].size();i++)
	{
		Node t=vec[n][i];
		ll nw=t.c;
//		print(t);
//		system("pause");
		for(int j=0,k=0;j<=LIM;j++) nw+=1LL*j*(sum[k+t.S[j]]-sum[k]),k+=t.S[j];
		ans=min(ans,nw);
	}
	cout<<ans<<"\n";
}
void ins(Node x)
{
	if(x.c>INF) return;
	now.pb(x);
}
void qwq(int i)
{
	stable_sort(now.begin(),now.end(),cmp);
	for(int j=0;j<now.size();j++)
	{
		bool ok=1;
		for(int k=(int)(vec[i].size()-1);k<vec[i].size();k++) if(now[j].c>INF||chk(now[j],vec[i][k]))
		{
			ok=0;
			break;
		}
		if(ok) vec[i].pb(now[j]);
	}
	swap(vec[i],now),vec[i].clear();

}
void qwq2(int i)
{
//	sort(now.begin(),now.end(),cmp);
	for(int j=0;j<now.size();j++)
	{
		bool ok=1;
		for(int k=0;k<vec[i].size();k++) if(now[j].c>INF||chk(now[j],vec[i][k]))
		{
			ok=0;
			break;
		}
		if(ok) vec[i].pb(now[j]);
	}
}
signed main()
{
	Node tmp;
	tmp.d=0,tmp.c=0;
	memset(tmp.S,0,sizeof(tmp.S));
	tmp.S[0]=1;
	vec[1].pb(tmp);
	for(int i=2;i<=100;i++)
	{
		now.clear();
		for(int j=1;j<i;j++)
		{
			int k=i-j;
			if(j>k) break;
			if(j!=k)
			{
				for(int u=0;u<vec[j].size();u++) for(int v=0;v<vec[k].size();v++)
				{
//					cout<<j<<" "<<k<<" "<<u<<" "<<v<<"\n";
					if(!vec[j][u].S[LIM]) ins(merge(vec[j][u],vec[k][v]));
					if(!vec[k][v].S[LIM]) ins(merge(vec[k][v],vec[j][u]));
				}
			}
			else
			{
				for(int u=0;u<vec[j].size();u++) for(int v=u;v<vec[j].size();v++)
				{
					if(!vec[j][u].S[LIM]) ins(merge(vec[j][u],vec[j][v]));
					if(u!=v&&!vec[j][v].S[LIM]) ins(merge(vec[j][v],vec[j][u]));
				}
			}
			qwq(i);
		}
		qwq2(i);
	}

	int a=1;
	cin>>a;
	while(a--) solve();
	return 0;
}