1 条题解
-
0Guest LV 0 MOD
-
0
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
int n,m,a[305][305],MIN[305],b[305],dp[305][2],i,j,s[305][305],ans,P,k;
int main()
{
while (cin>>n)
{
ans=-1000000000;
scanf("%d%d",&m,&P); assert(1<=n && n<=300 && 1<=m && m<=300 && -1000<=P && P<=1000);
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) {scanf("%d",&a[i][j]); assert(-1000<=a[i][j] && a[i][j]<=1000); }
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
s[i][j]=s[i-1][j]+a[i][j];
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++) MIN[j]=a[i][j];
for (j=i; j<=n; j++)
{
for (k=1; k<=m; k++) MIN[k]=min(MIN[k],a[j][k]);
for (k=1; k<=m; k++) b[k]=s[j][k]-s[i-1][k]; dp[0][1]=-1000000000;
for (k=1; k<=m; k++) dp[k][0]=max(dp[k-1][0]+b[k],b[k]),dp[k][1]=max(max(dp[k-1][1]+b[k],dp[k-1][0]+b[k]-MIN[k]+P),b[k]-MIN[k]+P);
for (k=1; k<m; k++) ans=max(ans,max(dp[k][0],dp[k][1]));
if (i==1 && j==n)
{
ans=max(ans,dp[m][1]); int sum=0;
for (k=m; k>1; k--) {sum+=b[k]; ans=max(ans,sum);}
} else
ans=max(ans,max(dp[m][1],dp[m][0]));
}
}
cout<<ans<<endl;
}
return 0;
}
- 1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 3
- 已通过
- 1
- 通过率
- 33%
- 上传者