364. Minimum Cost to Cut a Board Into Squares

A rectangular board is m units by n units and must be cut into 1x1 unit squares. Cutting along one horizontal or vertical grid line, all the way across whichever piece it currently runs through, costs a fixed amount depending only on which line it is (given as array X of m-1 horizontal-cut costs and array Y of n-1 vertical-cut costs) - but that fixed cost is paid separately for every already-separated piece the line has to cut through. Find the minimum total cost to cut the whole board into unit squares. (This is the same underlying problem as the classic 'CHOCOLA' chocolate-bar puzzle.)

Input: The first line contains m, the board's width in units. The second line contains n, the board's height in units. The third line contains m-1 space-separated integers, the horizontal cut costs. The fourth line contains n-1 space-separated integers, the vertical cut costs. Output: Print a single integer - the minimum total cost to cut the board into unit squares.

1 <= m, n <= 10^3

This is the exact same underlying problem as the classic 'CHOCOLA' chocolate-bar-breaking puzzle - recognizing that a board-cutting problem and a chocolate-breaking problem are mathematically identical is a good example of seeing through surface-level framing to the underlying structure.

Cut a rectangular board into unit squares, minimizing total cost, where each cut's cost multiplies by however many separated pieces it currently has to cut through. Brute force: Try every possible ORDER of making all the cuts and compute the total cost for each - this is factorial time, impractical, when a simple greedy 'most expensive cut first' strategy is provably optimal. Optimised: Making the MOST EXPENSIVE cut first (among all remaining cuts, both horizontal and vertical) minimizes how many times that expensive cost gets multiplied by future opposite-direction cuts - since cheaper cuts are then the ones getting multiplied more times as pieces accumulate, this greedy ordering provably minimizes total cost.

Merge the horizontal cut costs (array X) and vertical cut costs (array Y) into one combined list tagged by direction, and sort this combined list in descending order once. Then make a single pass through the sorted list, maintaining running counters horizontalPieces = 1 and verticalPieces = 1: each horizontal cut processed adds cost * verticalPieces to the total and increments horizontalPieces, while each vertical cut adds cost * horizontalPieces and increments verticalPieces. Sorting once up front and never re-scanning for the maximum again brings the total work down to just the sort plus one linear pass. Time: O((m+n) log(m+n)) Space: O(m+n)

Consider every possible order in which the m-1 horizontal cuts and n-1 vertical cuts could be performed, and for each complete ordering simulate the cutting process on the board, tracking how many separate pieces each cut has to slice through and accumulating the total cost, keeping track of the minimum cost found across all orderings. This is exhaustive and guaranteed to find the true optimum, but the number of possible cut orderings grows factorially with the number of cuts, making it usable only for very small boards. Time: O((m+n)!) Space: O(m+n)

Maintain a count of current horizontal pieces and vertical pieces, both starting at 1, along with the remaining (not-yet-used) cut costs from both arrays. Repeatedly scan through all remaining cut costs (both arrays together) to find the single largest one, perform that cut - adding cost times the current count of pieces running perpendicular to it, then incrementing the corresponding piece counter - and mark that cut as used; repeat until all cuts are exhausted. This greedily processes the most expensive cut first as the optimal strategy requires, but re-scanning for the maximum on every iteration is wasteful. Time: O((m+n)^2) Space: O(m+n)

1. Recognize that whichever cut currently costs the MOST should be made FIRST - once any cut is made, every FUTURE cut in the OTHER direction has to pass through one more separated piece, multiplying its effective total cost. 2. Sort both the horizontal and vertical cost arrays in DESCENDING order. 3. Merge them greedily: always take the larger of the two current fronts next, while tracking how many horizontal and vertical pieces exist so far (to know the multiplier for each cut).

Time: O((m+n) log(m+n)), dominated by sorting both cost arrays. Space: O(m+n), for the sorted cost arrays.

m = 1 or n = 1 (cuts needed in only one direction), all cut costs equal, and m, n at their maximum of 10^3 to confirm the greedy merge runs efficiently.

Be ready to explain WHY expensive cuts should happen FIRST (not last) - a cut made LATER gets multiplied by MORE already-separated pieces from the other direction, so you want your cheapest cuts to be the ones repeated most often, not your most expensive ones.