{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eПосле того, как задачи нахождения в числовой матрице наибольших квадратов и прямоугольников из нулей стали стандартными, появилась новая задача, обобщающая все предыдущие. Дана матрица из нулей и единиц. Необходимо найти наилучшую \"расческу\"\u0027, которую можно построить на нулевых ячейках этой матрицы (наилучшей называется расческа, которая занимает наибольшее количество ячеек данной матрицы). Звеном расчески называется непустая прямоугольная область из нулей в матрице, то есть некоторая подматрица ненулевой площади, состоящая только из нулей. \u003cstrong\u003ek\u003c/strong\u003e-расческой называется фигура, получаемая соединением по вертикали \u003cstrong\u003ek\u003c/strong\u003e (\u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003ek\u003c/strong\u003e ≤ \u003cstrong\u003em\u003c/strong\u003e) звеньев. У всех звеньев должна совпадать \u003cstrong\u003ex\u003c/strong\u003e-координата левой стороны, соседние звенья должны иметь разную ширину, а все звенья вместе должны образовывать цельную фигуру, то есть должны быть связаны. При этом \u003cstrong\u003e0\u003c/strong\u003e-расческа существует всегда и имеет размер \u003cstrong\u003e0\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eФигура на рисунке \u003cstrong\u003e1\u003c/strong\u003e является правильной \u003cstrong\u003e7\u003c/strong\u003e-расческой. Хотя фигура занимает \u003cstrong\u003e8\u003c/strong\u003e строк, она является \u003cstrong\u003e7\u003c/strong\u003e-расческой, так как на второй и третьей снизу строках находится одно и то же звено (соседние звенья обязательно должны быть разной ширины, но звено может быть высотой более \u003cstrong\u003e1\u003c/strong\u003e строки). Фигура на рисунке \u003cstrong\u003e2\u003c/strong\u003e не является правильной расческой, так как левая \u003cstrong\u003ex\u003c/strong\u003e-координата звеньев не совпадает. Фигура на рисунке \u003cstrong\u003e3\u003c/strong\u003e также не является правильной расческой, так как не является связной фигурой. Можно заметить, что наилучший прямоугольник это то же самое что наилучшая \u003cstrong\u003e1\u003c/strong\u003e-расческа (расческа высоты \u003cstrong\u003e1\u003c/strong\u003e звено). Очевидно, что для каждой длины \u003cstrong\u003ek\u003c/strong\u003e в матрице можно либо найти наилучшую расческу, либо заявить, что ее нет (то есть наилучшая расческа имеет размер \u003cstrong\u003e0\u003c/strong\u003e). Например, на рисунке \u003cstrong\u003e4\u003c/strong\u003e обозначена лучшая \u003cstrong\u003e3\u003c/strong\u003e-расческа (знаком \u003cstrong\u003eX\u003c/strong\u003e обозначены ненулевые элементы в матрице).\u003c/p\u003e\n\n\u003cp\u003e\u003cimg src\u003d\"https://static.e-olymp.com/content/12/124f526f0998393c49c53062f8daa13014b001b4.jpg\" /\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cem\u003e\u003cstrong\u003eРис. 4\u003c/strong\u003e\u003c/em\u003e\u003c/p\u003e\n\n\u003cp\u003eВаша задача - найти в данной матрице наилучшую расческу среди всех \u003cstrong\u003ek\u003c/strong\u003e-расчесок матрицы (для всех \u003cstrong\u003ek\u003c/strong\u003e от \u003cstrong\u003e0\u003c/strong\u003e до \u003cstrong\u003em\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВ первой строке входного файла даны два целых числа - высота (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003em\u003c/strong\u003e ≤ \u003cstrong\u003e2000\u003c/strong\u003e) и ширина (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003en\u003c/strong\u003e ≤ \u003cstrong\u003e2000\u003c/strong\u003e) матрицы соответственно. Далее, в \u003cstrong\u003em\u003c/strong\u003e строках дано по \u003cstrong\u003en\u003c/strong\u003e чисел через пробел - исходная матрица.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВ выходной файл необходимо вывести размер наибольшей расчески среди всех \u003cstrong\u003ek\u003c/strong\u003e-расчесок, которую можно построить на нулевых ячейках входной матрицы.\u003c/p\u003e\n\n"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\n0 0 1 0\n0 1 0 0\n0 0 0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}