1 条题解
-
0青丘杨哲 LV 4 @ 2018-11-16 19:33:24
#include<bits/stdc++.h> using namespace std; const int MAXN=205; const int INF=100000000; int N,M,ans; int minval,maxval,tmp1,tmp2; int a[MAXN][MAXN],tmp[MAXN][MAXN]; int p[MAXN][MAXN],q[MAXN][MAXN],dp[MAXN]; void Transpose(){ for (int i=1;i<=M;i++) for (int j=1;j<=N;j++) tmp[i][j]=a[j][M-i+1]; swap(N,M); memset(a,0,sizeof(a)); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) a[i][j]=tmp[i][j]; } void Solve(){ memset(p,0,sizeof(p)); memset(q,0,sizeof(q)); for (int i=1;i<=N;i++){ memset(dp,0,sizeof(dp)); maxval=-INF,minval=INF; for (int j=i;j<=N;j++){ tmp1=tmp2=0; for (int k=1;k<=M;k++){ dp[k]+=a[j][k]; tmp1+=dp[k],tmp1=max(tmp1,0); maxval=max(maxval,tmp1); tmp2+=dp[k],tmp2=min(tmp2,0); minval=min(minval,tmp2); } p[i][j]=maxval,q[i][j]=minval; } } for (int i=1;i<=N-1;i++) for (int j=i;j<=N-1;j++){ ans=max(ans,p[i][j]*p[j+1][N]); ans=max(ans,q[i][j]*q[j+1][N]); } } int main(){ scanf("%d%d",&N,&M); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) scanf("%d",&a[i][j]); if (N*M==2){ if (N==1) printf("%d",a[1][1]*a[1][2]); if (M==1) printf("%d",a[1][1]*a[2][1]); return 0; } Solve(); Transpose(); Solve(); printf("%d",ans); return 0; }
- 1
信息
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 7
- 已通过
- 0
- 通过率
- 0%
- 上传者