I read the editorial and i have understood the solution . Two key points in the solution are :
1.sorting on the basis of beauty.
2.observing that $$$max(c_i,a_j-a_i)=c_i+max(0,a_j-a_i-c_i)$$$.
After that finding solution is trivial.
I have personally solved problems with similar difficulties but i always wonder how the people who solved this in contest reached to such points. I can come up with such observations but it always take lot of time .
Can people who solved this during the contest share the thought process.
Thanks
I took advantage that in whatever case, I will visit all nodes. So, I will spend anyways minimum of $$$\sum\limits_{i=1}^{n}{c_i}$$$. So I took advantage of that to try to minimize cost of $$$max((a_j-a_i)-c_i,0)$$$ in total. I solved it after the contest by few minutes as I made a stupid bug :/ But got its idea in contest time.
Short answer: Intuition
An answer, which is more specific to this problem (or how I came up with it): So we can see, that we will visit all the nodes and we leave every node at some point in the journey. Looking at the formula, we can see that we will pay at least $$$c_i$$$ for each node, since the cost will always be bigger than that (because of the maximum. But when do we pay more? When $$$c_i$$$ is smaller than the difference of heights. The thought process behind is trying to figure out, when we actually pay more than only $$$c_i$$$. This then naturally leads to thinking, that each node has some "reach", nodes you can visit for free, and everything above it costs more. Also, as soon as you're on the top, you can visit all the unvisited nodes for free when going down. Thus we only need to find a path of minimal cost going upwards, so let's just sort them increasingly by heights.
This may sound more like a writeup of the solution, but this is exactly my thought process, how I came up with it. I even finished in a different way, by just smashing segtree and dp on it, without thinking any further, as this allows you to code it in very few minutes while already thinking about the next problem and is somewhat guaranteed to work as it's dp.
For this specific problem, I think the key was in plotting the cities as points of coordinates (a, c)
Once you plot the points, it became obvious that the distance can only be not c when going to the right, so all it's obvious that I only needed to find the "extra distance" (max(0, aj-ai-ci)) from the leftmost point to the rightmost point and add that by the values of c. From there, I find the simplest data structure that fits the job (in this case set).