Overview

This is a problem where you can harvest at most one fruit at or below the stepladder’s height during each of \(M\) harvest chances, and you want to maximize the total deliciousness. It can be solved efficiently using a greedy approach with a heap.

Analysis

Key Insight: The order of harvest chances is not essential

At first glance, it seems like the order matters since chances occur in order \(j = 1, 2, \ldots, M\), but in fact only the “assignment” of which fruit is harvested with which stepladder matters.

For example, consider the case \(L = [3, 5, 2]\). An assignment where a fruit at height 2 is picked during the 3rd chance (stepladder height 2), and a fruit at height 4 is picked during the 2nd chance (stepladder height 5), is valid. In other words, we only need to satisfy the condition that “at most one fruit with height less than or equal to the stepladder is assigned to each stepladder.”

Problems with the naive approach

Trying all possible assignments leads to combinatorial explosion. Since \(N, M\) can be up to \(2 \times 10^5\), even \(O(NM)\) may not be fast enough.

Solution: Sort + Greedy

Sort the stepladder heights in ascending order and process them from smallest to largest. For each stepladder, select the most delicious fruit among those within reach.

Why this is optimal (exchange argument): - Fruits reachable by a shorter stepladder are always reachable by a taller stepladder - Therefore, there is no need to “save” fruits for later — picking the most delicious reachable fruit is always the best choice - Even if the optimal solution had a different assignment, it can be shown through exchange that it yields a value equal to or less than this greedy solution

Algorithm

1. Sort the fruits in ascending order of height \(D_i\)
2. Sort the stepladder heights \(L_j\) in ascending order
3. Prepare a max-heap (priority queue)
4. Process the sorted stepladders from smallest to largest:
   • Add all not-yet-added fruits with height less than or equal to the current stepladder’s height to the heap
   • If the heap is not empty, extract the fruit with the highest deliciousness and add it to the total
5. Output the total

Concrete Example

Fruits: (height 2, deliciousness 10), (height 3, deliciousness 5), (height 5, deliciousness 8) Stepladders (sorted): [2, 4, 5]

• Stepladder 2: Fruits with height ≤ 2 → Add {deliciousness 10} to heap → Obtain 10
• Stepladder 4: Fruits with height ≤ 4 → Add {deliciousness 5} → Obtain 5
• Stepladder 5: Fruits with height ≤ 5 → Add {deliciousness 8} → Obtain 8

Total: \(10 + 5 + 8 = 23\)

Complexity

• Time complexity: \(O(N \log N + M \log M + (N + M) \log N)\)
  • Sorting fruits: \(O(N \log N)\)
  • Sorting stepladders: \(O(M \log M)\)
  • Heap operations: Each fruit is pushed/popped at most once, so \(O(N \log N)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Since Python does not have a max-heap, we negate the values and use heapq (min-heap)

• By using a fruit pointer fruit_idx and adding sorted fruits to the heap sequentially from the beginning, we efficiently manage which fruits are reachable for each stepladder

• Input is read all at once using sys.stdin.buffer.read() for faster I/O

  Source Code

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    fruits = []
    for i in range(N):
        D = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        fruits.append((D, V))
    
    L = []
    for j in range(M):
        L.append(int(input_data[idx])); idx += 1
    
    # Sort fruits by height
    fruits.sort(key=lambda x: x[0])
    
    # Sort chances by L value
    sorted_L = sorted(L)
    
    # Greedy: process chances from smallest L to largest
    # For each chance, add all fruits with D <= L to max-heap, pick the best
    max_heap = []  # store negative values for max-heap
    fruit_idx = 0
    total = 0
    
    for l in sorted_L:
        # Add all fruits reachable with this ladder height
        while fruit_idx < N and fruits[fruit_idx][0] <= l:
            heapq.heappush(max_heap, -fruits[fruit_idx][1])
            fruit_idx += 1
        
        # Pick the most valuable fruit if available
        if max_heap:
            total += -heapq.heappop(max_heap)
    
    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.