2809. Minimum Time to Make Array Sum At Most x

You are given two 0-indexed integer arrays nums1 and nums2 of equal length. Every second, for all indices 0 <= i < nums1.length, value of nums1[i] is incremented by nums2[i]. After this is done, you can do the following operation:

• Choose an index 0 <= i < nums1.length and make nums1[i] = 0.

You are also given an integer x.

Return the minimum time in which you can make the sum of all elements of nums1 to be less than or equal to x, or -1 if this is not possible.

c++

class Solution {
public:
    int minimumTime(vector<int>& A, vector<int>& B, int x) {
        vector<pair<long long, long long>> S;
        for(int i = 0; i < A.size(); i++) S.push_back({B[i], A[i]});
        sort(begin(S), end(S));
        vector<long long> dp(A.size() + 1, 0);
        for(auto& [b,a] : S) {
            for(int i = A.size() - 1; i >= 0; i--) {
                dp[i+1] = max(dp[i+1], dp[i] + (i + 1) * b + a);
            }
        }
        long long sum1 = accumulate(begin(B), end(B), 0ll), sum2 = accumulate(begin(A), end(A), 0ll);
        for(int i = 0; i <= A.size(); i++) {
            if(sum1 * i + sum2 - dp[i] <= x) return i;
        }
        return -1;
    }
};