求助灵异事件

问题：给出n*m的矩阵，n<=1000,m<=13，对于{1..m}的每一个子集S求出

\max_{i=1}^n\sum [j\in S]A_{ij}

这是个入门问题，所以我写了以下代码：

CPP

rep(i,1,n)rep(j,1,(1<<m)-1){
  int sum=0;rep(k,1,m)if((j>>(k-1))&1)sum+=a[i][k];
  ckmax(F[j],sum);
}

这个代码每个点要跑450ms

然后我TLE怀疑人生去鉴赏了一下一血的代码，发现他也是这样做的，但是他的循环顺序不一样

于是我修改了我的代码：

CPP

rep(j,1,(1<<m)-1)rep(i,1,n){
  int sum=0;rep(k,1,m)if((j>>(k-1))&1)sum+=a[i][k];
  ckmax(F[j],sum);
}

这个代码每个点跑80ms

以上

讨论操作