Problem: 1D dp speedup: (http://dmoj.ca/problem/cco19p4)

This dp satisfies the property $$$dp[j]=max_{i<j} (dp[i]+C[i][j])$$$, where $$$C[i][j]$$$ satisfies quadrangle inequality. How can I optimize to O(n log n) or O(n)?

Outline: since all queries are sorted in ascending order, I can do it with convex hull and binary search (if k=3). This gives O(n log n).

How binary search is done:

Fix $$$i<k<j$$$, we compare $$$dp[i]+C[i][j]$$$ with $$$dp[k]+C[k][j]$$$

Note $$$C[i][j]=(prefix[j]-prefix[i])^{\frac{k}{2}}$$$. It grows faster than $$$C[k][j]$$$. In fact, $$$(prefix[j]-prefix[i])-(prefix[j]-prefix[k])$$$ is an invariant, call $$$x$$$. Let $$$y=dp[k]-dp[i]$$$. Rewrite $$$C[k][j]=z, C[i][j]=z+x$$$.

Consider $$$(a,b)$$$ such that $$$a^{\frac{3}{2}}-b^{\frac{3}{2}}=y$$$, and $$$a-b=x$$$. The precise solution would use sqrt, and would take O(log n) anyways (to an error of $$$10^{-6}$$$, might raise if TLE). (Am I wrong?) Note $$$a$$$ corresponds to $$$C[i][j]$$$ and $$$b$$$ corresponds to $$$C[k][j]$$$, even though they might never be equal to those values. Then for all $$$C[i][j]>a$$$, $$$dp[i]+C[i][j]>dp[k]+C[k][j]$$$ and for all $$$C[i][j]<a$$$, $$$dp[i]+C[i][j]<dp[k]+C[k][j]$$$

Is this correct? Implementation looks rly hard.