Overview

Given staff skills \(A_i\) and task required skills \(B_j\), we want to create as many “pairs satisfying \(A_i \ge B_j\)” as possible. The number of such pairs \(\times C\) gives the maximum revenue.

Analysis

Since the revenue is “number of completed dishes” \(\times C\), the problem reduces to finding the maximum number of assignable tasks (maximum matching count).

A naive approach might be: - Exhaustively search which task each staff member can handle (\(O(NM)\)) - Or solve it using bipartite matching (max flow)

However, with constraints \(N,M \le 2\times 10^5\), \(O(NM)\) clearly won’t fit in time, and max flow is also too heavy at this scale.

The key observation is as follows:

• When viewing tasks in “ascending order of required skill,” tasks with lower requirements can be handled by more staff (the condition is looser)
• Conversely, tasks with high required skill can only be handled by a limited number of staff (the condition is stricter)

Therefore, it is natural to assign tasks in order from easy (low required skill), choosing the staff member with the lowest skill who can handle it. This way, we “preserve high-skill staff” and maximize the possibility of completing harder tasks later.

Furthermore, if we sort staff by skill in ascending order and tasks by required skill in ascending order:

• If a staff member’s skill cannot even satisfy the current (smallest) task, that staff member definitely cannot handle any subsequent tasks (which have even higher required skills)

So it is optimal to discard that staff member and move on.

Example: - Staff \(A=[2,4,7]\) - Tasks \(B=[3,5,6]\)

Looking in ascending order: - \(2\) cannot satisfy \(3\) → This staff member can’t do any task, so skip - \(4\) satisfies \(3\) → Match (1 match) - For the next task \(5\), \(7\) satisfies it → Match (2 matches) Maximum of 2 dishes can be made.

Algorithm

1. Sort arrays \(A\) (staff skills) and \(B\) (task required skills) in ascending order.
2. Prepare two pointers \(i\) (for staff) and \(j\) (for tasks), both starting from the smallest.
3. Repeat the following:
   • If \(A[i] \ge B[j]\), this staff member can handle this task, so assign it (increment match count by \(+1\), advance both \(i\) and \(j\)).
   • Otherwise (\(A[i] < B[j]\)), this staff member cannot even handle the current smallest task and won’t be able to handle any future ones either, so only advance the staff pointer (advance \(i\)).
4. If the match count is \(cnt\), the answer is \(cnt \times C\).

This method is a greedy approach that “always assigns the smallest possible staff member to the smallest task,” which avoids eliminating future options (harder tasks) and thus yields the maximum matching count.

Complexity

• Time complexity: \(O(N\log N + M\log M)\) for sorting and \(O(N+M)\) for the two-pointer scan, so \(O(N\log N + M\log M)\) overall.
• Space complexity: \(O(N+M)\) for storing the arrays.

Implementation Notes

• Since \(N,M\) can be large, it is safe to read input quickly using something like sys.stdin.buffer.read().

• The match count \(cnt \le 2\times 10^5\) and \(C \le 10^9\), so the maximum revenue can be around \(2\times 10^{14}\), but Python’s int handles this without any issues.

• The two-pointer implementation becomes concise if you consistently follow “advance both when matched” and “advance only the staff pointer when not matched.”

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    C = next(it)
    A = [next(it) for _ in range(N)]
    B = [next(it) for _ in range(M)]

    A.sort()
    B.sort()

    i = j = 0
    cnt = 0
    while i < N and j < M:
        if A[i] >= B[j]:
            cnt += 1
            i += 1
            j += 1
        else:
            i += 1

    print(cnt * C)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.