This concerns the following problem: 680D - Bear and Tower of Cubes. Here's a rough outline of my thoughts while solving this problem.

Let $$$f(m, x)$$$ be the optimal number of boxes (we can ignore the part about maximizing $$$X$$$, it's trivial to extend the solution to also accomplish this) for input $$$m$$$, where we are only allowed to use boxes of length at most $$$x$$$. The answer to the original problem is $$$f(m, 10^5)$$$, we have the base case $$$f(m, 0)=0$$$, and $$$f$$$ satisfies the recurrence

Evaluating $$$f(m, x)$$$ with DP is too slow for large $$$m$$$, but we can make the observation that for each pair $$$(m, x)$$$, it is either optimal to take a cube or not to take a cube, and that if it is optimal to take for $$$(m, x)$$$, then it must also be optimal to take for $$$(m+1, x)$$$. I don't have a rigorous proof for this, but it is intuitively true and AC submission confirms this. So, we can binary search on the "turning point" $$$p_x$$$ such that it is optimal to take for all $$$m\geq p_x$$$, and optimal not to take for all $$$m<p_x$$$. This yields a correct solution, but still gets TLE for large $$$m$$$.

The next observation is that since we only care about $$$x\leq 10^5$$$, we could theoretically precompute all $$$10^5$$$ values of $$$p_x$$$, which would yield a fast greedy solution. $$$10^5$$$ is a little too large for a precomputed table of long longs so this isn't really feasible. However, while computing these values, I noticed some patterns in the values of $$$p_x$$$, and began investigating various properties of the sequence, and I eventually decided to look at the sequence of $$$p_x-x^3$$$, which displayed some really weird behavior. Basically, for $$$x$$$ from $$$1$$$ to $$$10^5$$$ it only took on $$$12$$$ distinct values, which were non-decreasing. The sequence looked like

Where the later values were repeated many times. And so, I managed to use these values to encode all of the values of $$$p_x$$$, in order to get an AC submission for the problem: 84824995.

So, the obvious question here is, why does this work? I have no idea where this pattern is coming from.