这题O(n^3)都能水过

#include <bits/stdc++.h>
#define MAXN 1010
using namespace std;

int n, m;
long long dp[MAXN][MAXN];
int ar[MAXN][MAXN];
long long sum[MAXN][MAXN];
int main()
{
	memset(dp, -0x3f, sizeof(dp));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			scanf("%d", &ar[i][j]);
		}
	}

	for(int j = 1; j <= m; j++)
	{
		for(int i = 1; i <= n; i++)
		{
			sum[i][j] += (long long)sum[i-1][j] + ar[i][j];
			if(j == 1)
			{
				dp[1][i] = sum[i][1];
			}
			
		}
	}	
	for(int i = 2; i <= m; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			for(int k = 1; k <= j; k++)
			{
				dp[i][j] = max(dp[i-1][k] + sum[j][i] - sum[k-1][i], dp[i][j]);
			}
			for(int k = j; k <= n; k++)
			{
				dp[i][j] = max(dp[i-1][k] + sum[k][i] - sum[j-1][i], dp[i][j]);
			}
		}

	}
	printf("%lld", dp[m][n]);
	return 0;
}