Редкие единицы в таблице

Сложная

Таблица имеет размер width × height, в каждой клетке стоит 0 или 1. Требуется, чтобы в любом квадратном фрагменте размером side × side было не больше limit единиц. Верните наибольшее число единиц, которое может быть во всей таблице.

Пример 1

width=4, height=3, side=2, limit=1 → 4

Ставим единицы туда, где обе координаты чётные: (0, 0), (0, 2), (2, 0), (2, 2). В любой квадрат 2 × 2 попадает не больше одной из них — всего 4 единицы.

Пример 2

width=3, height=3, side=3, limit=9 → 9

Ограничение разрешает заполнить единицами весь квадрат 3 × 3.

Пример 3

width=5, height=5, side=2, limit=0 → 0

Ограничения

1 ≤ width, height ≤ 100
1 ≤ side ≤ min(width, height)
0 ≤ limit ≤ side²

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

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy Math Sorting Heap (Priority Queue)

Вход

width=4, height=3, side=2, limit=1

Ожидается

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