NC17060. 矩阵
描述
输入描述
第一行输入五个整数 R，C，X，Y，Z。接下来 N 行，每行输入 M 个整数，第 i 行第 j 列的整数表示 Mi,j。1 ≤ R,C ≤ 500.1 ≤ X ≤ R.
1 ≤ Y ≤ C.
1 ≤ Z ≤ R x C.
-109 ≤ Mi,j ≤ 109
输出描述
输出满足以上条件的最大子矩阵和。
示例1
输入:
5 5 3 3 4 0 0 10 0 0 3 4 0 2 3 -1 3 0 -8 3 0 0 32 -9 3 3 0 45 3 0
输出:
82
示例2
输入:
2 2 2 2 2 -1 -1 -1 -1
输出:
0
C++14(g++5.4) 解法, 执行用时: 2863ms, 内存消耗: 12392K, 提交时间: 2020-04-12 20:32:11
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,j,l,r,le,re,ans,X,Y,Z,q[1010],a[1010][1010],b[1010][1010],ze[1010][1010],c[1010],d[1010];
int main(){
scanf("%lld%lld%lld%lld%lld",&n,&m,&X,&Y,&Z);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
b[i][j]=b[i][j-1]+a[i][j];
ze[i][j]=ze[i][j-1]+(a[i][j]==0);
}
}
for(l=1;l<=m;l++)
for(r=l;r<=m;r++)if(r-l+1<=Y){
le=1;re=0;
for(i=1;i<=n;i++){
c[i]=c[i-1]+b[i][r]-b[i][l-1];
d[i]=d[i-1]+ze[i][r]-ze[i][l-1];
while(le<=re&&q[le]<=i-X)le++;
while(le<=re&&d[i]-d[q[le]-1]>Z)le++;
while(le<=re&&c[i-1]<=c[q[re]-1])re--;
q[++re]=i;
ans=max(ans,c[i]-c[q[le]-1]);
}
}
printf("%lld",ans);
}
C++(clang++ 11.0.1) 解法, 执行用时: 1058ms, 内存消耗: 12316K, 提交时间: 2023-03-26 15:57:09
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,j,l,r,le,re,ans,X,Y,Z,q[1010],a[1010][1010],b[1010][1010],ze[1010][1010],c[1010],d[1010];
int main(){
scanf("%lld%lld%lld%lld%lld",&n,&m,&X,&Y,&Z);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
b[i][j]=b[i][j-1]+a[i][j];
ze[i][j]=ze[i][j-1]+(a[i][j]==0);
}
}
for(l=1;l<=m;l++)
for(r=l;r<=m;r++)if(r-l+1<=Y){
le=1;re=0;
for(i=1;i<=n;i++){
c[i]=c[i-1]+b[i][r]-b[i][l-1];
d[i]=d[i-1]+ze[i][r]-ze[i][l-1];
while(le<=re&&q[le]<=i-X)le++;
while(le<=re&&d[i]-d[q[le]-1]>Z)le++;
while(le<=re&&c[i-1]<=c[q[re]-1])re--;
q[++re]=i;
ans=max(ans,c[i]-c[q[le]-1]);
}
}
printf("%lld",ans);
}