Overview

This problem is a maximum matching problem where we assign as many packages as possible to the given \(N\) trucks. Under the constraints of each truck’s weight limit, capacity limit (number of items), and each package’s weight, we find the maximum number of packages that can be delivered.

---

Analysis

Key Insight

This problem can be solved optimally using a Greedy Algorithm.

Intuitively, the optimal strategy is to process “trucks with stricter constraints” first, assigning them “the lightest packages that satisfy their constraints (= packages that have the least value to save for later trucks)”.

Specifically, we focus on the following properties: 1. Trucks with smaller weight limits \(E_i\) have fewer options for loadable packages, so they should be processed first. 2. Packages with smaller weights \(D_j\) are more versatile as they can be loaded onto more trucks, so ideally we’d like to save them and consume heavier packages (less versatile ones) first. However, trucks with strict weight limits can only carry light packages.

Therefore, by performing the assignment in the following manner, we can maximize the total number of delivered packages: - Sort trucks in ascending order of weight limit \(E_i\). - Sort packages in ascending order of weight \(D_j\). - Process trucks from the smallest weight limit, assigning “the lightest unused packages that can be loaded on that truck (weight ≤ \(E_i\))” up to the truck’s capacity limit \(C_i\).

Why is this greedy approach correct?

Consider the set of packages that can be loaded onto truck \(i\). Trucks \(i'\) processed after truck \(i\) satisfy \(E_{i'} \geq E_i\). This means that any package loadable onto truck \(i\) is also loadable onto all later trucks \(i'\).

Therefore, regardless of which packages we assign to truck \(i\), the impact on the “number of available packages” for later trucks is the same. Thus, assigning the lightest \(C_i\) unassigned packages to truck \(i\) does not disadvantage later trucks’ options.

---

Algorithm

For the sorted trucks and packages, we use a two-pointer (sliding window) technique for efficient assignment.

1. Sorting:

   • Sort trucks in ascending order of weight limit \(E_i\).
   • Sort packages in ascending order of weight \(D_j\).

2. Pointer Initialization:

   • \(L\): Index of the lightest package not yet assigned to any truck (initial value \(0\)).
   • \(R\): Right boundary of packages whose weight is at most \(E_i\) for the current truck \(i\) (initial value \(0\)).

3. Simulation: For each truck \(i\) (from \(0\) to \(N-1\)), do the following:

   • Advance pointer \(R\) as long as \(D[R] \leq E_i\) holds.
   • At this point, the “unassigned packages” loadable onto truck \(i\) are those with indices in the range \([L, R - 1]\). Their count is \(R - L\).
   • The actual number of packages \(k\) loaded onto truck \(i\) is the minimum of the truck’s capacity \(C_i\) and the number of available packages. $\(k = \min(C_i, R - L)\)$
   • Add \(k\) to the answer (total number of deliverable packages).
   • Since the lightest \(k\) packages have been consumed, advance pointer \(L\) by \(k\) (\(L \leftarrow L + k\)).

---

Complexity

Time Complexity

• Sorting:
  • Sorting trucks: \(O(N \log N)\)
  • Sorting packages: \(O(M \log M)\)
• Two-pointer traversal:
  • Within the processing of all trucks, pointer \(R\) advances at most \(M\) times in total.
  • Pointer \(L\) similarly advances at most \(M\) times in total.
  • Therefore, the traversal part runs in \(O(N + M)\) time.

The overall time complexity is \(O(N \log N + M \log M)\), which runs sufficiently fast for the constraints \(N, M \leq 2 \times 10^5\).

Space Complexity

• An array of \(O(N)\) is used to store truck information, and an array of \(O(M)\) is used to store package weights.

The overall space complexity is \(O(N + M)\).

---

Implementation Notes

• Monotonic increase of pointer \(R\): Since trucks are sorted in ascending order of weight limit \(E_i\), the value of \(R\) satisfying \(D[R] \leq E_i\) for truck \(i\) will also satisfy \(D[R] \leq E_{i+1}\) for the next truck \(i+1\). Therefore, there is no need to reset \(R\) to \(0\) for each truck; we can simply continue from its previous position. This dramatically improves the overall complexity from \(O(NM)\) to \(O(N+M)\).

• Overflow prevention: The capacity limit \(C_i\) for loadable packages and the final answer ans can potentially become large values, so in C++ we use the long long type to prevent overflow.

  Source Code

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

using namespace std;

struct Truck {
    long long E;
    long long C;
    bool operator<(const Truck& other) const {
        return E < other.E;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Truck> trucks(N);
    for (int i = 0; i < N; ++i) {
        cin >> trucks[i].E >> trucks[i].C;
    }

    vector<long long> D(M);
    for (int i = 0; i < M; ++i) {
        cin >> D[i];
    }

    sort(trucks.begin(), trucks.end());
    sort(D.begin(), D.end());

    long long ans = 0;
    int L = 0;
    int R = 0;
    for (int i = 0; i < N; ++i) {
        while (R < M && D[R] <= trucks[i].E) {
            R++;
        }
        int available = R - L;
        long long k = min(trucks[i].C, (long long)available);
        ans += k;
        L += k;
    }

    cout << ans << "\n";

    return 0;
}

---

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