代码拉取完成,页面将自动刷新
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
/**
* https://www.acwing.com/problem/content/description/4398/
* 思路:
* 首先,不用把矩阵构造出来,子矩阵的面积和就是2个数组区间和的乘积
* 预处理出每个区间长度下,区间和的最小值
* 枚举区间每个长度,算出结果
*/
const int N = 2005;
int n,m;
int s1[N],s2[N];
int a[N],b[N];
int main(){
cin>>n>>m;
for(int i = 1; i <=n; i++) {
int x;
cin>>x;
s1[i] = s1[i-1]+x;
}
for(int i = 1; i <=m; i++) {
int x;
cin>>x;
s2[i] = s2[i-1]+x;
}
int limit;
cin>>limit;
//枚举每个区间长度
memset(a,0x3f,sizeof a);
memset(b,0x3f,sizeof b);
for(int i = 1; i <=n; i++) {
for(int j = 1; j+i-1 <=n; j++) {
a[i] = min(s1[j+i-1]-s1[j-1],a[i]);
}
}
for(int i = 1; i <=m; i++) {
for(int j = 1; j+i-1 <=m; j++) {
b[i] = min(s2[j+i-1]-s2[j-1],b[i]);
}
}
int ans = 0;
for(int i = n; i; i--) {
for(int j = m; j ; j--) {
//注意这里相乘会报int
if ((LL)a[i]*b[j]<=limit){
ans = max(ans,i*j);
}
}
}
cout<<ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。