TheRealSamuel/LeetCodeProblem

1{2    "id": 3500,3    "name": "minimum_cost_for_cutting_cake_ii",4    "difficulty": "Hard",5    "link": "https://leetcode.com/problems/minimum-cost-for-cutting-cake-ii/",6    "date": "2024-07-07 00:00:00",7    "task_description": "There is an `m x n` cake that needs to be cut into `1 x 1` pieces. You are given integers `m`, `n`, and two arrays: `horizontalCut` of size `m - 1`, where `horizontalCut[i]` represents the cost to cut along the horizontal line `i`. `verticalCut` of size `n - 1`, where `verticalCut[j]` represents the cost to cut along the vertical line `j`. 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: Cut along a horizontal line `i` at a cost of `horizontalCut[i]`. Cut along a vertical line `j` at a cost of `verticalCut[j]`. After the cut, the piece of cake is divided into two distinct pieces. The cost of a cut depends only on the initial cost of the line and does not change. Return the **minimum** total cost to cut the entire cake into `1 x 1` pieces. **Example 1:** **Input:** m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5] **Output:** 13 **Explanation:** Perform a cut on the vertical line 0 with cost 5, current total cost is 5. Perform a cut on the horizontal line 0 on `3 x 1` subgrid with cost 1. Perform a cut on the horizontal line 0 on `3 x 1` subgrid with cost 1. Perform a cut on the horizontal line 1 on `2 x 1` subgrid with cost 3. Perform a cut on the horizontal line 1 on `2 x 1` subgrid with cost 3. The total cost is `5 + 1 + 1 + 3 + 3 = 13`. **Example 2:** **Input:** m = 2, n = 2, horizontalCut = [7], verticalCut = [4] **Output:** 15 **Explanation:** Perform a cut on the horizontal line 0 with cost 7. Perform a cut on the vertical line 0 on `1 x 2` subgrid with cost 4. Perform a cut on the vertical line 0 on `1 x 2` subgrid with cost 4. The total cost is `7 + 4 + 4 = 15`. **Constraints:** `1 <= m, n <= 105` `horizontalCut.length == m - 1` `verticalCut.length == n - 1` `1 <= horizontalCut[i], verticalCut[i] <= 103`",8    "public_test_cases": [9        {10            "label": "Example 1",11            "input": "m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]",12            "output": "13 "13        },14        {15            "label": "Example 2",16            "input": "m = 2, n = 2, horizontalCut = [7], verticalCut = [4]",17            "output": "15 "18        }19    ],20    "private_test_cases": [21        {22            "input": [23                89625,24                86605,25                [],26                []27            ],28            "output": 27018437367729        },30        {31            "input": [32                24520,33                74173,34                [],35                []36            ],37            "output": 6305673566438        },39        {40            "input": [41                86957,42                32234,43                [],44                []45            ],46            "output": 9743379749147        },48        {49            "input": [50                85068,51                26951,52                [],53                []54            ],55            "output": 7968365505656        },57        {58            "input": [59                9975,60                93053,61                [],62                []63            ],64            "output": 3232799872065        },66        {67            "input": [68                32757,69                15609,70                [],71                []72            ],73            "output": 1789151083674        },75        {76            "input": [77                11492,78                52523,79                [],80                []81            ],82            "output": 2108435132483        },84        {85            "input": [86                84008,87                3918,88                [],89                []90            ],91            "output": 1152480754792        },93        {94            "input": [95                73955,96                16674,97                [],98                []99            ],100            "output": 42937148241101        },102        {103            "input": [104                30041,105                32034,106                [],107                []108            ],109            "output": 33349734393110        }111    ],112    "haskell_template": "minimumCost :: Int -> Int -> [Int] -> [Int] -> Int\nminimumCost m n horizontalCut verticalCut ",113    "ocaml_template": "let minimumCost (m: int) (n: int) (horizontalCut: int list) (verticalCut: int list) : int =  ",114    "scala_template": "def minimumCost(m: Int,n: Int,horizontalCut: List[Int],verticalCut: List[Int]): Int = { \n    \n}",115    "java_template": "class Solution {\n    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {\n        \n    }\n}",116    "python_template": "class Solution(object):\n    def minimumCost(self, m, n, horizontalCut, verticalCut):\n        \"\"\"\n        :type m: int\n        :type n: int\n        :type horizontalCut: List[int]\n        :type verticalCut: List[int]\n        :rtype: int\n        \"\"\"\n        "117}