It's abc163_e.

• There is an editorial in English.
• However, note that the problem may be quite hard for you (it's rated $$$2037$$$ on AtCoder).

I believe there is a greedy solution here that works in $$$O(n \log n)$$$ time

Strategy : You sort the towers with height and take the highest tower and put it at the most corner point possible, and you repeat.

Ex: [5, 3, 1, 2, 7] --> [7, 2, 1, 3, 5] (greedy solution)

Explanation : put 7 at the other corner, put 5 at opposite corner, put 3 at next opposite corner, put 2 at next opposite corner. Finally last element stays at its place. (only place possible for 1 is its initial position)

Proof: I'll sketch the basic idea of the proof

Suppose $$$O$$$ is optimal arrangement of towers and suppose there is an inversion i.e. there exist pairs $$$(h_j, h_k)$$$ such that $$$h_j$$$ is placed at $$$r$$$ and $$$h_k$$$ is placed at $$$i$$$ with $$$h_j>h_k$$$ and $$$h_j$$$ is farther from $$$i$$$ than $$$r$$$.

Swap these two towers, change in score = (new-score)$$$(h_k \times |k-r| + h_j \times |j-i|)-$$$ (old-score)$$$(h_k \times |i-k| + h_j \times |j-r|)$$$ = $$$h_k(|k-r|-|i-k|)+h_j(|j-i|-|j-r|)$$$

Assume WLOG $$$i < r$$$ and so $$$i < r< j$$$.

Now $$$|k-r|-|i-k| = r-i$$$ if $$$k<i$$$ and $$$r+i-2k$$$ if $$$i<k<r$$$ and $$$i-r$$$ if $$$k>r$$$

For $$$k<i$$$ we get $$$h_k(r-i)+h_j(r-i)\geq0$$$

For $$$i<k<r$$$ we get $$$h_k(i+r-2k)+h_j(r-i) > h_k(i-r)+h_j(r-i) = (h_j-h_k)(r-i)\geq 0$$$

For $$$k>r$$$ we get $$$h_k(i-r) + h_j(r-i) = (h_j-h_k)(r-i)\geq 0$$$

Thus, we can improve our score using these swaps and our optimal solution can be converted to greedy solution produced by the algorithm described

Hope this was helpful!

PS: I realised it is lot more subtle than that, you need to identify the correct corner to push large towers to