[제목 묘사]

칸마다 정수 (절대값이 10과 크지 않음) 가 있는 N*M의 행렬현재 서로 교차하지 않는 두 개의 서브 행렬 (같은 칸을 포함하지 않음) 을 구하여 그들의 가치의 곱셈이 가장 크다.
예를 들어 N=3, M=4와 같이 행렬은 그림과 같습니다.
2 3 4 5
1 3 2 4
4 3 2 1
최대 하위 행렬 값의 곱셈은 288이다.(왼쪽 두 열의 합은 16이고 오른쪽 두 열의 합은 18이며 결과는 16*18=288)이다.

[형식 입력]

첫 줄에는 두 개의 숫자 n, m(n, m < 100)이 있습니다.이후의 n줄은 줄마다 m개의 정수가 있다.

[출력 형식]

출력 파일은 두 개의 서로 교차하지 않는 서브 행렬 가치 곱셈의 최대 값만 있습니다.

[샘플 입력] [샘플 출력]

1 7                                                                                                         
128
-9 -9 8 8 1 7 -4
최대 서브 매트릭스 확장 문제는 음수의 경우 두 개의 부중합 서브 매트릭스는 반드시 가로축이나 세로축에 의해 분리된다. 우리는 가로선과 세로선을 매개하고 n^3 예처리 매트릭스를 통해 복잡도를 O(n^3)로 낮출 수 있다.

//f【i】    1   i ，   m      
//dp【i】    1   i ，   n       
#include
#include
#include
#include
#include
using namespace std;
int n,m,s[105][105],f[105],f2[105],f3[105],f4[105],dp[105],dp2[105],dp3[105],dp4[105],a[105],s2[105][105],ans=-0x3f3f3f3f;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		int x;
		scanf("%d",&x);
		s[i][j]=s[i-1][j]+x;
		s2[i][j]=s2[i][j-1]+x;
	}
	f[0]=-0x3f3f3f3f;
	f2[0]=0x3f3f3f3f;
	f3[n+1]=-0x3f3f3f3f;
	f4[n+1]=0x3f3f3f3f;
	dp[0]=-0x3f3f3f3f;
	dp2[0]=0x3f3f3f3f;
	dp3[m+1]=-0x3f3f3f3f;
	dp4[m+1]=0x3f3f3f3f;//    
	for(int i=1;i1;i--)
	{
		f3[i]=f3[i+1];
		for(int x=n;x>=i;x--)
		{
			a[1]=s[x][1]-s[i-1][1];
			f3[i]=max(f3[i],a[1]);
			for(int k=2;k<=m;k++)
			{
				a[k]=max(a[k-1]+s[x][k]-s[i-1][k],s[x][k]-s[i-1][k]);
				f3[i]=max(f3[i],a[k]);
			}
		}
	}//         
	for(int i=1;i1;i--)
	{
		f4[i]=f4[i+1];
		for(int x=n;x>=i;x--)
		{
			a[1]=s[x][1]-s[i-1][1];
			f4[i]=min(f4[i],a[1]);
			for(int k=2;k<=m;k++)
			{
				a[k]=min(a[k-1]+s[x][k]-s[i-1][k],s[x][k]-s[i-1][k]);
				f4[i]=min(f4[i],a[k]);
			}
		}
	}//        ，dp     
	for(int i=1;i1;i--)
	{
		dp3[i]=dp3[i+1];
		for(int x=m;x>=i;x--)
		{
			a[1]=s2[1][x]-s2[1][i-1];
			dp3[i]=max(dp3[i],a[1]);
			for(int k=2;k<=n;k++)
			{
				a[k]=max(a[k-1]+s2[k][x]-s2[k][i-1],s2[k][x]-s2[k][i-1]);
				dp3[i]=max(dp3[i],a[k]);
			}
		}
	}
	for(int i=1;i1;i--)
	{
		dp4[i]=dp4[i+1];
		for(int x=m;x>=i;x--)
		{
			a[1]=s2[1][x]-s2[1][i-1];
			dp4[i]=min(dp4[i],a[1]);
			for(int k=2;k<=n;k++)
			{
				a[k]=min(a[k-1]+s2[k][x]-s2[k][i-1],s2[k][x]-s2[k][i-1]);
				dp4[i]=min(dp4[i],a[k]);
			}
		}
	}
	for(int i=1;i