There are N towns in a line. Distance between town i and j is abs(j-i). We want to go from town 0 to town N-1. From town i, we can jump to any town j > i and that costs (j-i)*A[i] + (j2 - i2)*A[i]2, where A is given as input. We want to find the minimum cost needed. N <= 10^5.
There’s an O(N2) dp solution. If we remove the second part of the cost function – (j-i)*A[i] + (j2 - i2)*A[i]2, then it becomes a standard Convex Hull Trick problem (which is also on SPOJ) and can be done in O(NlogN). But we can’t use CHT here because of that part. We can change the cost function later to make it less standard-looking but I think the main idea in the solution remain will the same.