O(n ^ 2) Propagation DP
Intuition\n Describe your first thoughts on how to solve this problem. \nThe key observation about dp approach is that if we\'re selecting  k positions to be ma
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key observation about dp approach is that if we\'re selecting $$ k$$ positions to be made $$0$$ at successive intervals then we should select the position with in increasing order of $$nums2[i]$$.\nLet\'s prove this below,\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n$$S$$ = sum of values in nums1\n$$A$$ = sum of values in nums2\n\nThe final value after $$i$$ seconds without making any operations on the array will be: $$S + A * i$$\n\nNow imagine the situation after $$i$$ seconds as a 2D matrix where first row is $$nums1$$ and next $$i$$ rows are same as $$nums2$$ array\n\nAt this point of time we have to try to minimize the total sum of the matrix. At $$i$$ seconds we can select at max $$i$$ columns make all their elements from $$time = 0$$ to some $$time <= i$$. So obviously we\'ve to try to select maximum possible ending time to reduce the matrix sum. But we have to select only distinct time instants. i.e. we cannot select same row number for any two columns. Think a little and you\'ll find that the column in which value of $$nums2[i]$$ is maximum should be selected most later in time to kill more occurrances of $$nums2[i]$$ in matrix. This would lead to a conclusion that we have select the columns in increasing order of $$nums2[i]$$.\n\nIf we rearrange the values $$nums2$$ along with their corresponding $$nums1$$ values, it wouldn\'t affect the answer.\n\nSo now pair $$nums1$$ and $$nums2$$ and sort it according increasing order of $$nums2$$ to make it easier for applying dynamic programming on it.\n\n## Understanding dp approach:\nfor simplification:\n$$a = nums1$$\n$$b = nums2$$\n\nAfter time $$k$$, we\'ll have $$k$$ columns where we\'ve applied the operations and $$n - k$$ columns where no operations been applied\n\nEquation of matrix at time $$k$$ will be:\n\n\n$$[(a[i_1] + b[i_1] * k) +  (a[i_2] + b[i_2] * k) + .... + (a[i_(n-k)] + b[i_(n-k)])] - [(a[j_1] + b[j_1]) + (a[j_2] + 2 * b[j_2]) + .... + (a[j_k] + k * b[j_k])]$$\n\nso basically we have to maximize the second term which is\n\n$$(a[j_1] + b[j_1]) + (a[j_2] + 2 * b[j_2]) + .... + (a[j_k] + k * b[j_k])$$\nwe can write it as\n$$(a[j_1] + a[j_2] + .... + a[j_k]) + (b[j_1] + 2 * b[j_2] + .... + k * b[j_k])$$\n\nSo basically at time $$k$$ we have to select a subsequence of length $$k$$ which has maximum value of the above expression\n\nconsider $$dp[i][j]$$ here $$i$$ refers to the prefix of the array $$a/b$$ and $$j$$ refers to the time instant $$j$$ and $$dp[i][j]$$ is the maximum sum of a subsequence of length $$j$$ selected from first $$i$$ positions.\n\nwe know that our array $$b$$ is sorted so at the position which is selected at time instant $$j$$ is always greater than the one selected at time instant $$j - 1$$. As we\'re selecting $$b[i]$$ in it\'s increasing order.\n\nlet\'s understand the transtitions to maximize $$dp[i][j]$$.\n- for $$dp[i][j]$$ either we\'d select the current column $$i$$ at $$jth$$ time instant or we do not select it.\n- If we don\'t select it then it means we\'ve already selected $$j$$ positions from first $$i - 1$$ elements.\n- If we select it then we must\'ve selected $$j - 1$$ positions from $$i - 1$$ elements\n\nso final dp equation:\n\n$$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i] + b[i] * j)$$\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n ^ 2 + n  *log(n))$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n ^ 2)$$\n# Code\n```\nclass Solution {\npublic:\n    int minimumTime(vector<int>& a, vector<int>& b, int x) {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0); cout.tie(0); cerr.tie(0);\n        int n = a.size();\n        int sum = accumulate(a.begin(), a.end(), 0);\n        int add = accumulate(b.begin(), b.end(), 0);\n        vector<pair<int,int>> v(n);\n        for(int i = 0; i < n; i++) v[i] = {b[i], a[i]};\n        sort(v.begin(), v.end());\n        for(int i = 0; i < n; i++) b[i] = v[i].first, a[i] = v[i].second;\n        vector<vector<int>> dp(n + 1, vector<int> (n + 1));\n        if(sum <= x) return 0;\n        for(int i = 1; i <= n; i++){\n            for(int j = 1; j <= i; j++){\n                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1] + b[i - 1] * j);\n            }\n        }\n        for(int i = 1; i <= n; i++){\n            if(sum + add * i - dp[n][i] <= x) return i;\n        }\n        return -1;\n    }\n};\n```
['Dynamic Programming', 'C++']