Let's look at the following DP: $$$d_{i,j,k}$$$ is the largest expected value if we used $$$j$$$ Poke Balls and $$$k$$$ Ultra Balls on the first $$$i$$$ Pokemon. There are four transitions from each state, corresponding to whether or not we used or didn't use a Poke Ball and an Ultra Ball on the $$$i$$$-th Pokemon. Clearly this solution has time complexity $$$O(n^3)$$$. However, if we shuffle the input, the optimal solution (imagined as a path through the 3D DP space) will not deviate much from the straight line connecting $$$(0,0,0)$$$ and $$$(n,a,b)$$$. If we only compute DP values inside a "tube" with some radius $$$r$$$ containing this straight line, it will have very high probability of containing the optimal solution, so the computed solution will be correct. By "tube", I mean the set of points $$$(i,x,y)$$$ such that $$$|x - \frac{ia}{n}| \leq R$$$, and $$$|y - \frac{ib}{n}| \leq R$$$. The complexity is $$$O(nr^2)$$$. Right now I don't have a rigorous proof but I think that in general a good value for $$$r$$$ is on the order of $$$\sqrt n$$$, which leads to an $$$O(n^2)$$$ solution.

For this problem, I originally used $$$r = 128$$$, however, even $$$r = 32$$$ worked and $$$r = 16$$$ only failed on the 84th testcase. Note that this approach does not depend on testcases being "weak". No matter what the testcases are, a lower bound on the probability of success can be computed.