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

Unable to parse markup [type=CF_MATHJAX]

grid with row costs

Unable to parse markup [type=CF_MATHJAX]

and column costs

Unable to parse markup [type=CF_MATHJAX]

. You are at $$$(1,1)$$$ and want to go to

Unable to parse markup [type=CF_MATHJAX]

by repeatedly performing one of the two following operations when you are at $$$(x,y)$$$:

• Move to

  Unable to parse markup [type=CF_MATHJAX]

  with a cost of $$$a_x$$$;
• Move to

  Unable to parse markup [type=CF_MATHJAX]

  with a cost of

  Unable to parse markup [type=CF_MATHJAX]

  .

You want to know what is the minimum total cost you can achieve. The constraints are

Unable to parse markup [type=CF_MATHJAX]

, 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

Unable to parse markup [type=CF_MATHJAX]

and points

Unable to parse markup [type=CF_MATHJAX]

. However, I have no idea how to prove this. Could someone please help? Many thanks in advance!