Автор задачи: Владимир Рябчун, разработчики: Даниил Орешников и Владимир Рябчун
Для решения первой подзадачи можно было не делать никаких наблюдений относительно того, в каком порядке надо отключать элементы — достаточно было перебрать все возможные перестановки и попробовать отключать их в таком порядке, пока к следующему элементу есть доступ. С помощью std::next_permutation решение можно было написать совсем коротко.
Вторая подзадача, аналогично, решалась полным перебором, однако здесь стоило применить динамическое программирования по подмножествам, $$$\mathtt{dp}[mask]$$$ — минимальная стабильность, начиная с которой можно отключить в некотором порядке все элементы, закодированные маской $$$mask$$$. Пересчет динамики осуществлялся перебором первого элемента для отключения. Время работы решения — $$$\mathcal{O}(2^n \cdot n)$$$.
Для решения следующих подгрупп следовало сделать некоторые наблюдения относительно порядка отключения элементов.
Для начала заметим, что если какой-то конечной стабильности можно добиться, то ее также можно добиться, отключая сначала только элементы с положительными $$$b_i$$$, а затем — только с отрицательными. Действительно, если мы сначала можем отключить элемент с отрицательным $$$b_i$$$, а затем с положительным $$$b_j$$$, то $$$s \geqslant a_i$$$ и $$$s - |b_i| \geqslant a_j$$$. Из этого следует, что $$$s + b_j \geqslant a_i$$$ и $$$s \geqslant a_j$$$, а значит их можно с тем же результатом отключить в противоположном порядке.
Аналогичное наблюдение можно сделать и касательно порядка, в котором можно отключать «положительные» элементы — если это можно сделать в каком-то порядке, то можно сделать и порядке возрастания $$$a_i$$$. Доказательство еще проще — при их отключении стабильность только растет, значит если элемент с большим $$$a_i$$$ можно было отключить раньше, его можно будет отключить и позже.
Это позволяет решить третью подзадачу аналогично задаче о рюкзаке: отсортируем все «положительные» элементы по возрастанию $$$a_i$$$ и посчитаем $$$\mathtt{dp}[t][x]$$$ — «можно ли получить стабильность $$$x$$$, отключая только элементы из числа первых $$$t$$$». Пересчет динамики будет следующий: $$$$$$\mathtt{dp}[t][x] = \begin{cases} \mathtt{dp}[t - 1][x] & \text{если } x - b_t < a_t \\ \mathtt{dp}[t - 1][x] \text{ or } \mathtt{dp}[t - 1][x - b_t] & \text{иначе.} \end{cases}$$$$$$
После чего достаточно найти минимальное такое $$$S$$$, которое можно получить с помощью «положительных» элементов, и при котором можно отключить единственный «отрицательный». Если итоговое значение после его отключения лучше изначальной стабильности, оно и будет ответом. Время работы решения — $$$\mathcal{O}\left(n \cdot \left(s + \sum |b_i|\right)\right)$$$.
Если все отрицательные $$$b_i$$$ равны между собой, то можно сделать аналогичное наблюдение о том, что их можно применять в порядке уменьшения $$$a_i$$$ и получить все то же множество возможных результатов. Доказательство полностью аналогично рассмотренным выше. В таком случае достаточно объединить идеи второй и третьей подзадач: посчитаем
Пересчет такой динамики аналогичен, $$$\mathtt{dp}^-[t][x]$$$ равно либо $$$\mathtt{dp}^-[t - 1][x]$$$, либо $$$\mathtt{dp}^-[t - 1][x + b_t]$$$, если $$$x \geqslant a_t$$$. Достаточно выбрать минимальное возможное значение. Время работы решения такое же, как и в предыдущей подгруппе.
В последних двух подгруппах отличие в том, что не всегда можно прийти к оптимальному ответу, отключая «отрицательные» элементы в порядке убываения $$$a_i$$$. В предпоследней подгруппе можно было исправить это, взяв динамику, описанную во второй подгруппе вместо пятой. Для полного решения же можно доказать, что достаточно отключать «отрицательные» элементы в порядке убывания $$$a_i + b_i$$$.
Действительно, пусть $$$a_i + b_i < a_j + b_j$$$ и верны неравенства $$$$$$\begin{cases} s \geqslant a_i \\ s + b_i \geqslant a_j\text{.} \end{cases}$$$$$$
Из второго неравенства следует, что $$$s \geqslant a_j - b_i$$$, что больше $$$a_i - b_j$$$ по нашему предположению. А из этого как раз следует, что $$$$$$\begin{cases} s \geqslant a_j & \text{так как } b_i < 0 \\ s + b_j \geqslant a_i\text{,} \end{cases}$$$$$$ а значит соответствующие элементы можно отключить в обратном порядке. Дальше достаточно применить решение из пятой подгруппы, только отсортировать «отрицательные» элементы в порядке возрастания $$$a_i + b_i$$$. Время работы решения то же самое.