Автор задачи: Фитисов Артем, разработчик: Мария Жогова
Заметим, что масса любого симбиота ограничена $$$10^9$$$. Поэтому масса $$$i$$$-го симбиота после того, как он пожертвовал собой, может дойти до симбиота с номером $$$j$$$, удаленного от $$$i$$$-го не дальше, чем на $$$R = \log_2 10^9 \leqslant 30$$$. При этом масса $$$i$$$-го симбиота может как-то увеличить массу $$$j$$$-го, и эта обновленная масса может дойти до симбиота $$$k$$$ на расстоянии также не больше $$$R$$$ от $$$j$$$. Таким образом на вес $$$k$$$-го симбиота могут повлиять симбиоты, удаленные от него не дальше, чем на $$$2 \cdot R$$$.
Так как у каждого симбиота есть сосед слева и справа, то масса $$$k$$$-го симбиота может меняться в течении первых $$$4 \cdot R$$$ лет. Далее все ближайшие симбиоты погибнут, а масса остальных симбиотов уже не будет доходить до $$$k$$$-го ни в каком виде.
Давайте считать, что $$$4 \cdot R < n - 1$$$. Для $$$1 \leqslant t \leqslant 4 \cdot R$$$ ответ можно предпочитать, а для больших $$$t$$$ он очевидно будет равен ответу при $$$t = 4 \cdot R$$$.
Давайте для каждого $$$0 \leqslant i \leqslant n - 1$$$ пронаблюдаем то, как его масса будет влиять на $$$2 \cdot R$$$ соседей слева и справа. Пусть $$$r[i][j]$$$ — масса $$$i$$$-го симбиота при условии, что $$$j$$$ его соседей справа поделились своей массой, а $$$l[i][j]$$$ — масса $$$i$$$-го симбиота при условии, что $$$j$$$ его соседей слева поделились своей массой. Ясно, что $$$l[(i + j) \bmod n][j] = \left\lfloor \cfrac{l[(i + j - 1) \bmod n][j - 1]}{2} \right\rfloor + a[(i + j) \bmod n]$$$, а $$$r[(i + j) \bmod n][j] = \left\lfloor \cfrac{r[(i + j + 1) \bmod n][j - 1]}{2} \right\rfloor + a[(i + j) \bmod n]$$$ для всех $$$1 \leqslant j \leqslant 2\cdot R$$$.
Тогда максимальная достижимая $$$i$$$-м симбиотом за $$$t$$$ лет масса $$$m[i][t] = \max\limits_{0 \leq j \leq t} l[i][j] + r[i][t - j] - a[i]$$$. Ответ на задачу равен $$$ans[t] = \max\limits_{i=0}^{n - 1} m[i][t]$$$. Это верно для любых $$$0 \leqslant t \leqslant \min(n - 1, 4 R)$$$. Для $$$t > 4 \cdot R$$$ при условии $$$4 \cdot R < n - 1$$$ ответ будет равен $$$ans[4R]$$$.
Если $$$n - 1 \leqslant 4 \cdot R$$$, то $$$ans[t]$$$ для $$$t < n - 1$$$ считается так же, как в общем случае. Рассмотрим отдельно случай, когда $$$t = n - 1$$$. В этом случае первый симбиот, который пожертвовал собой поделится своим весом с правым и левым соседом. Поэтому $$$m[i][n - 1] = \max\limits_{j=0}^n l[i][j] + r[i][n - j] - a[i]$$$. Следовательно, $$$ans[n - 1] = \max\limits_{i=0}^{n-1} m[i][n-1]$$$. В остальных случаях ($$$t > n - 1$$$) $$$ans[t] = ans[n - 1]$$$.
Общий план решения задачи.
Общее время работы — $$$\mathcal{O}(R^2 \cdot n + m) = \mathcal{O}(n + m)$$$.