Эта задача решается как перебором с мемоизацией, так и динамическим программированием (что по сути довольно близкие методы).
С динамическим программированием будет чуть больше оптимизационных проблем, потому что будет много недостижимых состояний, которые на самом деле даже не надо обрабатывать, а вот перебор с мемоизацией проходит по времени с достаточным запасом.
Давайте заметим, что у каждой награды есть три возможных варианта — либо отдать ее одному герою, либо другому, либо оставить и потом раздвоить. Перебирать все $$$3^n$$$ состояний при этом нет смысла — если есть несколько способов прийти к одному и тому же «состоянию», нас не интересует их количество. А состояниями в этой задаче можно считать пары $$$(i, d)$$$, где $$$i$$$ — количество рассмотренных наград (рассматриваем их по порядку), а $$$d$$$ — абсолютная разница между тем, что получил Дэдпул, и тем, что получил Росомаха.
Из состояния $$$(i, d)$$$ мы можем получить
При чем всего возможных состояний не более $$$5 \cdot 10^7$$$, из которых на самом деле многие могут оказаться недостижимыми (но не обязательно). Сделаем рекурсивный перебор с описанными переходами между состояниями, при чем при получении ответа для какого-то состояния будем запоминать его. Посещая это же состояние в следующий раз, мы сможем сразу вернуть ответ, поэтому общее время работы будет не больше, чем количество состояний плюс количество переходов, чего достаточно, чтобы пройти в ограничения по времени.
Ответом для каждого состояния будет минимальная сумма наград, не отданных никому. Запомнить из рекурсивного перебора необходимо только те пути, которые приводят нас в состояние $$$(n, 0)$$$ — «все награды рассмотрены, и герои получили поровну». Ответом тогда будет $$$0.5 ( \mathtt{ans} + \sum a_i)$$$, где $$$\mathtt{ans}$$$ мы получили перебором.