区间动规+高精

经计算高精开50位已经足够

#include<bits/stdc++.h>
using namespace std;
long long m,n,a[105];
struct oppo {
    int a[55];
    oppo operator*(const int x) {
        oppo y;
        memset(y.a,0,sizeof(y.a));
        for(int i=1; i<=50; i++) {
            y.a[i]+=a[i]*x;
            y.a[i+1]+=y.a[i]/10;
            y.a[i]%=10;
        }
        return y;
    }
    oppo operator+(const oppo x) {
        oppo y;
        memset(y.a,0,sizeof(y.a));
        for(int i=1; i<=50; i++) {
            y.a[i]+=a[i]+x.a[i];
            y.a[i+1]+=y.a[i]/10;
            y.a[i]%=10;
        }
        return y;
    }
} p[105],dp[105][105],ans;
oppo maxx(oppo a,oppo b) {
    for(int i=50; i>0; i--)
        if(a.a[i]>b.a[i])
            return a;
        else if(b.a[i]>a.a[i])
            return b;
    return a;
}
int main() {
    p[0].a[1]=1;
    for(long long i=1; i<=100; i++)
        p[i]=p[i-1]*2;
    cin>>m>>n;
    while(m--) {
        memset(dp,0,sizeof(dp));
        for(long long i=1; i<=n; i++)
            scanf("%lld",&a[i]);
        for(long long len=1; len<=n; len++) {
            for(long long x=1; x+len-1<=n; x++) {
                long long y=x+len-1;
                dp[x][y]=maxx(dp[x+1][y]+p[n-len+1]*a[x],dp[x][y-1]+p[n-len+1]*a[y]);
            }
        }
        ans=ans+dp[1][n];
    }
    int tot=50;
    while(!ans.a[tot]&&tot>1)
        tot--;
    tot++;
    while(--tot)
        cout<<ans.a[tot];
    return 0;
}