Hello Codeforces,

Is anyone familiar with this problem:

Consider an array of items with labels $$$1, \dots, n$$$ the $$$i$$$th of which has a weight $$$W_i$$$ and a cost $$$C_i$$$. The array must be partitioned into disjoint subarrays. The weight of a subarray from $$$i$$$ to $$$j$$$ is the sum $$$W_i + W_{i+1} + \dots + W_{j}$$$ and the cost is the maximum $$$\max(C_i, C_{i+1}, \dots, C_{j})$$$. No subarry in the partition can exceed a given maximum weight $$$W_\max$$$. Subject to this contraint, we wish to minimize the sum of subarray costs, i.e. the sum of maximums.

I have devised a solution that is $$$O(n \log n)$$$. I wonder if this is a well known problem and if a linear time solution exists. Also, are there any published results in the literature?

I am also curious about the extension of this problem to trees. Partition a tree into paths subject to the same constraints.