Overview

This problem asks you to find the “minimum time” to complete all \(M\) print requests using the given \(N\) printers while satisfying the page number constraints.

Since we need to find “the minimum time to complete all requests (minimizing the maximum),” we can solve this by combining binary search on the answer with a greedy approach.

Analysis

1. Converting to a Decision Problem (Introducing Binary Search)

Directly solving the problem “What is the minimum time \(X\) to complete all requests?” is difficult. However, by fixing the time and rephrasing it as the decision problem: “Can all requests be completed within time \(X\)?” (check(X)), it becomes relatively easy to solve.

This decision problem has monotonicity: the larger \(X\) is, the more likely it is “possible,” and the smaller it is, the more likely it is “impossible.” Therefore, we can use binary search to find the minimum \(X\) that satisfies the condition.

2. How to Solve the Decision Problem check(X) (Greedy Approach)

When time \(X\) is fixed, the maximum number of requests that each printer \(i\) can process within time \(X\) is \(\lfloor X / T_i \rfloor\).

Requests have the constraint that “a request with page count \(P_j\) can only be processed by a printer whose maximum page capacity \(W_i\) is at least \(P_j\).” Requests with larger page counts have fewer available printer options. Therefore, a greedy approach of prioritizing the assignment of requests with larger page counts first is optimal.

Specifically, the process is as follows: 1. Sort printers in descending order of maximum page capacity \(W_i\), and sort requests in descending order of page count \(P_j\). 2. Process requests from largest to smallest. For the current request \(P_j\), make all printers that can handle it (those satisfying \(W_i \geq P_j\)) “available.” 3. Maintain the “total number of processable requests within time \(X\)” across all available printers. 4. To process request \(P_j\), decrease the total processable count by \(1\). If the processable count reaches \(0\), the request cannot be processed, so we determine that time \(X\) is insufficient.

Since we process requests from largest to smallest, any printer that has just become available can also handle all subsequent smaller requests (\(P_{j'} \leq P_j\)). Therefore, it is safe to immediately allocate available slots to the current request.

3. Determining Impossible Cases

If the request with the largest page count \(P_0\) exceeds the capacity of the printer with the largest maximum page capacity \(W_0\) (i.e., when \(W_0 < P_0\)), it is impossible to process regardless of how much time is allowed. In this case, we immediately output -1. In all other cases, all requests can be processed if given sufficient time.

---

Algorithm

1. Initial Check:

   • Sort printers in descending order of \(W_i\) and requests in descending order of \(P_j\).
   • If \(W_0 < P_0\), output -1 as it is impossible to process, and terminate.

2. Setting the Binary Search Range:

   • Minimum time low = 1
   • Maximum time high = 2 * 10^14 (In the worst case, one printer processes all requests: \(M \times \max(T_i) = 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\))

3. Executing the Binary Search:

   • Set mid = (low + high) / 2 and perform check(mid).
   • If check(mid) is true, try to find a shorter possible time by setting high = mid - 1 and updating the answer candidate.
   • If check(mid) is false, the time is insufficient, so set low = mid + 1.

---

Complexity

• Time Complexity: \(O(N \log N + M \log M + (N + M) \log(\text{high}))\)

  • Sorting takes \(O(N \log N + M \log M)\).
  • The number of binary search iterations is \(\log_2(2 \times 10^{14}) \approx 48\).
  • Within each check function, the pointer to printers advances at most \(N\) times in total (similar to the two-pointer technique), so each check runs in \(O(N + M)\).
  • Overall, this comfortably fits within the time limit.

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

  • Only arrays storing printer and request information are used.

---

Implementation Notes

• Preventing Overflow: When summing up the processable count (\(X / T_i\)) for each printer in the check function, the total can become extremely large and may overflow even with long long type. Since the required total processable count is at most \(M\) requests, you can safely prevent overflow by clipping the total with an upper bound of \(M\) when adding: min(total_capacity + cap, (long long)M).

  Source Code

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

using namespace std;

struct Printer {
    long long W, T;
    bool operator<(const Printer& other) const {
        return W > other.W; // Sort in descending order of W
    }
};

int main() {
    // Optimize standard I/O operations for performance
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<Printer> printers(N);
    for (int i = 0; i < N; ++i) {
        cin >> printers[i].W >> printers[i].T;
    }

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

    // Sort printers and requests in descending order
    sort(printers.begin(), printers.end());
    sort(P.begin(), P.end(), greater<long long>());

    // If the largest request cannot be handled by the best printer, it's impossible.
    if (printers[0].W < P[0]) {
        cout << -1 << "\n";
        return 0;
    }

    // Decision function to check if all requests can be completed within time X
    auto check = [&](long long X) -> bool {
        long long total_capacity = 0;
        int idx = 0;
        for (int j = 0; j < M; ++j) {
            // Add capacities of all printers that can handle the current request size
            while (idx < N && printers[idx].W >= P[j]) {
                long long cap = X / printers[idx].T;
                total_capacity = min(total_capacity + cap, (long long)M); // Prevent overflow
                idx++;
            }
            if (total_capacity == 0) {
                return false;
            }
            total_capacity--;
        }
        return true;
    };

    // Binary search for the minimum time
    long long low = 1;
    long long high = 2e14; // Max possible answer: M * max(T) = 2e5 * 1e9 = 2e14
    long long ans = high;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1; // Try to find a smaller valid time
        } else {
            low = mid + 1;  // Increase the time limit
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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