Simple DP in C++, java & Python
Intuition\n\nSome conclusions:\n1. Each number will be cleared to 0 at most once. Since if we clear a number twice, we can skip the first time setting to make e
# Intuition\n\nSome conclusions:\n1. Each number will be cleared to 0 at most once. Since if we clear a number twice, we can skip the first time setting to make everything earlier.\n2. The numbers with larger increasing rates (nums2[.]) should be cleared to 0 later than the numbers with smaller rates.\n\nSo if the numbers are sorted by the rates (nums2[.]), we need to select (at most) n numbers to clear in order.\n\nHowever, the difficulty is some numbers (with smaller rates) may not be selected when the sum matches the requriment.\n\n# Approach\nCreate a matrix with n rows and n columns. (To make it simpler, let indices start from 1 here).\nThe ith row and jth column is nums1[i] + nums2[i] * j, which is the value each number will be after j seconds. \n\nThe question changes into select j rows from the first j columns (one row per column), let the sum be s, we want sum(matrix[.][j]) - s <= x.\nHere sum(matrix[.][j]) is the sum of all the values in jth column which is a constant = nums1[0..n - 1] + nums2[0..n - 1] * j and x is also a constant. So our goal is to make s as large as possible.\n\nIn general to select one column in each row can be solved by graph matching, but this question\'s constraints are too large to a graph matching algorithm.\n\nWe can use dyanmaic programming.\n\ndp[i][j] means the maximum sum to select j columns from the first i rows (note j <= i).\ndp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + nums1[i] + j * nums2[i])\nwhich is basically select the jth column or not.\n\n\n# Complexity\n- Time complexity:\nO(n ^ 2)\n\n- Space complexity:\nO(n) if we do some optimizations on DP.\n\n# Code\nC++\n```\nclass Solution {\npublic:\n    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {\n        const int n = nums1.size();\n        vector<int> ind(n);\n        int s = 0, d = 0;\n        for (int i = 0; i < n; ++i) {\n            ind[i] = i;\n            s += nums1[i];\n            d += nums2[i];\n        }\n        if (s <= x) {\n            return 0;\n        }\n        sort(ind.begin(), ind.end(), [&](const int a, const int b) {\n            return nums2[a] < nums2[b];\n        });\n        vector<int> dp(n + 1);\n        int r = n + 1;\n        for (int i = 1; i <= n; ++i) {\n            for (int j = min(i, r - 1); j; --j) {\n                dp[j] = max(dp[j], dp[j - 1] + nums2[ind[i - 1]] * j + nums1[ind[i - 1]]);\n                if (s + j * d - dp[j] <= x) {\n                    r = j;\n                }\n            }\n        }\n        return r <= n ? r : -1;\n    }\n};\n```\n\nJava\n```\npublic class Solution {\n    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {\n        int n = nums1.size();\n        Integer[] ind = new Integer[n]; // Using Integer array instead of int[]\n        int s = 0, d = 0;\n        for (int i = 0; i < n; ++i) {\n            ind[i] = i;\n            s += nums1.get(i);\n            d += nums2.get(i);\n        }\n        if (s <= x) {\n            return 0;\n        }\n        Arrays.sort(ind, (a, b) -> nums2.get(a) - nums2.get(b)); // Custom comparator\n        int[] dp = new int[n + 1];\n        int r = n + 1;\n        for (int i = 1; i <= n; ++i) {\n            for (int j = Math.min(i, r - 1); j > 0; --j) {\n                dp[j] = Math.max(dp[j], dp[j - 1] + nums2.get(ind[i - 1]) * j + nums1.get(ind[i - 1]));\n                if (s + j * d - dp[j] <= x) {\n                    r = j;\n                }\n            }\n        }\n        return r <= n ? r : -1;\n    }\n}\n```\nPython:\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        n = len(nums1)\n        ind = list(range(n))\n        s, d = 0, 0\n        for i in range(n):\n            s += nums1[i]\n            d += nums2[i]\n        if s <= x:\n            return 0\n\n        # Custom comparator for sorting ind based on nums2 values\n        ind.sort(key=lambda i: nums2[i])\n\n        dp = [0] * (n + 1)\n        r = n + 1\n        for i in range(1, n + 1):\n            for j in range(min(i, r - 1), 0, -1):\n                dp[j] = max(dp[j], dp[j - 1] + nums2[ind[i - 1]] * j + nums1[ind[i - 1]])\n                if s + j * d - dp[j] <= x:\n                    r = j\n        return r if r <= n else -1\n```
['Python', 'C++', 'Java', 'Python3']