题解

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct dzs{
int ws,li[20];
};
int a[81][81],n,m;
dzs f[2][81][81][81],er[81],an,ans,pss1,pss2;
dzs gjc(int p1,dzs p2){ //高精乘单精
for(int i=1;i<=p2.ws;i++)
p2.li[i]*=p1;
for(int i=1;i<=p2.ws+5;i++){
if(i>p2.ws&&p2.li[i]!=0)p2.ws=i;
if(p2.li[i]>9999)p2.li[i+1]+=p2.li[i]/10000,p2.li[i]%=10000;
}
return p2;
}
dzs gjj(dzs p1,dzs p2){ //高精加
dzs p3;memset(p3.li,0,sizeof(p3.li));p3.ws=1;
for(int i=1;i<=max(p1.ws,p2.ws);i++)
p3.li[i]=p2.li[i]+p1.li[i];
for(int i=1;i<=p2.ws+5;i++){
if(i>p3.ws&&p3.li[i]!=0)p3.ws=i;
if(p3.li[i]>9999)p3.li[i+1]+=p3.li[i]/10000,p3.li[i]%=10000;
}
return p3;
}
dzs maxd(dzs p1,dzs p2){ //取大数
if(p1.ws>p2.ws)return p1;
if(p2.ws>p1.ws)return p2;
for(int i=p1.ws;i>=1;i--){
if(p1.li[i]>p2.li[i])return p1;
if(p1.li[i]<p2.li[i])return p2;
}
return p1;
}
int print(dzs p1){
for(int i=p1.ws;i>=1;i--){
if(i==p1.ws){
cout<<p1.li[i];continue;
}
if(p1.li[i]<10)cout<<"000";
else if(p1.li[i]<100)cout<<"00";
else if(p1.li[i]<1000)cout<<"0";
cout<<p1.li[i];
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
er[1].li[1]=2;er[1].ws=1;
for(int i=2;i<=m;i++){
er[i]=gjc(2,er[i-1]);
}//计算2^i(gao jing)
for(int k=1;k<=n;k++)//第k行
for(int i=1;i<=m;i++){//第i次取数
for(int j=1;j<=i;j++){
f[0][k][i][j]=gjj(maxd(f[0][k][i-1][j-1],f[1][k][i-1][m-(i-j)+1]),gjc(a[k][j],er[i]));
}
for(int j=m-i+1;j<=m;j++){
f[1][k][i][j]=gjj(maxd(f[1][k][i-1][j+1],f[0][k][i-1][i-(m-j+1)]),gjc(a[k][j],er[i]));
}
}
memset(ans.li,0,sizeof(ans.li));ans.ws=1;
for(int k=1;k<=n;k++){
an.ws=1;memset(an.li,0,sizeof(an.li));
for(int i=1;i<=m;i++){
an=maxd(an,f[0][k][m][i]);
an=maxd(an,f[1][k][m][i]);
}
ans=gjj(ans,an);
}
print(ans);
cout<<endl;
return 0;
}