代码:
#include <bits/stdc++.h>
#define int __int128
int read() {
int s = 0, w = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) w = ch == '-' ? -1 : 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0';
return s * w;
}
void write(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int max(int _a, int _b) { return _a < _b ? _b : _a; }
int pow2[100], dp[100][100], N, M, m[100], ans = 0;
signed main() {
pow2[0] = 1;
for (signed i = 1; i <= 80; i ++) pow2[i] = pow2[i - 1] * 2;
N = read(), M = read();
for (int mx; N --;) {
mx = -1, memset(dp, 0, sizeof dp);
for (signed i = 1; i <= M; i ++) m[i] = read();
for (signed i = 1; i <= M; i ++)
for (signed j = M; j >= i; j --)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j] * pow2[M - j + i - 1]
* m[i - 1], dp[i][j + 1] * pow2[M - j + i - 1] * m[j + 1]));
for (signed i = 1; i <= M; i ++) mx = max(mx, dp[i][i] + m[i] * pow2[M]);
ans += mx;
}
write(ans);
return 0;
}