[NOIP 2007 提高组] 矩阵取数游戏

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 80;
int n, m;
int a[MAXN + 5];
__int128 two[MAXN + 5];
__int128 dp[MAXN + 5][MAXN + 5];
void out(__int128 x)
{
    if (x / 10 > 0)
        out(x / 10);
    cout << (int)(x % 10);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    two[0] = 1;
    for (int i = 1; i <= m; i++)
        two[i] = two[i - 1] * 2;
    __int128 ans = 0;
    while (n--)
    {
        for (int i = 1; i <= m; i++)
            cin >> a[i];
        for (int len = 1; len <= m; len++)
        {
            for (int l = 1; l + len - 1 <= m; l++)
            {
                int r = l + len - 1;
                if (len == 1)
                {
                    dp[l][r] = a[l] * two[m];
                    continue;
                }
                dp[l][r] = max(dp[l + 1][r] + a[l] * two[m - len + 1],
                               dp[l][r - 1] + a[r] * two[m - len + 1]);
            }
        }
        ans += dp[1][m];
    }
    out(ans);
    return 0;
}