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

Сложность выходит O(SlogS), где S максимальная площадь карты, т.е.  ≤ 10⁵.

У нас очень простое решение, за O(WH·min(W, H)) = O((WH)^1.5). Пойдём по строкам, будем поддерживать для каждого столбца каждого куска текущую высоту столбца из нулей. Как найти максимальную площадь для прямоугольника, оканчивающегося на данной высоте? Переберём высоту прямоугольника (кандидатов min(W, H), т.к. имеет смысл перебирать только высоты, являющиеся текущими высотами какого-то из столбцов), для каждой высоты итерируемся по всем кускам и считаем ответ (крайние куски добавляют немного геморроя).

Не понятно, за что минусуют: вроде решение норм.

Нельзя сказать что очень честное, но работает без отсечения по времени, оценивать асимптотику не умеем, а еще есть подозрение, что просто макс.тест настолько специфический, что его заранее построить невозможно. А решение такое:

Посчитаем хеши всех префиксов и всех перевернутых суффиксов запросов, для каждой полученной пары <хеш, длина подстроки> сделаем set того, чем она является (префикс или суффикс и в каком запросе). Далее динамика по дереву — для каждой вершины храним set pair<хеш,длина> всевозможных путей из этой вершины, мержим два сета за O(размер меньшего set'а) (для этого надо хранить пару не в явном виде а как линейную функцию от нее и при добавлении вершины пересчитывать коэффициенты), при этом для каждого хэша из меньшего множества проверяем частью какой строки он может являться (при помощи тех самых заранее построенных сетов) и обновляем ответы, как только мы нашли одно вхождение строки, сразу удаляем из сетов, при этом если хеш уже не может быть частью ни одной строки, то про него надо забыть, т.к. потом и подавно мы с его помощью ничего не найдем.

Предполагалось такое решение:

(a) Предположим, что у нас в строках запросов соседнии символы не равны: s_i ≠ s_i + 1, в конце, будет пояснено, как избежать этого ограничения.

1) Допустим у нас всего одна строка s в запросе. То можно решать разными способами, но один из них может быть таким: Предположим, что строка проходит через вершину u, проверим, что это так: например, собрав хэши по путям из вершины u, наша строка проходящая через u будет состоять из двух путей: пути из u — являющимся перевернутым префиксом строки s и пути из u являющимся суффиксом строки s. Предположение (a) гарантирует, что они не попадут в одно поддерево. В таком случае можно для каждого пути из этого дерева искать соответствующий перевернутый префикс (можно хэшами) и смотреть, есть ли в этом дереве хэш соответствующего суффикса. Если это не так (т.е. строка не проходит, через u), то выкинем вершину u, дерево распадется на несколько меньших деревьев и для каждого нового дерева, запустим эту процедуру повторно. Если в качестве u каждый раз выбирать "центр" графа — вершину у которой максимальное из поддеревьев  ≤  размер поддерева / 2, то глубина такой операции будет O(log(n)), а суммарное количество вершин в деревьях на всех этапах (и путей для которых считаются хэши) -- O(nlog(n)). Но если на входе много запросов, то решить так не сможем.

2) Промоделируем процесс из п.1, т.е. каждый раз будем искать центр графа, выкидывать его, и повторять для каждого из новых деревьев. И сохраним все эти деревья T_i. Для каждого такого дерева посчитаем хэши путей и составим из них множество S_i. Таких множеств O(n) и суммарное количество элементов в них, как было написано в п.1, O(nlog(n)). Теперь для каждой строки, рассмотрим каждое из ее разбиений на пару префикс + суффикс, тогда нам нужно уметь быстро определять, есть ли такое множество S_i в котором есть и перевернутый префикс и суффикс, но проблема в том, что множества S_i между собой пересекаются. Для этого можно применить следующий прием: составим граф из вершин -- все различные префиксы и суффиксы строк их O(m), где m будет суммарной длиной всех строк-запросов, а ребро между двумя вершинами u и v, если есть строка u + v. Будем теперь проходиться по каждому из множеств S_i и красить все вершины, которые входят в S_i в цвет i, тогда если мы будем знать набор ребер, которые в какой момент времени были покрашены в один цвет (т.е. это будет означать, что и u и v лежат в одном дереве), то сможем ответить, какие строки входят в дерево, ну и если красить с дополнительной информацией (т.е. еще сохранять путь в исходном дереве, который соответствует данной вершине), то можно восстановить и само вхождение.

3) Как сделать п.2 эффективно: можно применить стандартный прием, который вроде бы называется корневой эвристикой: разобьем все вершины в графе префиксов и суффиксов на два множества: те у кого инцидентных ребер больше -- назовем их большими, и у тех у кого не больше -- назовем их маленькими. Теперь когда рассматриваем какое-то дерево S_i -- просто покрасим все вершины соответствующие какому-то хэшу из S_i в цвет i. Теперь пройдемся по тем вершинам которые красили в цвет i, пусть мы сейчас рассматриваем некоторую вершину u этого графа, то если u является маленькой, то можно влоб пройтись по всем инцидентным ребрам этой вершины и проверить является ли ребро "одноцветным", если является, то как-нибудь его пометить. Это позволит рассмотреть ребра с двумя маленькими вершинами и одной маленькой и одной большой вершинами. Если вершина u большая, то пройдемся по инцидентным ей большим вершинам (их не больше ) и проверим — являются ли они одного цвета, если являются, то пометим эти ребра. Это рассмотрит случай ребра с двумя большими вершинами.
После прохода по всем множествам S_i у нас есть список помеченных ребер, которые были покрашены в какой-то момент в один цвет (т.е. есть какое-то S_i которому принадлежат обе вершины).
Понятно, что на каждую из вершин потратится операций. А операций покраски O(nlog(n)), т.е. суммарное время . Когда есть список таких помеченных ребер, то можно просто для каждой строки из запросов проверять, помечена ли какая-нибудь из пар префикс + суффикс.

