Самый большой лист после разрезов

Средняя

Прямоугольный лист фанеры имеет высоту height и ширину width. Его режут насквозь: row_cuts[i] — расстояние от верхнего края до i-го горизонтального разреза, col_cuts[j] — расстояние от левого края до j-го вертикального. Разрезы перечислены в произвольном порядке. После всех разрезов лист распадается на прямоугольные куски. Верните площадь самого большого куска по модулю 10⁹ + 7.

Пример 1

height=6, width=5, row_cuts=[2, 5], col_cuts=[3] → 9

По высоте полосы 2, 3 и 1, по ширине — 3 и 2. Самый большой кусок 3 × 3 = 9.

Пример 2

height=4, width=7, row_cuts=[1], col_cuts=[6, 2] → 12

Разрезы могут идти не по порядку. Полосы по высоте 1 и 3, по ширине 2, 4 и 1: ответ 3 × 4 = 12.

Пример 3

height=2, width=2, row_cuts=[1], col_cuts=[1] → 1

Ограничения

2 ≤ height, width ≤ 10⁹
1 ≤ len(row_cuts) ≤ min(height - 1, 10⁵)
1 ≤ len(col_cuts) ≤ min(width - 1, 10⁵)
1 ≤ row_cuts[i] < height, 1 ≤ col_cuts[j] < width
Все значения в row_cuts различны, в col_cuts — тоже

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy Array Sorting

Вход

height=6, width=5, row_cuts=[2, 5], col_cuts=[3]

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 88 тестов на сервере, включая скрытые.