折半搜索，先搜索一半的数字，记录第一个人的值，第二个人、第三个人和第一个人的差值，开个map哈希存一下，然后另一半搜完直接根据差值查找前一半的答案。
代码
#include<cstdio>
#include<map>
#define ll long long
#define N 100
using namespace std;
map<long long,int> ma,Ma;
char str[];
int n,i,a[N],b[N],c[N],Ans,A1,A2,ans[N];
void dfs(ll x,ll y,ll z,int d,int k)
{
if (d>n/)
{
long long tmp=(y-x)*+(z-x);
if ((ma.find(tmp)==ma.end())||(x>ma[tmp]))
{
ma[tmp]=x;
Ma[tmp]=k;
}
return;
}
dfs(x+a[d],y+b[d],z,d+,k*);
dfs(x,y+b[d],z+c[d],d+,k*+);
dfs(x+a[d],y,z+c[d],d+,k*+);
}
void Dfs(ll x,ll y,ll z,int d,int k)
{
if (d>n)
{
long long tmp=(x-y)*+(x-z);
if (ma.find(tmp)!=ma.end())
{
if (ma[tmp]+x>Ans)
{
Ans=ma[tmp]+x;
A1=Ma[tmp];
A2=k;
}
}
return;
}
Dfs(x+a[d],y+b[d],z,d+,k*);
Dfs(x,y+b[d],z+c[d],d+,k*+);
Dfs(x+a[d],y,z+c[d],d+,k*+);
}
int main()
{
scanf("%d",&n);
Ans=-0x37373737;int q=;
for (i=;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
/*
for (i=1;i<=n;i++)
{
scanf("%s",str);
if (str[0]=='L') q+=a[i];
}
printf("%d\n",q);
*/
dfs(,,,,);
Dfs(,,,n/+,); if (Ans==-0x37373737)
printf("Impossible");
else
{
//printf("%d\n",Ans);
for (i=n;i>n/;i--)
{
ans[i]=A2%;
A2=A2/;
}
for (i=n/;i>=;i--)
{
ans[i]=A1%;
A1=A1/;
}
for (i=;i<=n;i++)
if (ans[i]==)
printf("LM\n");
else
if (ans[i]==)
printf("MW\n");
else
if (ans[i]==)
printf("LW\n");
}
}