[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle

这场有点惨的过分了，怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧

这个题卡了是最最难受的，因为从矩阵的角度考虑不管怎么样都搞不出来一个O(n3)的算法，无论如何都不可能，然 而 ，然 而！这题目根本就不用考虑矩阵。。。因为每一行每一列都是成比例的啊。。。光给个矩阵怎么可能n²算出来答案？很明显是跟题目数据自身的性质有关系的，然后自己就傻脸看了俩小时不知道怎么操作，呵呵，出发点就不对怎么可能算出来。。。

因为每一行都是成比例的，比例是bi，所以要求一个最大的不超过x的子矩阵，只需要枚举上下边然后给预处理出来的sb数组乘个上下边之差就可以了，小于x的操作可以用sb[x/(pa[j]-pa[i-1])]来操作。。。。。。所有的处理都极其暴力，但是因为所有的处理都是在a或者b的一维序列上进行的，所以暴力也是n²，如果脑子里只有那个矩阵的话怎么都不可能n²，因为他是个二维的。。
写错的地方的话是x可能会比pb[m]大，这时候只需要取到这个最大值就可以了。

#include
//#include
//#include

using namespace std;

typedef long long LL;
const int maxn=2e3+5;
const int mod=1e9+7;

LL sb[maxn*maxn];
LL a[maxn],b[maxn],pa[maxn],pb[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    LL x;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        pa[i]=pa[i-1]+a[i];
    }

    for (int i=1;i<=m;i++)
    {
        cin>>b[i];
        pb[i]=pb[i-1]+b[i];
    }
    cin>>x;
    for (int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
        sb[pb[j]-pb[i-1]]=max(sb[pb[j]-pb[i-1]],j-i+1LL);
    for(int i=1;i<=pb[m];i++)
        sb[i]=max(sb[i],sb[i-1]);
    LL ans=0;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
        {
            LL cur=x/(pa[j]-pa[i-1]);
            if(cur>=pb[m])
                ans=max(ans,(j-i+1)*sb[pb[m]]);
            else
                ans=max(ans,(j-i+1)*sb[cur]);
        }

    cout<