标准记忆化搜索

#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>
using namespace std;
#define inf 0x3f3f3f3f
#define minf 0x3f
#define inp(x) cin>>x
#define otp(x) cout<<x
#define otp_nl(x) cout<<x<<"\n"
#define otp_sp(x) cout<<x<<" "
#define int long long
#define veci vector<int>
#define str string
#define pb(x) push_back(x)
#define fr(k,len) for(k=0;k<len;k++)
#define nfr(k,len) for(int k=0;k<len;k++)
#define ret return
#define db long double
#define all(x) x.begin(),x.end()

namespace my_stl {

}

int qpow(int a, int t, int p) {
	a %= p;
	int b[64];
	b[0] = a;
	nfr(i, 63)b[i + 1] = (b[i] * b[i]) % p;
	int ans = 1;
	nfr(i, 64) {
		if (t & (1 << i)) {
			ans *= b[i];
			ans %= p;
		}
	}
	ret ans;
}

int gcd(int a, int b) {
	ret (b ? (gcd(b, a % b)) : a);
}

int invp(int a, int p) {
	ret qpow(a, p - 2, p);
}
int x, y;

void exgcd(int a, int b, bool f) {
	if (f)
		x = 0, y = 0;
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b, false);
	int tx = x;
	x = y;
	y = tx - a / b * y;
}

int inv(int a, int p) {
	exgcd(a, p, true);
	return (x + p) % p;
}
#define ll __int128

void printll(ll x, bool f) {
	if (!(x || f))
		return;
	printll(x / 10, false);
	putchar(x % 10 + '0');
}
ll dp[100][100][100];
int a[100][100];
int n, m;

ll dfs(int l, int r, int k) {
	if (l >= r)
		return 0;
	if (l + 1 == r)
		return (ll)a[k][l];
	if (dp[l][r][k])
		return dp[l][r][k];
	return dp[l][r][k] = max(dfs(l, r - 1, k) + a[k][r] << (m - r + l + 1), dfs(l + 1, r, k) + a[k][l] << (m - r + l + 1));
}

void solve() {
	cin >> n >> m;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
		printll(dfs(0, m, i), true);
		cout << endl;
		ans += dfs(0, m, i);
		for (int j = 0; j <= m; j++) {
			for (int k = j + 1; k <= m; k++) {
				printf("dp[%d][%d][%d]=", j, k, i);
				printll(dfs(j, k, i), true);
				cout << endl;
			}
		}
	}
	printll(ans, true);
	ret;
}

signed main() {
	int t = 1;
	nfr(i, t) {
		solve();
	}
	ret 0;
}