Overview

This is a problem where, under conditions allowing multiple harvests from each tree, we maximize the total harvest amount subject to the constraint that the total number of harvests is at most \(M\).

Analysis

For each tree \(i\), the harvest amount on the \(k\)-th harvest is calculated as \(\max(F_i - (k-1) \times D_i, 0)\). A naive approach would be to list all possible harvest amounts from all trees in descending order and select the top \(M\). However, since each tree can be harvested up to \(M\) times and the number of trees \(N\) can be up to \(2 \times 10^5\), enumerating all harvest amounts would produce up to \(N \times M = 4 \times 10^{10}\) candidates, making this computationally infeasible.

Therefore, the following two observations become important: 1. The harvest amounts from each tree decrease in an arithmetic progression 2. We should prioritize selecting larger harvest amounts first

Based on these observations, using a heap (priority queue) to efficiently manage the candidates with the largest harvest amounts is an effective approach.

Algorithm

1. Sort the trees in descending order of their initial harvest amount \(F_i\)
2. Prepare a min-heap and maintain the current total harvest amount and the heap size (number of harvests)
3. For each tree, while the harvest amount is greater than 0, increase the harvest count \(k\) and perform the following:
   • Calculate the current harvest amount
   • If the heap size is less than \(M\), add the harvest amount to the heap and add it to the total
   • If the heap is full (size \(M\)), compare the minimum value in the heap with the current harvest amount, and if the current value is larger, replace the minimum value
4. Output the final total harvest amount

With this approach, we generate harvest amounts from each tree only as needed, while always maintaining the top \(M\) maximum harvest amounts.

Complexity

• Time complexity: \(O(N \log M + M \log M)\)
  • Sorting the trees: \(O(N \log N)\)
  • Processing each tree: \(O(M \log M)\) in the worst case
  • Overall \(O(N \log N + M \log M)\), but since \(N\) and \(M\) are of similar magnitude, this can be considered \(O(N \log N)\)
• Space complexity: \(O(M)\)
  • Since the heap size is at most \(M\)

Implementation Notes

• Use a min-heap so that the current minimum harvest amount can be accessed in \(O(1)\)

• By using the heapreplace operation, the minimum value in the heap can be efficiently replaced

• For each tree, terminate processing as soon as the harvest amount becomes 0 or less to avoid unnecessary computation

• By sorting trees in descending order of initial harvest amount, larger harvest amounts are processed first

  Source Code

import heapq

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    M = int(data[1])
    trees = []
    for i in range(n):
        F = int(data[2 + 2*i])
        D = int(data[3 + 2*i])
        trees.append((F, D))
    
    trees.sort(key=lambda x: x[0], reverse=True)
    
    heap = []
    total = 0
    for F, D in trees:
        k = 1
        while F > 0 and k <= M:
            current = F - (k-1)*D
            if current <= 0:
                break
            if len(heap) < M:
                heapq.heappush(heap, current)
                total += current
            else:
                if heap[0] < current:
                    total += current - heap[0]
                    heapq.heapreplace(heap, current)
                else:
                    break
            k += 1
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.