Codeforces 585D. Lizard Era: Beginning（meet in the middle）

　　一眼题...这个数据范围也太明显了吧...

　　suma1==suma2 && sumb1==sumb2 && sumc1==sumc2

　　相当于suma1-sumb1==sumb2-suma2 && suma1-sumc1==sumc2-suma2

　　于是前一半O(3^(N/2))搜出所有情况的suma1-sumb1和suma1-sumc1，后一半搜出sumb2-suma2和sumc2-suma2，都丢到一个数组里作为两个关键字排序，在两个关键字都相同的一段里面找到前一半最大的suma和后一半最大的suma，更新答案即可

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=, inf=1e9+;

struct poi{int x, y, st, a, ty;}v[maxn];

int n, cnt, ans, ansst1, ansst2;

int a[maxn], b[maxn], c[maxn], mi[];

void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline bool cmp(poi a, poi b){return a.x==b.x?(a.y<b.y):a.x<b.x;}

inline void printans(int x, int num)

{

    for(int i=;i<=num;i++)

    {

        int now=x%;

        if(now==) printf("LM\n");

        else if(now==) printf("LW\n");

        else printf("MW\n");

        x/=;

    }

}

int main()

{

    read(n);

    for(int i=;i<=n;i++) read(a[i]), read(b[i]), read(c[i]);

    int l=(n+)>>, r=n;

    mi[]=; for(int i=;i<=l;i++) mi[i]=mi[i-]*;

    for(int i=;i<=mi[l]-;i++)

    {

        int tmpa=, tmpb=, tmpc=;

        for(int j=;j<=l;j++)

        {

            int tmp=i/mi[j-]%;

            if(tmp==) tmpa+=a[j], tmpb+=b[j];

            else if(tmp==) tmpa+=a[j], tmpc+=c[j];

            else tmpb+=b[j], tmpc+=c[j];

        }

        v[++cnt].x=tmpa-tmpb; v[cnt].y=tmpa-tmpc; v[cnt].a=tmpa; v[cnt].st=i; v[cnt].ty=;

    }

    for(int i=;i<=mi[r-l]-;i++)

    {

        int tmpa=, tmpb=, tmpc=;

        for(int j=;j<=r-l;j++)

        {

            int tmp=i/mi[j-]%;

            if(tmp==) tmpa+=a[j+l], tmpb+=b[j+l];

            else if(tmp==) tmpa+=a[j+l], tmpc+=c[j+l];

            else tmpb+=b[j+l], tmpc+=c[j+l];

        }

        v[++cnt].x=tmpb-tmpa; v[cnt].y=tmpc-tmpa; v[cnt].a=tmpa; v[cnt].ty=; v[cnt].st=i;

    }

    sort(v+, v++cnt, cmp); ans=-inf;

    for(int i=, j=;i<=cnt;i=j)

    {

        int tmp1=-inf, tmp2=-inf, tmpst1=, tmpst2=;

        while(v[j].x==v[i].x && v[j].y==v[i].y)

        {

            if(v[j].ty==) {if(tmp1<v[j].a) tmp1=v[j].a, tmpst1=v[j].st;}

            else {if(tmp2<v[j].a) tmp2=v[j].a, tmpst2=v[j].st;}

            j++;

        }

        if(tmp1==-inf || tmp2==-inf) continue;

        if(tmp1+tmp2>ans) ans=tmp1+tmp2, ansst1=tmpst1, ansst2=tmpst2;

    }

    if(ans==-inf) return puts("Impossible"), ;

    printans(ansst1, l); printans(ansst2, r-l);

}