Автор задачи и разработчик: Даниил Орешников
Будем характеризовать состояние носителей $$$i$$$-й пары парой $$$(x, y)$$$, где $$$x$$$ — суммарная опасность симбиотов, расположенных в $$$2i-1$$$-м носителе, а $$$y$$$ — в $$$2i$$$-м носителе.
Рассмотрим возможные расположения двух симбиотов из $$$i$$$-й пары в носителях $$$i$$$-й пары, и какие состояния носителей им соответствуют. Если оба симбиота расположились в предыдущей паре, состояние будет равно $$$(0, 0)$$$ (случай 1). Если один из симбиотов расположился в предыдущей паре, то состояние может быть равно $$$(0, a_{2i-1})$$$, $$$(0, a_{2i})$$$ или двум симметричным им (случаи 2 и 3). Аналогично, случай 4 соответствует состоянию $$$(a_{2i-1}, a_{2i})$$$ и симметричному ему (которых поровну). И случай 5 возможен, если $$$a_{2i-1} + a_{2i} \leqslant B$$$, и соответствует состояниям $$$(a_{2i-1} + a_{2i}, 0)$$$ и $$$(0, a_{2i-1} + a_{2i})$$$ (количество способов достичь которых, аналогично, одинаково в силу симметрии).
Заведем $$$\mathtt{dp}[i][s]$$$, где $$$0 \leqslant i \leqslant n$$$ и $$$1 \leqslant s \leqslant 5$$$ — количество способов расположить первые $$$i$$$ пар симбиотов в первых $$$i$$$ парах носителей, чтобы последняя пара носителей находилась в состоянии, отвечающему случаю $$$s$$$. Пересчет такой динамики заключается в аккуратном разборе случаев расположения симбиотов $$$i$$$-й пары в зависимости от состояния $$$i-1$$$-й пары носителей и ожидаемого состояния $$$i$$$-й пары носителей. Можно немного сократить ручной перебор, закодировав случаи состояний и разобрав общий случай перехода.
Ответ в такой динамике будет располагаться в $$$\sum\limits_s \mathtt{dp}[n][s]$$$. При ручном рассмотрении случаев подсчет $$$\mathtt{dp}[i][s]$$$ требует перебора пяти предыдущих состояний $$$\mathtt{dp}[i-1][s_{old}]$$$, и дает общую асимптотику времени работы $$$\mathcal{O}(25n) = \mathcal{O}(n)$$$.