| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 2048 MB | 21 | 11 | 10 | 58.824% |
В ОЦ <<Сириус>> любимым местом для сбора и неформального общения школьников служат различные лестницы. Но количество участников олимпиады по информатике значительно превосходит количество участников любой образовательной программы, и подходящей для них лестницы среди имеющихся не нашлось, поэтому служба оснащения решила построить новую лестницу, используя специальную заготовку.
Заготовка представляет собой таблицу из $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 --- числа, написанные в клетках таблицы.
Выведите одно число --- максимальное количество клеток, образующих лестницу.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 25 | $h, w \le 50$ |
| 2 | 25 | $h, w \le 400$ |
| 3 | 25 | $h \cdot w \le 200\,000$ |
| 4 | 25 |
6 4 0011 1101 0111 1110 0111 0100
8
Ниже изображен рисунок для первого примера. Лестница, состоящая из максимально возможного количества клеток таблицы, отмечена серым цветом.