AcWing 4395. 最大子矩阵
原题链接
困难
作者:
专注的迪迦
,
2022-11-30 21:02:44
,
所有人可见
,
阅读 161
算法1
(前缀和加二分) $O(n^2)$
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N],b[N],sa[N],sb[N];
int s[N];
typedef long long ll;
int main(){
int n,m,k;
int ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++) {cin>>a[i];sa[i]=sa[i-1]+a[i];}
for(int i=1;i<=m;i++) {cin>>b[i];sb[i]=sb[i-1]+b[i];}
cin>>k;
int cnt=0;
memset(s,0x3f,sizeof s);
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++){
s[j-i]=min(s[j-i],sb[j]-sb[i-1]);//求每个长度的最小区间和,最终长度越大的区间和也越大。
}
}
sort(s,s+m);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int x=sa[j]-sa[i-1];
int b=upper_bound(s,s+m,double(k)/x)-s;
ans=max(ans,(j-i+1)*b);
}
}
cout<<ans;
return 0;
}