Олимпиадный тренинг

Задача . C. Максимальный подпрямоугольник

Задача

Темы: Бинарный поиск два указателя реализация *1600

Даны два массива $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$.

Примечание

Матрица из первого примера и выбранный подпрямоугольник (синего цвета):