3219. Minimum Cost for Cutting Cake II Hard

1/**
2 * [3219] Minimum Cost for Cutting Cake II
3 *
4 * There is an m x n cake that needs to be cut into 1 x 1 pieces.
5 * You are given integers m, n, and two arrays:
6 * 
7 * 	horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.
8 * 	verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.
9 * 
10 * In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:
11 * <ol>
12 * 	Cut along a horizontal line i at a cost of horizontalCut[i].
13 * 	Cut along a vertical line j at a cost of verticalCut[j].
14 * </ol>
15 * After the cut, the piece of cake is divided into two distinct pieces.
16 * The cost of a cut depends only on the initial cost of the line and does not change.
17 * Return the minimum total cost to cut the entire cake into 1 x 1 pieces.
18 *  
19 * <strong class="example">Example 1:
20 * <div class="example-block">
21 * Input: <span class="example-io">m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]</span>
22 * Output: <span class="example-io">13</span>
23 * Explanation:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/04/ezgifcom-animated-gif-maker-1.gif" style="width: 280px; height: 320px;" />
25 * 
26 * 	Perform a cut on the vertical line 0 with cost 5, current total cost is 5.
27 * 	Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
28 * 	Perform a cut on the horizontal line 0 on 3 x 1 subgrid with cost 1.
29 * 	Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.
30 * 	Perform a cut on the horizontal line 1 on 2 x 1 subgrid with cost 3.
31 * 
32 * The total cost is 5 + 1 + 1 + 3 + 3 = 13.
33 * </div>
34 * <strong class="example">Example 2:
35 * <div class="example-block">
36 * Input: <span class="example-io">m = 2, n = 2, horizontalCut = [7], verticalCut = [4]</span>
37 * Output: <span class="example-io">15</span>
38 * Explanation:
39 * 
40 * 	Perform a cut on the horizontal line 0 with cost 7.
41 * 	Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.
42 * 	Perform a cut on the vertical line 0 on 1 x 2 subgrid with cost 4.
43 * 
44 * The total cost is 7 + 4 + 4 = 15.
45 * </div>
46 *  
47 * Constraints:
48 * 
49 * 	1 <= m, n <= 10^5
50 * 	horizontalCut.length == m - 1
51 * 	verticalCut.length == n - 1
52 * 	1 <= horizontalCut[i], verticalCut[i] <= 10^3
53 * 
54 */
55pub struct Solution {}
56
57// problem: https://leetcode.com/problems/minimum-cost-for-cutting-cake-ii/
58// discuss: https://leetcode.com/problems/minimum-cost-for-cutting-cake-ii/discuss/?currentPage=1&orderBy=most_votes&query=
59
60// submission codes start here
61
62impl Solution {
63    pub fn minimum_cost(m: i32, n: i32, horizontal_cut: Vec<i32>, vertical_cut: Vec<i32>) -> i64 {
64        
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_3219() {
76    }
77}
78