ACMP 928

Ссылки на задачу

• ACMP #928 — Берёзовая аллея

Похожие задачи

• РОИ 2012-2013, региональный этап, D

Комментарии

Будем перебирать пары (i1, j1) в порядке увеличения суммы (i1 + j1), а при равных суммах – в порядке возрастания i1. Для каждой такой суммы с ростом i1 оба конца отрезка допустимых (для данного i1) значений j2 будут уменьшаться.

Тогда для хранения этого отрезка можно использовать очередь с поддержкой операций добавления в конец, удаления из начала и поиска минимум за O(1). В этом случае нам потребуется лишь линейная дополнительная память для хранения очереди, длина которой в каждый момент времени не будет превосходить N.