Comment by chaoxu

This is monotone min-plus, so you can do it with even better running time than what you listed (which is just min-plus). Also, if all numbers are at most k, you can even get running time related to k too, replacing n with k is obviously possible, but more can be done too. I feel this might be likely in practice where k might be small?