ACMP 928
Перейти к навигации
Перейти к поиску
Ссылки на задачу
Похожие задачи
Комментарии
Будем перебирать пары (i1, j1) в порядке увеличения суммы (i1 + j1), а при равных суммах – в порядке возрастания i1. Для каждой такой суммы с ростом i1 оба конца отрезка допустимых (для данного i1) значений j2 будут уменьшаться.
Тогда для хранения этого отрезка можно использовать очередь с поддержкой операций добавления в конец, удаления из начала и поиска минимум за O(1). В этом случае нам потребуется лишь линейная дополнительная память для хранения очереди, длина которой в каждый момент времени не будет превосходить N.