Overview

A problem where you harvest at most \(M\) times from \(N\) types of fruit trees and maximize the total number of fruits obtained.

Analysis

Each time you harvest from a tree, the number of fruits obtained decreases (\(\max(F_i - (k-1) \times D_i, 0)\)). Therefore, simply “harvesting in order of largest initial yield \(F_i\)” does not necessarily give the optimal result.

For example, consider the following case: - Tree A: \(F_A = 10\), \(D_A = 9\) - Tree B: \(F_B = 8\), \(D_B = 1\) - Maximum number of harvests \(M = 2\)

Harvesting tree A twice yields \(10 + (10 - 9) = 11\) fruits. On the other hand, harvesting tree B twice yields \(8 + (8 - 1) = 15\) fruits. In this way, trees with small fatigue rates can be more profitable in the long run.

Therefore, the optimal strategy is to always choose “the harvest that yields the most fruits next.” This can be achieved with a greedy approach.

Avoiding TLE/WA

Trying all patterns causes a combinatorial explosion, so it is not practical. Also, simply iterating over the trees repeatedly does not tell us which tree to harvest from next. To efficiently retrieve and update “the number of fruits obtainable from the next best harvest,” we use a priority queue (heap).

Algorithm

1. For each fruit tree, register the initial harvest yield into the heap (only if the yield is greater than 0).
2. The heap is used as a max-heap so that “the largest number of fruits obtainable next” can always be extracted (since Python only has a min-heap, we store values with their signs inverted).
3. For each of the \(M\) harvests, do the following:
   • Extract the largest value from the heap and add it to the total.
   • Calculate the next harvest yield for that tree, and if it is positive, add it back to the heap.
4. If the heap becomes empty, no more harvests are possible, so we stop.

This results in a greedy approach that always selects “the harvest that yields the most fruits right now.”

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Initially inserting \(N\) elements into the heap → \(O(N \log N)\)
  • \(M\) operations, each removing and inserting at most one element → \(O(M \log N)\)
• Space complexity: \(O(N)\)
  • The heap holds at most \(N\) elements

Implementation Notes

• Python’s heapq is a min-heap, so to extract the maximum value, you need to negate the sign of the elements.

• Once the harvest yield becomes 0, there is no point in harvesting from that tree anymore, so it is not added back to the heap.

• sys.stdin.read is used for fast input reading.

  Source Code

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    fruits = []
    index = 2
    for _ in range(N):
        F = int(data[index])
        D = int(data[index+1])
        index += 2
        fruits.append((F, D))
    
    # 各木について、次の収穫で得られる果物の数を管理するための優先度付きキュー
    # 最大値を取り出すために符号を反転させて格納
    heap = []
    
    # 初期状態で各木の1回目の収穫をキューに追加
    for F, D in fruits:
        if F > 0:
            heapq.heappush(heap, (-F, F, D))  # (-現在の収穫量, 初回収穫量, 疲弊度)
    
    total_fruits = 0
    
    # M回まで収穫を行う
    for _ in range(M):
        if not heap:
            break
        
        # 現在最も多くの果物が得られる収穫を選択
        neg_current, current, D = heapq.heappop(heap)
        total_fruits += current
        
        # 次の収穫での果物の数を計算
        next_amount = max(current - D, 0)
        
        # 次の収穫が有効であればキューに追加
        if next_amount > 0:
            heapq.heappush(heap, (-next_amount, next_amount, D))
    
    print(total_fruits)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.