I recently came across this problem Icy Roads of Nomel from Petrozavodsk Summer-2013. Gennady Korotkevich Contest 1. The problem statement is simple:

You are given an $$$(n+1)\times (m+1)$$$ grid with row costs $$$a_1,a_2,\dots,a_{n+1}$$$ and column costs $$$b_1,b_2,\dots,b_{m+1}$$$. You are at $$$(1,1)$$$ and want to go to $$$(n+1,m+1)$$$ by repeatedly performing one of the two following operations when you are at $$$(x,y)$$$:

• Move to $$$(x,y+1)$$$ with a cost of $$$a_x$$$;
• Move to $$$(x+1,y)$$$ with a cost of $$$b_y$$$.

You want to know what is the minimum total cost you can achieve. The constraints are $$$1\leq n,m\leq 5\times 10^5$$$, and costs are of magnitude $$$10^9$$$.

This does look like Problem 1 and Problem 2, where one usually utilizes the convexity of costs to speed up the dynamic programming. However, here the costs are arbitrary, and there is absolutely no convexity.

From reading some code from the Atcoder mirror, (I think), the solution looks like performing some kind of greedy on two lower convex hulls formed by points $$$(i,a_i)$$$ and points $$$(j,b_j)$$$. However, I have no idea how to prove this. Could someone please help? Many thanks in advance!