Автор задачи и разработчик: Даниил Голов
Частичные решения по задаче включают полный перебор в первой подгруппе или расположение свидетелей в произвольном порядке во второй и третьей подгруппах. Ниже приведем полное решение задачи.
На самом деле достаточно посмотреть на момент времени, в который скучность дела максимальна. Все критические точки, которые будут пройдены, будут пройдены в этот момент, если не раньше. Поскольку скучность больше не увеличится, новые критические точки пройдены не будут. Таким образом, достаточно минимизировать максимальную из скучностей дела.
Скучность дела является префиксной суммой скучностей допрашиваемых. Заметим, что префиксная сумма $$$a_1 + \ldots + a_n$$$ точно встретится в конце, поэтому получить максимум меньше ее не получится. А добиться того, чтобы она была максимальной, можно, расположив сначала всех подозреваемых с отрицательной скучностью, а после — всех с положительной.
Таким образом, самым простым решением было отсортировать всех подозреваемых по скучности и вывести в таком порядке, либо же за два прохода по массиву сначала вывести всех с отрицательной скучностью, а за второй проход — с положительной. Такое решение будет работать за время $$$\mathcal{O}(n + m)$$$. Количество пройденных критических точек также можно искать линейным проходом по массиву $$$b_i$$$.