Активная подготовка к битве

Автор задачи и разработчик: Владимир Рябчун

Отсортируем людей по возрастанию $$$p_i$$$ и перенумеруем (теперь люди с меньшими номерами — это люди с меньшими значениями $$$p_i$$$).

Может оказаться так, что первых $$$t > 0$$$ людей Карнаж может съесть, не привлекая внимания полиции. В таком случае он может это сделать, выбирая людей в порядке возрастания $$$p_i$$$: действительно, если он, не привлекая внимания полиции, съедает человека с $$$p_i > p_j$$$ раньше, то $$$P \geqslant p_i$$$ и $$$P + p_i \geqslant p_j$$$, но из первого же неравенства следует, что $$$P \geqslant p_j$$$ и $$$P + p_j \geqslant p_i$$$, а значит их можно было поменять местами. Пройдем по началу списка людей циклом while, добавляя силу рассмотренных людей к $$$P$$$, пока она не превосходит текущего значения $$$P$$$. В тот момент, когда цикл остановится, у всех оставшихся людей сила будет больше текущей силы Карнажа.

Заметим, что, съев некоторого человека, Карнаж может сразу же после этого съесть и всех людей с меньшей силой (так как его собственная сила теперь превзошла силу съеденного человека). Поэтому, если Карнаж может, добившись настороженности полиции $$$C$$$, съесть $$$i$$$-го человека, он может при той же настороженности получить силу $$$P_{\text{нач}} + \sum\limits_{j=1}^i p_j$$$. Если посмотреть на это с другой стороны, то, чтобы съесть очередного $$$i$$$-го человека, если $$$p_i > P_\text{текущей}$$$, необходимо и достаточно $$$\min\limits_{j=i}^n c_j$$$ внимания полиции на то, чтобы съесть любого человека $$$j \geqslant i$$$, а затем всех предыдущих.

Таким образом, все решение заключается в следующем: будем обрабатывать людей по очереди, каждый раз поддерживая $$$(P, C)$$$ — текущие оптимальные силу Карнажа и настороженность полиции, достигаемые при съедении всех обработанных людей. Если $$$p_i$$$ нового человека не превосходит $$$P_{\text{текущей}}$$$, то новая пара получается увеличением $$$P$$$ на $$$p_i$$$ без изменения $$$C$$$. Затем, как только встречается человек номер $$$i$$$, которого невозможно съесть незаметно, Карнажу следует выбрать $$$j$$$, на котором достигается $$$\min\limits_{j=i}^n c_j$$$, после чего запомнить следующую пару $$$\left(P = \sum\limits_{k=1}^j c_k, C = c_j\right)$$$, съесть всех людей до $$$j$$$ «бесплатно» и перейти к рассмотрению следующих.

Можно заметить, что первый элемент в таких парах всегда увеличивается, а второй — не уменьшается. Таким образом, для ответа на каждый вопрос можно применить двоичный поиск по запомненным парам, либо отсортировать запросы и пройтись двумя указателями.