За $$$A$$$ обозначим максимальное значение $$$a_i$$$

Для начала решим задачу за $$$O(n \cdot k \cdot f(k, A))$$$ с помощью динамического программирования.

Положим $$$dp[i][j]$$$ - максимальный возможный объем наименьшего кусочка, если по первым $$$i$$$ измерениям мы разделили шоколадку на $$$j$$$ частей. Если мы разделили более чем на $$$k$$$ частей, так же положим результат в $$$dp[i][k]$$$. В пересчете нам нужно решить на сколько часей делить шоколадку вдоль очередного измерения. Рассмотрим несколько способов это сделать.

- Можно за $$$O(k)$$$ перебрать состояние, в которое переходим, и из этого посчитать на сколько частей нужно разделить шоколадку вдоль очередного измерения. - Получим $$$O(n \cdot k^2)$$$

- Можно за $$$O(A)$$$ перебрать на сколько частей мы делим шоколадку вдоль очередного измерения.

- Находясь в состоянии $$$dp[i][j]$$$, можно перебирать $$$b_i$$$ - на сколько частей делить шоколадку, пока $$$j \cdot b_i \le k$$$. Можно показать, что такое решение будет работать за $$$O(n \cdot k \cdot \ln{k})$$$

Ключевая идея

- предположим нам нужно разделить шоколадку на $$$10$$$ частей, и вдоль первых измерений мы уже разделили её на $$$5$$$ частей, или на $$$6$$$ частей, или на $$$7, 8$$$ или $$$9$$$ частей. Все эти состояния не различимы для нас, потому что во всех этих случаях нам нужно разделить шоколадку ещё хотя бы на $$$2$$$ части. Осталось понять сколько всего таких «интересных» состояний и научиться их хранить. Для этого есть несколько подходов, разберем один из них:

- нам интересны все значения $$$\lceil \frac{k}{i} \rceil$$$ для $$$i = 1, 2, \ldots k$$$ - это то, на сколько частей ещё может быть нужно разделить шоколадку. Среди них всего $$$O(\sqrt{k})$$$ различных, так как либо $$$i \le \sqrt{k}$$$, либо само значение $$$\lceil \frac{k}{i} \rceil \le \sqrt{k}$$$. Если сделать все эти числа состояниями, и пересчитываться, перебирая состояние, в которое переходить, получим $$$O(n \cdot \sqrt{k} \cdot \sqrt{k}) = O(n \cdot k)$$$ - этого всё ещё не достаточно, чтобы решить полую задачу.

Последнее наблюдение

Если мы находимся в состоянии $$$dp[i][remain]$$$ где $$$remain = \lceil \frac{k}{i} \rceil$$$ для какого-то $$$i$$$ - применим к нему ту же идею. Из него нам интересны переходы в состояния $$$\lceil \frac{remain}{j} \rceil$$$ для $$$j = 1, 2, \ldots remain$$$. Какая асимптотика получится, если перебирать только интересные переходы?

$$$n \cdot (\sum\limits_{r=1}^{\sqrt{k}}{ 2 \cdot \sqrt{r} + 2 \cdot \sqrt{\lceil \frac{k}{r} \rceil}})$$$

- можно показать, что это $$$O(n \cdot k^{3/4})$$$ - что решает задачу