Maximal Score After Applying K Operations
You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.
In one operation:
- Choose an index
isuch that0 <= i < nums.length. - Increase your score by
nums[i]. - Replace
nums[i]withceil(nums[i] / 3).
Return the maximum possible score you can attain after applying exactly k operations.
The ceiling function ceil(val) is the least integer greater than or equal to val.
Example 1
Input
nums = [10,10,10,10,10], k = 5Output
50Apply the operation to each array element exactly once, giving a final score of 10 + 10 + 10 + 10 + 10 = 50.
Example 2
Input
nums = [1,10,3,3,3], k = 3Output
17Select index 1 twice for scores 10 and 4, then select index 2 for score 3, for a total score of 17.
Constraints
- 1 <= nums.length, k <= 10^5
- 1 <= nums[i] <= 10^9