You are given two arrays aa and bb of positive integers, with length nn and mm respectively.

Let cc be an n×mn×m matrix, where ci,j=ai?bjci,j=ai?bj.

You need to find a subrectangle of the matrix cc such that the sum of its elements is at most xx, and its area (the total number of elements) is the largest possible.

Formally, you need to find the largest number ss such that it is possible to choose integers x1,x2,y1,y2x1,x2,y1,y2 subject to 1≤x1≤x2≤n1≤x1≤x2≤n, 1≤y1≤y2≤m1≤y1≤y2≤m, (x2?x1+1)×(y2?y1+1)=s(x2?x1+1)×(y2?y1+1)=s, and
∑i=x1x2∑j=y1y2ci,j≤x.
∑i=x1x2∑j=y1y2ci,j≤x.
Input
The first line contains two integers nn and mm (1≤n,m≤20001≤n,m≤2000).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤20001≤ai≤2000).

The third line contains mm integers b1,b2,…,bmb1,b2,…,bm (1≤bi≤20001≤bi≤2000).

The fourth line contains a single integer xx (1≤x≤2?1091≤x≤2?109).

Output
If it is possible to choose four integers x1,x2,y1,y2x1,x2,y1,y2 such that 1≤x1≤x2≤n1≤x1≤x2≤n, 1≤y1≤y2≤m1≤y1≤y2≤m, and ∑x2i=x1∑y2j=y1ci,j≤x∑i=x1x2∑j=y1y2ci,j≤x, output the largest value of (x2?x1+1)×(y2?y1+1)(x2?x1+1)×(y2?y1+1) among all such quadruplets, otherwise output 00.

Examples
Input
3 3
1 2 3
1 2 3
9
Output
4
Input
5 1
5 4 2 4 5
2
5
Output
1
Note
Matrix from the first sample and the chosen subrectangle (of blue color):

Matrix from the second sample and the chosen subrectangle (of blue color):

這個題，作為渣渣的我感覺挺難得。大體意思就是，兩個矩陣相乘，出來一個nm矩陣，在這個矩陣中找一個子矩陣使得這個子矩陣的和小于等于x但是矩陣的面積是最大的。
我們要知道，子矩陣的和=(a[1]+a[2]+a[3]+…+a[j])(b[1]+b[2]+…+b[i])這就是i*j矩陣的最小值。那我們應該做的就是找到前綴和最小的。在代碼里的mina[i]=j;代表長度為i的數組最小值是j。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=2e3+10; int n,m; ll a[maxx]; ll b[maxx]; ll mina[maxx]; ll minb[maxx]; ll x;int main() {while(scanf("%d%d",&n,&m)!=EOF){a[0] = b[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=a[i-1];//維護一個前綴和數組。}for(int i=1;i<=m;i++){scanf("%d",&b[i]);b[i]+=b[i-1];}memset(mina,inf,sizeof(mina));//先將那兩個數組賦予最大值memset(minb,inf,sizeof(minb));for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){mina[j-i+1]=min(mina[j-i+1],a[j]-a[i-1]);//動態規劃，代表長度為i的最小值。}}for(int i=1;i<=m;i++){for(int j=i;j<=m;j++){minb[j-i+1]=min(minb[j-i+1],b[j]-b[i-1]);}}scanf("%I64d",&x);int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(mina[i]*minb[j]<=x)//找到小于x的面積最大的。ans=max(ans,i*j);}}cout<<ans<<endl;} }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Maximum Subrectangle（矩阵，前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。