Дополнения:

* Как можно избавиться от предположения (a): Для этого вершины можно красить не в цвет i, когда мы рассматриваем множество S_i, а в (i, v), где v будет корнем поддерева T_i в котором лежит соответствующий путь и в каждой вершины сохранять по две различных расскраси. Тогда нужно будет проверять, не то что цвета равны, а то что найдется из цветов, такие пары, что первые элементы цветов равны, а вторые не равны (т.е. лежат в одном дереве, но в разных поддеревьях).

** Можно построить решение без хэшей с той же ассимптотикой, для этого изначально необходимо построить суффиксное дерево на строках s_i, rev(s_i), где rev(a) — это перевернутая строка. Строить его надо — разделив все соотвествующими разделителями, т.е. для строки вида s₁#₁rev(s₁)#₂s₂#₃rev(s₂)... s_n#_2n - 1rev(s_n)#_2n. Тогда вместо хэша можно рассматривать состояние в суффиксном дереве. Для перевернутого префикса и не перевернутого суффикса — эти состояния получить легко. Теперь необходимо так же занумеровать пути из деревьев T_i, для этого можно просто обходить эти деревья и параллельно идти по суффиксному дереву и сохранять в виде хэша -- состояние в суффиксном дереве. Нужно учитывать, что если по какому-то символу из u нет перехода из текущего состояния, то переходить в дереве T_i из u по этому символу нельзя -- таких префиксов и суффиксов все равно нет.

*** в п.2. можно не сохранять все деревья T_i, а использовать линейное количество памяти: проверить по п.3. текущее дерево, удалить оттуда корень и запустить соответствующую процедуру рекурсивно.

Если интересуют какие-то отдельные детали — буду рад пояснить. К сожалению, тесты не смогли покрыть все эвристики по этой задаче, но надеюсь она все равно хоть кому-нибудь понравилась =).

Без жадности?! Мы честно пытались валить его с жадностью, когда cmd придумал решение за O(N), но так ничего и не вышло...

Нормальное решение такое. Построим двудольный граф с весами, взятыми из матрицы. Задача свелась к такой: надо для каких-то вершин выбрать рёбра, так что для каждой вершины выбрано <=одно ребро, для каждого ребра <=1 вершина, и сумма весов рёбер максимальна. Несложно заметить, что допустимые подмножества — это наборы компонент связности, где каждая компонента — дерево + (возможно) одно ребро. Утверждается, что такие штуки можно искать жадно, аналогично алгоритму Краскала.

Как можно строить граф: слева у нас будет N * M вершин (вершины соответствует клеткам), справа будет N + M вершин (для строк и столбцов). Клетка соединяется со строкой и со столбцом в которой находится. Вес в данном случаи имееют только вершины в левой доли (клетки). Если не нужно восстанавливать паросочетание, а только найти его оптимальный вес, то можно это сделать за O(N) используя DSU, учитывая что для каждой вершины левой доли есть только 2 ребра в правую.

Если втупую (за квадрат) — для каждой вершины dfs'ом считаем вероятность того, что она плохая, потом по линейности матожидания суммируем эти вероятности. Теперь оптимизация — когда вызываемся dfs'ом из вершины x, придя в неё из вершины y, запоминаем ответ для пары (x, y) (т.е. грубо говоря, для ориентированного ребра). Это уже работает за линию.

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

G — запихиваем листья (из которых ничего не выходит) и корни (в которые ничего не входит) в массив, сортируем по высоте, попарно соединяем

Как я понимаю, под div2 only обычно приносят скорее баянистые задачи, чем реально простые. Не знаю, что закодили ребята, которые эту задачу решили первыми, а у меня была стандартная, но довольно громоздкая (ещё и потребовавшая оптимизации) динамика за O(3^N * 2^N * logX): для каждой позиции (от больших к меньшим) в двоичной записи мы перебираем, в каких числах там будет 0, а в каких 1; для тех вариантов, где все ограничения [Li, Ri] удевлетворены, запоминаем какие из чисел уже можно продолжать по-любому (то есть что мы не припишем, они уже не выйдут за свой диапазон), а какие всё ещё могут оказаться меньше своего L или больше R, и вот тройка {номер бита, битмаска — какие из чисел ещё могут уйти ниже L, битмаска — какие из чисел ещё могут уйти выше R} будет наше состояние.

Можно заметить, что четность количества инверсий (т.е. таких пар (i, j), что i < j и A_i > A_j) после каждого хода меняется. То есть достаточно посмотреть на четность инверсии в начальной последовательности и сравнить её с конечной... если равно тогда второй выигрывает, иначе выигрывает первый.