Лучшие предметы с полок

Средняя

На складе n полок, на каждой по m предметов. Ценность предметов записана в таблице shelves: shelves[i][j] — ценность j-го предмета на полке i. Вы забираете со склада не более total предметов, причём с полки i можно взять не больше caps[i] предметов. Верните наибольшую суммарную ценность того, что можно унести.

Пример 1

shelves=[[4, 9, 2], [7, 1, 8]], caps=[1, 2], total=3 → 24

С первой полки можно взять один предмет — берём 9. Со второй — два: 8 и 7. Сумма 24.

Пример 2

shelves=[[5, 6], [3, 10]], caps=[2, 2], total=2 → 16

Всего можно взять два предмета: 10 со второй полки и 6 с первой. Сумма 16.

Пример 3

shelves=[[3, 3, 3]], caps=[0], total=0 → 0

Ограничения

n = len(shelves) = len(caps), m = len(shelves[i])
1 ≤ n, m ≤ 500
0 ≤ shelves[i][j] ≤ 10⁵
0 ≤ caps[i] ≤ m
0 ≤ total ≤ min(n · m, sum(caps))

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

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy Array Matrix Sorting Heap (Priority Queue)

Вход

shelves=[[4, 9, 2], [7, 1, 8]], caps=[1, 2], total=3

Ожидается

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