Задача №115396. Лестница для участников олимпиады
В ОЦ «Сириус» любимым местом для сбора и неформального общения школьников служат различные лестницы. Но количество участников олимпиады по информатике значительно превосходит количество участников любой образовательной программы, и подходящей для них лестницы среди имеющихся не нашлось, поэтому служба оснащения решила построить новую лестницу, используя специальную заготовку.
Заготовка представляет собой таблицу из \(h\) строк и \(w\) столбцов, пронумерованных сверху вниз и слева направо соответственно. В каждой клетке таблицы записано одно число — ноль или единица. Лестницу можно сделать только из тех клеток таблицы, в которых записана единица.
Полученная лестница образуется из множества клеток, в которых записана единица, находящихся в нескольких последовательных строках таблицы. Множество выбранных клеток в каждой строке лестницы должно быть непрерывным отрезком. При этом в каждой следующей строке, входящей в лестницу, должно быть выбрано не меньше клеток, чем в предыдущей, находящейся непосредственно над нею, строке, а самые левые выбранные клетки в каждой строке должны располагаться в одном и том же столбце.
Ниже приведен пример лестницы.
Найдите в заданной таблице максимальное количество клеток, образующих лестницу.
Первая строка входных данных содержит два целых числа \(h\) и \(w\) (\(1 \le h, w \le 2 \cdot 10^5\), \(h \cdot w \le 4 \cdot 10^6\)) — количество строк и столбцов таблицы соответственно.
Каждая из следующих \(h\) строк содержит по \(w\) символов, каждый из которых равен 0 или 1 — числа, написанные в клетках таблицы.
Выведите одно число — максимальное количество клеток, образующих лестницу.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
| \(h\), \(w\) | |||
| \(1\) | \(25\) | \(h, w \le 50\) | У |
| \(2\) | \(25\) | \(h, w \le 400\) | У, 1 |
| \(3\) | \(25\) | \(h \cdot w \le 200\,000\) | У, 1, 2 |
| \(4\) | \(25\) | — | У, 1–3 |
Ниже изображен рисунок для первого примера. Лестница, состоящая из максимально возможного количества клеток таблицы, отмечена серым цветом.
6 4 0011 1101 0111 1110 0111 0100
8