Задача 76257

Тема:    [ Многомерные массивы ]

Сложность: 3 Классы:

Условие

Приведённое решение предыдущей задачи требует порядка mn² действий. Придумать способ с числом действий порядка mn.

Подсказка

Придётся пожертвовать симметрией и выбрать одну из строк за основную. Двигаясь по основной строке, поддерживаем такое соотношение: во всех остальных строках отмечен максимальный элемент, не превосходящий текущего элемента основной строки.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	2
Название	Массивы
задача
Номер	1.2.26