14197: 【原4197】Maximum Subrectangle

题目

题目描述

author: cyx666 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4197 ## Description

现有一个\(n\)维列向量\(a\)和一个\(m\)维行向量\(b\)，并定义矩阵\(C=a×b\)。 求\(C\)的最大子矩阵，即子矩阵内元素个数最多，满足子矩阵和小于等于\(x\)。 若不存在满足条件的子矩阵，则输出\(0\)。

Input Format

第一行包含两个正整数\(n\)和\(m\)； 第二行包含一个\(n\)个正整数，用空格隔开，表示向量\(a\)； 第三行包含一个\(m\)个正整数，用空格隔开，表示向量\(b\)； 第四行包含一个正整数\(x\)。

Output Format

一个整数，表示最大子矩阵内元素个数。

Sample Input1

3 3
1 2 3
1 2 3
9

Sample Output1

4

Sample Input2

5 1
5 4 2 4 5
2
5

Sample Output2

1

Data Range

对于30%的数据，\(1 \le n，m，a_i，b_i \le 100\)

对于100%的数据，\(1 \le n，m，a_i，b_i \le 2000\)，\(1 \le x \le 2*10^9\)

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, a[2005], b[2005], x;
int suma[2005], sumb[2005];
int minia[2005], minib[2005];
void init(){
    n = read(), m = read();
    suma[0] = sumb[0] = 0;
    REP(i, 1, n)
        a[i] = read(), suma[i] = suma[i - 1] + a[i];
    REP(i, 1, m)
        b[i] = read(), sumb[i] = sumb[i - 1] + b[i];
    x = read();
    REP(i, 1, n){
        minia[i] = 0x3f3f3f3f;
        REP(j, 1, n - i + 1)
            minia[i] = min(minia[i], suma[j + i - 1] - suma[j - 1]);
    }
    REP(i, 1, m){
        minib[i] = 0x3f3f3f3f;
        REP(j, 1, m - i + 1)
            minib[i] = min(minib[i], sumb[j + i - 1] - sumb[j - 1]);
    }
}
void solve(){
    int curb = m, ans = 0;
    REP(i, 1, n){
        while (curb > 0 && 1ll * minia[i] * minib[curb] > 1ll * x)
            --curb;
        ans = max(ans, i * curb);
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}