Problem 403736 · medium · Phase 04 Non-Linear Data Structures

Orchard Harvest Rounds

heaps · greedy · max-heap · ceil division

An orchard has trees whose current fruit counts are trees. You will perform exactly k harvest rounds. In each round you pick one tree, collect all of its fruit (adding that count to your score), and the tree regrows to ceil(count / 3) fruit, so it can be picked again later.

Return the maximum score you can collect in k rounds.

Examples

Input:  trees = [10, 10, 10, 10, 10], k = 5
Output: 50
Explanation: pick each tree once.

Input:  trees = [1, 10, 3, 3, 3], k = 3
Output: 17
Explanation: pick the 10 (regrows to 4), then that same tree again for 4 (regrows to 2),
             then one of the 3s: 10 + 4 + 3 = 17.

Constraints

  • 1 <= len(trees) <= 10**5, 1 <= trees[i] <= 10**9
  • 1 <= k <= 10**5
  • Target complexity: O(n + k log n).

Goals

  • Drive a repeated best-choice simulation with a max-heap
  • Compute ceil(x / 3) with integer arithmetic
  • Accumulate a score across k rounds
Starting Python…