# Mirror【省选模拟赛】

## yanQval毒瘤题

Posted by yjjr's blog on March 27, 2018

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define inf 1e9
const int maxn=(1<<10)+6;
char st[26][26];
int n,m,h[maxn],cnt[maxn],f[maxn][200],g[maxn][200],ans[maxn];
int main()
{
freopen("mirror.in","r",stdin);
freopen("mirror.out","w",stdout);
rep(i,1,n)scanf("%s",st[i]+1);
rep(sta,0,(1<<n)-1){
int t=0,x=-1;
rep(i,0,n-1)
if((sta>>i)&1){
t+=x*i;
x*=-1;
}
if(x==1)h[sta]=-inf;else h[sta]=t;
}
rep(sta,0,(1<<n)-1)cnt[sta]=cnt[sta>>1]+(sta&1);
rep(sta,0,(1<<n))rep(i,0,n*m)f[sta][i]=-inf;
f[0][0]=0;
rep(j,1,m){
memcpy(g,f,sizeof f);
rep(sta,0,(1<<n))rep(i,0,n*m)f[sta][i]=-inf;
int tmp=0;
rep(i,1,n)if(st[i][j]=='1')tmp^=1<<i-1;
rep(sta,0,(1<<n))
rep(i,0,n*m)
if(g[sta][i]>-inf){
for(int s=tmp;;s=(s-1)&tmp){
int t=g[sta][i]+h[s],nm=cnt[s],nm2=cnt[s&sta];
t+=j*(nm2+nm2-nm);
f[sta^s][i+nm]=max(f[sta^s][i+nm],t);
if(!s)break;
}
}
}
rep(i,0,n*m)ans[i]=f[0][i];
rep(i,1,n*m)ans[i]=max(ans[i],ans[i-1]);
rep(i,0,n*m)printf("%d ",4*n*m-2*ans[i]);printf("\n");
return 0;
}