← 返回题目列表

Codeforces · 1060/C

C. 最大子矩形

中文机器翻译题面 查看原题

给定两个正整数数组 $$$a$$$ 和 $$$b$$$,长度分别为 $$$n$$$ 和 $$$m$$$。

令 $$$c$$$ 为 $$$n \times m$$$ 矩阵,其中 $$$c_{i,j} = a_i \cdot b_j$$$。

你需要找到矩阵$$$c$$$的一个子矩形,使其元素之和至多为$$$x$$$,并且其面积(元素总数)尽可能最大。

形式上,您需要找到最大的数字 $$$s$$$,以便可以选择整数 $$$x_1, x_2, y_1, y_2$$$ 并满足 $$$1 \leq x_1 \leq x_2 \leq n$$$, $$$1 \leq y_1 \leq y_2 \leq m$$$, $$$(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s$$$,并且 $$$$$$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.$$$$$$

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2000$$$)。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 2000$$$)。

第四行包含一个整数 $$$x$$$ ($$$1 \leq x \leq 2 \cdot 10^{9}$$$)。

输出

如果可以选择四个整数 $$$x_1, x_2, y_1, y_2$$$ 使得 $$$1 \leq x_1 \leq x_2 \leq n$$$, $$$1 \leq y_1 \leq y_2 \leq m$$$,并且$$$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$$$,输出所有四元组中$$$(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$$$的最大值,否则输出$$$0$$$。

示例

输入 #1

3 3
1 2 3
1 2 3
9

输出 #1

4

输入 #2

5 1
5 4 2 4 5
2
5

输出 #2

1

注意

第一个样本和所选子矩形(蓝色)的矩阵:

第二个样本和所选子矩形(蓝色)的矩阵: