2809. Minimum Time to Make Array Sum At Most X

Problem §

Examples §

Solutions §

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        n = len(nums1)
        idxs = sorted(range(n), key=lambda x:nums2[x])
        dp = [0] * (n + 1)
        base = sum(nums1)
        incr = sum(nums2)
        # If already satisfies the requirement.
        if base <= x:
            return 0
        
        # Now, check each time point.
        for time_point in range(1, n + 1):
            curr_sum = base + incr * time_point
            # print(curr_sum)
            new_dp = [0] * (n + 1)
            for i in range(time_point, n + 1): # We do not need to select y values from the first x elements if x < y.
                new_dp[i] = max(new_dp[i - 1], dp[i - 1] + nums1[idxs[i - 1]] + time_point * nums2[idxs[i - 1]]) # The i th value has an index i - 1
                if curr_sum - new_dp[i] <= x: # If requirement matches.
                    return time_point
            dp = new_dp
        
        return -1

Output:

[0, 2, 4, 6] 

13 -> 2 + 2 + 3 + 3 + 3
[0, 0, 8, 13] 
[0, 0, 0, 20]