← All solutions

Shortest judge solution: 650 bytes. Shortest team solution (during contest): 668 bytes.

The first thing to note is that the problem is scale-invariant: if we multiply the dimensions w and h by a factor f, the optimal positions to place the shafts will be scaled by a factor f and the total excavation cost will be scaled by a factor f². Thus let us normalize the size to w = 1 and h < 1.

Now suppose we have fixed the placement 0 < x < 1 of the right-most vertical shaft. An optimal solution subject to this restriction looks as follows:

• The dirt in the mother well is transported directly upwards for a cost of h²/2
• The dirt in the horizontal channel between points x and 1 is split up, some of it being taken right and then up the mother well, and some of it being take left and then up the shaft at position x. Given the position x ≤ x₀ ≤ 1 of the breakpoint – how much dirt to move to the left and how much to move to the right – the cost of this part is a quadratic function in x₀, so with a little pen and paper work one can figure out the best choice of x₀ and therefore the cost of this part.
• The remaining dirt is excavated according to an optimal solution with n − 1 shafts in a qanat of width x and height h · x. By scale invariance this can easily be computed from an optimal solution with n − 1 shafts in a qanat of width 1 and height h, so by iteratively computing the solution for 1, 2, . . . shafts, we can assume we know the cost of this part as well.

When one works out the details (with some more pen and paper work), one sees that the resulting cost is a quadratic function in x, so the choice of x that minimizes the overall cost can again be figured out.