Прямокутна ковзанка
Обмеження: 3 сек., 256 МіБ
Наступного дня Зеник з Марічкою вирішили покататися на ковзанах.
На курорті є прямокутна ковзанка розміру \(n \times m\). Кожна з \(n \times m\) ділянок ковзанки має свій рівень небезпеки \(d_{i j}\).
Ковзанка дуже велика, тому пара не хоче їздити по всій її площі, а тільки вибрати собі квадрат розміру \(k \times k\) зі сторонами паралельними до сторін ковзанки і кататися на ньому.
Рівень небезпеки квадрата — це максимальний рівень небезпеки серед усіх ділянок, що йому належать.
Марічка просить вас дізнатися, який мінімальний рівень небезпеки може мати квадрат \(k \times k\).
Вхідні дані
У першому рядку задано три цілих числа \(n\), \(m\) та \(k\) — розміри ковзанки та квадрата. У наступних \(n\) рядках задано по \(m\) цілих чисел \(d_{i j}\) — рівень небезпеки на відповідній ділянці ковзанки.
Вихідні дані
У єдиному рядку виведіть ціле число — мінімальний рівень небезпеки квадрата \(k \times k\).
Обмеження
\(1 \le n, m \le 1500\), \(1 \le k \le min\{n, m\}\),
\(1 \le d_{i j} \le 10^9\).
10 балів: \(n, m \le 100\);
10 балів: \(n, m \le 700\);
5 балів: без додаткових обмежень.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 3 2 2 5 4 4 1 3 3 2 1 | 3 |
Примітки
У прикладі можливі такі способи вибрати квадрат \(2 \times 2\):
\(\begin{matrix} 2 & 5 \\ 4 & 1 \end{matrix}\) з рівнем небезпеки 5,
\(\begin{matrix} 5 & 4 \\ 1 & 3 \end{matrix}\) з рівнем небезпеки 5,
\(\begin{matrix} 4 & 1 \\ 3 & 2 \end{matrix}\) з рівнем небезпеки 4,
\(\begin{matrix} 1 & 3 \\ 2 & 1 \end{matrix}\) з рівнем небезпеки 3.
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
Прямокутна ковзанка - Розбір
Спробуємо перевірити, чи існує квадрат розміру \(k \times k\) який має усі елементи менші за \(x\).
Утворимо новий масив \(a_{i j} = 0\), якщо \(d_{i j} \le x\) або \(a_{i j} = 1\) інакше. Тоді порахувавши префіксні суми, ми можемо знайти суму в одному квадраті \(k \times k\) за \(O(1)\).
Переберемо всі квадрати, і якщо хоча б в одному з них сума буде рівна \(0\) — це означатиме, що квадрат не містить елементів більших за \(x\).
Тепер ми можемо скористатися методом двійкового пошуку для того, аби знайти мінімальне значення \(x\), для якого існує квадрат \(k \times k\), що містить усі елементи не більші за \(x\). Це значення й буде відповіддю на задачу.
Код розв’язку Python (набирає 10 балів)
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|