Overview

This problem asks for the earliest time (makespan) at which \(N\) printers can finish processing all \(M\) print jobs. It is solved by combining binary search on the answer with a greedy feasibility check.

Analysis

Key Observations

1. “Can all jobs be processed by time \(t\)?” has monotonicity
   If processing is possible at time \(t\), then it is obviously also possible at any \(t' > t\). This monotonicity allows us to binary search on the answer.

2. Given a time \(t\), the number of jobs each printer can handle is determined
   Printer \(i\) can process \(\lfloor t / T_i \rfloor\) jobs by time \(t\).

3. Jobs with larger page counts have fewer usable printers
   By considering jobs in decreasing order of page count, a greedy approach that assigns jobs starting from those with the fewest available printers is effective.

Problems with the Naive Approach

Trying to explicitly assign jobs to printers leads to combinatorial explosion and TLE. The key is to reduce the problem to a “decision problem” via binary search and perform the check efficiently.

Correctness of the Check (Hall’s Theorem Perspective)

Sort both jobs and printers in decreasing order of capacity. The top \(k\) jobs with the largest page counts can only be processed by printers whose capacity is at least as large. Therefore, if for every \(k\), “the total processing capacity of printers that can handle the top \(k\) jobs \(\geq k\)” holds, then a valid assignment for all jobs exists (this corresponds to Hall’s Marriage Theorem).

Algorithm

1. Sort printers in decreasing order of \(W_i\), and sort jobs in decreasing order of \(P_j\).
2. If the largest job \(P_1\) cannot be processed by any printer, output \(-1\).
3. Binary search on the answer. The check function check(t) works as follows:
   • Maintain a pointer ptr and the cumulative processing capacity sum of the printer group.
   • Iterate through jobs in decreasing order. For the \(k\)-th job:
     • Sequentially include printers while printers[ptr].first >= jobs[k], adding \(\lfloor t / T_{\text{ptr}} \rfloor\) to sum.
     • If sum < k + 1, return false (the top \(k+1\) jobs cannot all be processed).
   • If all jobs pass the check, return true.
4. Output the result of the binary search.

Concrete Example

Printers: \((W=10, T=2), (W=5, T=1)\); Jobs: \(P=8, P=4, P=3\)

For \(t=4\): - Printer 1 can process \(\lfloor 4/2 \rfloor = 2\) jobs - Printer 2 can process \(\lfloor 4/1 \rfloor = 4\) jobs - Jobs in decreasing order: \(8, 4, 3\) - \(k=0\): \(P=8\) → Only printer 1 can handle it → \(sum=2 \geq 1\) ✓ - \(k=1\): \(P=4\) → Printer 2 is also included → \(sum=2+4=6 \geq 2\) ✓ - \(k=2\): \(P=3\) → \(sum=6 \geq 3\) ✓ - Check result: feasible

Complexity

• Time complexity: \(O((N + M) \log(M \times \max(T_i)))\)
  • Binary search runs \(O(\log(M \times 10^9)) \approx O(60)\) iterations
  • Each check takes \(O(N + M)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Upper bound of binary search: The worst case is processing all jobs on a single printer, giving an upper bound of \(M \times 10^9\).

• Overflow prevention: If sum exceeds \(M\), clamp it to \(M\). Since \(\lfloor t / T_i \rfloor\) can become very large, use long long and clamp appropriately.

• Pointer reuse: Since both jobs and printers are sorted, moving the pointer in one direction is sufficient to achieve the \(O(N + M)\) check.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    vector<pair<long long, long long>> printers(N);
    for (int i = 0; i < N; i++) {
        cin >> printers[i].first >> printers[i].second;
    }
    
    vector<long long> jobs(M);
    for (int j = 0; j < M; j++) {
        cin >> jobs[j];
    }
    
    sort(printers.begin(), printers.end(), [](const auto& a, const auto& b) {
        return a.first > b.first;
    });
    
    sort(jobs.begin(), jobs.end(), greater<long long>());
    
    if (jobs[0] > printers[0].first) {
        cout << -1 << endl;
        return 0;
    }
    
    auto check = [&](long long t) -> bool {
        long long sum = 0;
        int ptr = 0;
        for (int k = 0; k < M; k++) {
            while (ptr < N && printers[ptr].first >= jobs[k]) {
                sum += t / printers[ptr].second;
                if (sum >= (long long)M) sum = (long long)M;
                ptr++;
            }
            if (sum < (long long)(k + 1)) return false;
        }
        return true;
    };
    
    long long lo = 0, hi = (long long)M * 1000000000LL;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    cout << lo << endl;
    return 0;
}

---

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