Overview

We precompute the “minimum required efficiency” needed to complete each job, then sort both the staff efficiencies and job requirements in ascending order and greedily assign them to find the maximum number of jobs that can be completed.

Analysis

The condition for staff \(i\) to be able to handle job \(j\) is: \(D_j \le V_i \times T_j\)

Rearranging this with respect to \(V_i\): \(V_i \ge \dfrac{D_j}{T_j}\)

Since \(V_i\) is an integer, the minimum efficiency required for job \(j\) is:

• \(\left\lceil \dfrac{D_j}{T_j} \right\rceil\)

In other words, each job can be reduced to a simple condition: “any staff member with efficiency \(\ge req_j\) can do it.”

Why naive approaches are difficult

• If we naively search for an “assignable staff member” for each job, the worst case is \(O(NM)\), which is far too slow for \(N, M \le 2\times 10^5\).
• It could also be solved as a bipartite matching problem, but the graph tends to become huge (with an enormous number of edges), making this equally impractical.

How to solve it (key insight)

Each job can be compressed into a single value, its “required efficiency \(req_j\)”, and the condition becomes simply “whether the staff member’s efficiency meets or exceeds it.” In this form, the following greedy approach is optimal:

• Process jobs in order of increasing required efficiency,
• Assign the smallest available staff member that can satisfy the requirement.

(Intuition) If we use a high-efficiency staff member for a job with a small requirement, we may later run out of staff members who can handle jobs with larger requirements. Therefore, it is best to use the “smallest staff member that just barely meets the requirement.”

Algorithm

1. Compute the required efficiency from each job \((D_j, T_j)\): \(req_j = \left\lceil \dfrac{D_j}{T_j} \right\rceil = \left\lfloor \dfrac{D_j + T_j - 1}{T_j} \right\rfloor\)
2. Sort the staff efficiency array \(V\) in ascending order.
3. Sort the required efficiency array \(req\) in ascending order.
4. Use two pointers for greedy matching:
   • If \(V[i] \ge req[j]\), job \(j\) can be assigned to staff \(i\), so assign it (answer + 1, advance both \(i\) and \(j\)).
   • Otherwise, staff \(i\) is insufficient, so move to the next staff member (advance only \(i\)).

Concrete Example

Staff efficiencies \(V=[2,5,6]\), job required efficiencies \(req=[1,5,7]\) (already sorted).

• \(2 \ge 1\) → assign (1 job completed)
• \(5 \ge 5\) → assign (2 jobs completed)
• \(6 \not\ge 7\) → cannot assign (done)

The maximum is 2 jobs.

Complexity

• Time complexity: \(O(N\log N + M\log M)\) (dominated by sorting; the matching step is \(O(N+M)\))
• Space complexity: \(O(N + M)\) (for storing the arrays)

Implementation Notes

• The required efficiency is computed using ceiling division: \(req = (D + T - 1) // T\)

• The greedy matching after sorting is implemented with two pointers, assigning “the smallest staff member that meets the requirement, processing jobs from smallest requirement first”

• \(D, T, V\) can be up to \(10^9\), but all computations can be safely handled within integer range (no issues with Python’s int)

  Source Code

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    if not it:
        return
    idx = 0
    N = it[idx]; M = it[idx + 1]; idx += 2

    V = it[idx:idx + N]
    idx += N

    req = [0] * M
    for j in range(M):
        D = it[idx]; T = it[idx + 1]; idx += 2
        req[j] = (D + T - 1) // T

    V.sort()
    req.sort()

    i = j = 0
    ans = 0
    while i < N and j < M:
        if V[i] >= req[j]:
            ans += 1
            i += 1
            j += 1
        else:
            i += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.