Maximum Total Beauty of the Gardens
Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens.
You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the i^th garden. Flowers that are already planted cannot be removed. You are also given an integer newFlowers, which is the maximum number of flowers that Alice can additionally plant, and the integers target, full, and partial.
A garden is considered complete if it has at least target flowers. The total beauty of the gardens is determined as the sum of the following:
- The number of complete gardens multiplied by
full. - The minimum number of flowers in any of the incomplete gardens multiplied by
partial. If there are no incomplete gardens, then this value will be0.
Return the maximum total beauty that Alice can obtain after planting at most newFlowers flowers.
Example 1
Input
flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1Output
14Planting to make the gardens
[3, 6, 2, 2] gives 1 complete garden and a minimum incomplete value of 2, for total beauty 1 * 12 + 2 * 1 = 14, which is maximal.Example 2
Input
flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6Output
30Planting to make the gardens
[5, 4, 5, 5] gives 3 complete gardens and a minimum incomplete value of 4, for total beauty 3 * 2 + 4 * 6 = 30, which is maximal.Constraints
- 1 <= flowers.length <= 10^5
- 1 <= flowers[i], target <= 10^5
- 1 <= newFlowers <= 10^10
- 1 <= full, partial <= 10^5