Problem - C - Codeforces
给定两个正整数数组 a 和 b，长度分别为 n 和 m。
定义矩阵 c 为一个 n×m 的矩阵，其中 ci,j=ai⋅bj。
你需要在矩阵 c 中找到一个子矩形，使得它的元素之和最多为 x，并且它的面积（即元素总数）尽可能大。
具体来说，你需要找到最大的数字 s，使得能够选择整数 x1、x2、y1、y2 满足 1≤x1≤x2≤n，1≤y1≤y2≤m，(x2−x1+1)×(y2−y1+1)=s 且
∑i=x1x2∑j=y1y2ci,j≤x。
输入格式 第一行包含两个整数 n 和 m（1≤n,m≤2000）。
第二行包含 n 个整数 a1,a2,…,an（1≤ai≤2000）。
第三行包含 m 个整数 b1,b2,…,bm（1≤bi≤2000）。
第四行包含一个整数 x（1≤x≤2⋅109）。
输出格式 如果能够选择四个整数 x1、x2、y1、y2 满足 1≤x1≤x2≤n，1≤y1≤y2≤m 并且 ∑x2i=x1∑y2j=y1ci,j≤x，则输出所有这样的四元组中 (x2−x1+1)×(y2−y1+1) 的最大值，否则输出 0。
Examples
input
Copy
3 3 1 2 3 1 2 3 9
output
Copy
4
input
Copy
5 1 5 4 2 4 5 2 5
output
Copy
1
题解:
如果一开始啥也不考虑,直接模拟数组,找二维前缀和,这道题就寄了,
我们应该从题目根本去考虑,这个得到的矩阵究竟意味着什么
真的稍微仔细想想,我们其实就可以发现,矩阵中任意一个子矩阵和,都是两个数组连续段的和相乘的结果
到这里这题就基本解出来了,接着暴力求两个数组长度为x的连续子段最小的和即可,
然后枚举长度1~n和1~m的两个数组相乘的结果,矩阵最大且小于等于k的即为答案
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int mod = 1e9 + 7;
int a[2005];
int b[2005];
int r[2004];
int c[2004];
void solve()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
a[i] = a[i - 1] + a[i];
}
for(int i = 1;i <= m;i++)
{
cin >> b[i];
b[i] = b[i - 1] + b[i];
}
memset(r,0x3f,sizeof r);
memset(c,0x3f,sizeof c);
for(int i = 1;i <= n;i++)
{
for(int j = 0;j < i;j++)
r[i - j] = min(r[i - j],a[i] - a[j]);
}
int k;
cin >> k;
for(int i = 1;i <= m;i++)
{
for(int j = 0;j < i;j++)
c[i - j] = min(c[i - j],b[i] - b[j]);
}
int ans = 0;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(r[i]*c[j] <= k)
ans = max(ans,i*j);
}
}
cout << ans;
}
signed main()
{
// ios::sync_with_stdio(0 );
// cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
