Flowerbed Beauty on a Budget

Hard

A gardener looks after n flowerbeds. The array beds holds how many flowers already grow in each bed; they cannot be dug up. The gardener also has spare seedlings and may plant them into any beds, using at most spare flowers in total. A bed is finished once it has at least goal flowers. The beauty of the garden is the sum of two parts: - the number of finished beds times full_bonus; - the smallest flower count among the unfinished beds times partial_bonus (this part is 0 if every bed is finished). Return the largest beauty that can be reached.

Example 1

beds=[2, 5, 1], spare=4, goal=5, full_bonus=10, partial_bonus=3 → 26

Plant 3 flowers in the first bed and 1 in the last: [5, 5, 2]. Two finished beds (2 · 10 = 20) and a minimum of 2 among the unfinished ones (2 · 3 = 6), 26 in total. Spending the flowers on raising the minimum instead gives only 10 + 3 · 3 = 19.

Example 2

beds=[3, 3], spare=4, goal=5, full_bonus=6, partial_bonus=1 → 12

There are exactly enough flowers to bring both beds to 5: 2 · 6 = 12. No bed is left unfinished, so the second part of the beauty is 0.

Example 3

beds=[1, 1, 1], spare=1, goal=10, full_bonus=100, partial_bonus=2 → 2

Constraints

1 ≤ n = len(beds) ≤ 10⁵
1 ≤ beds[i], goal ≤ 10⁵
1 ≤ spare ≤ 10¹⁰
1 ≤ full_bonus, partial_bonus ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Two Pointers Binary Search Enumeration Prefix Sum Sorting

Similar problems

Common Setting at Different Step Prices Hard Studios for Recording Sessions Medium Stick Triples That Form a Triangle Medium Best-Paid Gig for Each Worker Medium Even Out With Increments Medium

Input

beds=[2, 5, 1], spare=4, goal=5, full_bonus=10, partial_bonus=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.