Skip to content

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;
}