Долгое путешествие

Автор задачи: Фитисов Артем, разработчик: Мария Жогова

Заметим, что масса любого симбиота ограничена $$$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]$$$.

Общий план решения задачи.

  1. Посчитаем $$$l[i][j]$$$ и $$$r[i][j]$$$ для $$$0 \leq i \leq n$$$, $$$0 \leq j \leq 2 \cdot R$$$ через рекуррентные соотношения.

  2. Для всех $$$t$$$ от $$$1$$$ до $$$\min(4 R, n - 1)$$$ посчитаем ответ $$$ans[t] = \max\limits_{0 \leq i \leq n - 1} \left( \max\limits_{\max(0, t - 2 R) \leq j \leq \min(t, 2 R)} l[i][j] + r[i][t - j] - a[i] \right)$$$.

  3. Если $$$n - 1 < 2 \cdot R$$$, то $$$ans[n - 1] = \max\limits_{0 \leq i \leq n - 1} \left( \max\limits_{\max(0, n - 2 R) \leq j \leq \min(n - 1, 2 R)} l[i][j] + r[i][n - j] - a[i] \right)$$$.

  4. Выведем выводить ответы на запросы. Для всех $$$t_i$$$ либо уже посчитан, либо он равен ответу при $$$t = min(n - 1, 4 R)$$$, который посчитан.

Общее время работы — $$$\mathcal{O}(R^2 \cdot n + m) = \mathcal{O}(n + m)$$$.