height и шириной width. Покупатели готовы брать куски определённых размеров: offers[i] = [h, w, p] значит, что кусок высотой h и шириной w можно продать за p. Кусков одного размера можно продать сколько угодно; продавать каждый размер не обязательно.
Доску режут только сквозными распилами: один распил идёт поперёк всего куска, по горизонтали или по вертикали, и делит его на два меньших прямоугольника. Распилов можно сделать сколько угодно. Из-за направления волокон куски поворачивать нельзя: кусок h × w и кусок w × h — разные.
Верните наибольшую выручку, которую можно получить с доски height × width.height=2, width=3, offers=[[1, 1, 1], [2, 3, 10], [1, 3, 6]] → 12
Целиком доску можно продать за 10. Выгоднее разрезать её вдоль на две полосы 1 × 3 и продать каждую за 6: всего 12.
height=3, width=1, offers=[[2, 1, 5]] → 5
Отрезаем кусок 2 × 1 и продаём за 5. Оставшийся кусок 1 × 1 никто не покупает.
(h, w) в offers различныheight=2, width=3, offers=[[1, 1, 1], [2, 3, 10], [1, 3, 6]]
12
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 86 тестов на сервере, включая скрытые.