Overview

There are \(N\) fruits, each with a distinct tastiness and height, and \(M\) harvesting opportunities (stepladders) with limited usable heights. Each stepladder can only be used once and can harvest one fruit located at a position at or below its height. The problem is to maximize the total tastiness of harvested fruits.

---

Analysis

This problem is about optimally deciding “which tasty fruits to collect and which stepladders to use for each.” Since we want to maximize value, we consider applying a Greedy approach.

1. Which fruits should we prioritize?

Since we want to maximize the total tastiness, we naturally want to prioritize securing “fruits with higher tastiness (\(V_i\))” first. Therefore, it is natural to sort fruits in descending order of tastiness and check from the top whether each can be harvested.

2. When multiple stepladders satisfy the condition, which one should we use?

Consider harvesting a fruit at height \(D_i\). The stepladders that can be used to harvest this fruit are all those with height at least \(D_i\) (\(L_j \geq D_i\)). If there are multiple candidate stepladders, it is optimal to use “the one with the lowest height among those satisfying the condition (closest to \(D_i\))”.

This is because if we use an unnecessarily tall stepladder here, we lose a valuable tall stepladder that could be used to harvest a “fruit at an even higher position (but still tasty)” that appears later. By preferentially consuming shorter stepladders, we can reserve taller stepladders for the future.

3. Data structure for efficient processing

We need to efficiently perform the operation of “finding the minimum element greater than or equal to a given value \(D_i\), and deleting it.” Using arrays or lists would take \(O(M)\) time for searching and deletion, resulting in \(O(N \times M)\) overall, which would exceed the time limit (TLE).

Therefore, we use a balanced binary search tree (C++’s std::multiset), which can perform insertion, binary search, and deletion all in \(O(\log M)\).

---

Algorithm

1. Sort the fruit information in descending order of tastiness \(V_i\).
2. Add all stepladder heights \(L_j\) to a std::multiset.
3. Process fruits in order from the tastiest, performing the following:
   • Use binary search (lower_bound) in the multiset to find the smallest stepladder with height at least \(D_i\).
   • If a stepladder satisfying the condition is found:
     • Decide to harvest that fruit and add its tastiness \(V_i\) to the total.
     • Remove the used stepladder from the multiset.
   • If not found:
     • Give up on that fruit and move on to the next one.
4. Output the final total tastiness.

---

Complexity

• Time Complexity: \(O(N \log N + M \log M)\)

  • Sorting fruits takes \(O(N \log N)\).
  • Inserting \(M\) stepladders into the multiset takes \(O(M \log M)\).
  • For each fruit, performing binary search and deletion in the multiset (at most \(M\) times) takes \(O(\log M)\) per operation, so \(O(N \log M)\) overall.
  • With constraints \(N, M \leq 2 \times 10^5\), the total computation is approximately \(10^7\) operations, which comfortably fits within the time limit.

• Space Complexity: \(O(N + M)\)

  • The array storing fruit information uses \(O(N)\), and the multiset managing stepladder information uses \(O(M)\) memory.

---

Implementation Notes

• Search method for std::multiset: When performing binary search on a multiset, always use the member function L.lower_bound(val). Using the generic function std::lower_bound(L.begin(), L.end(), val) will take \(O(M)\) time due to the nature of the iterators, resulting in TLE.

• Deleting duplicate elements: When deleting an element from a multiset, if you specify the value directly like L.erase(val), all elements with that value will be deleted. Since we want to delete only “one” used stepladder, always pass the iterator found during the search to delete, like L.erase(it).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct Fruit {
    long long d;
    long long v;
    // おいしさの降順でソートするための比較演算子
    bool operator<(const Fruit& other) const {
        return v > other.v;
    }
};

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<Fruit> fruits(n);
    for (int i = 0; i < n; ++i) {
        cin >> fruits[i].d >> fruits[i].v;
    }

    multiset<long long> L;
    for (int j = 0; j < m; ++j) {
        long long l;
        cin >> l;
        L.insert(l);
    }

    // おいしさの降順にソート
    sort(fruits.begin(), fruits.end());

    long long total_v = 0;
    for (const auto& fruit : fruits) {
        // 高さ fruit.d 以上の脚立のうち、最も高さが低いものを選択する
        auto it = L.lower_bound(fruit.d);
        if (it != L.end()) {
            total_v += fruit.v;
            L.erase(it); // 使用した脚立を削除
        }
    }

    cout << total_v << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.