题解 | #线代高手#

看大家都用二维数组前缀和写这道题，那我就来介绍点不一样的方法，暴力枚举+一维前缀和，可以先用两层循环枚举数组的上下边界，再在循环内先预处理前缀和，再暴力枚举区间的左右边界，将x与区间和比较记录最大值；

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=55;

int S[N];
int a[N],b[N];
ll g[N][N];
ll max(ll a,ll b){return a>b?a:b;}
int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int j=1;j<=m;j++)cin>>b[j];
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            g[i][j]=a[i]*b[j];
            //cout<<g[i][j]<<" ";
        }
        //cout<<endl;
    }
    int x;
    cin>>x;
    //int len=0,wei=0;
    //ll sum=0,s=0,l,k;
    ll l,r,s=0;
    for(int i=1;i<=n;i++)//枚举上边界
        for(int j=n;j>=i;j--)//枚举下边界
        {
            memset(S,0,sizeof S);
            for(l=1;l<=m;l++)
            {
                int sums=0;
                for(int k=i;k<=j;k++)//预处理一维数组
                    sums+=g[k][l];
                    S[l]=S[l-1]+sums;
            }
            
            for(r=1;r<=m;r++)
                for(l=1;l<=r;l++)
                if(S[r]-S[l-1]<=x)//区间和与目标进行比较
                s=max(s,(j-i+1)*(r-l+1));
            
        }
    
    cout<<s<<endl;
    
    
}