Overview

This is a problem where you need to match staff skill levels with task required skill levels and determine the maximum number of tasks that can be completed. The answer is the number of completed tasks multiplied by the unit price \(C\).

Analysis

Identifying the Essence of the Problem

This problem asks for the “maximum matching” between staff and tasks. The condition for staff \(i\) to handle task \(j\) is \(A_i \geq B_j\) (skill level is at least the required skill level).

Issues with a Naive Approach

Trying all combinations of staff and tasks requires considering \(O(N \times M)\) assignments. Furthermore, finding the optimal assignment requires a bipartite matching algorithm, which has a complexity of around \(O(NM)\). Since \(N, M\) can be up to \(2 \times 10^5\), this approach is too slow.

Key Insight: A Greedy Approach Works

This problem has a special structure. Since skill levels and required skill levels are determined solely by their “relative ordering,” we can obtain the optimal solution by sorting and greedily assigning.

Intuitive Explanation: - Staff with higher skills are more likely to be able to handle any task - Tasks with higher required skills can only be handled by a limited number of staff - Therefore, staff with higher skills should be preferentially assigned to tasks with higher required skills

Verification with a Concrete Example

Staff skills: \([5, 3, 8]\) → After sorting: \([8, 5, 3]\)
Task required skills: \([4, 7, 2]\) → After sorting: \([7, 4, 2]\)

1. Staff (skill 8) and Task (required 7) → \(8 \geq 7\), so matching succeeds
2. Staff (skill 5) and Task (required 4) → \(5 \geq 4\), so matching succeeds
3. Staff (skill 3) and Task (required 2) → \(3 \geq 2\), so matching succeeds

Result: 3 tasks completed

Algorithm

1. Sort the staff skill level array \(A\) in descending order
2. Sort the task required skill level array \(B\) in descending order
3. Prepare two pointers \(i\) (for staff) and \(j\) (for tasks)
4. Repeat the following:
   • If \(A_i \geq B_j\), assign task \(j\) to staff \(i\) and advance both pointers
   • If \(A_i < B_j\), the current staff cannot handle this task, so advance only the task pointer \(j\) (to look for an easier task)
5. Output the number of successful matchings × \(C\)

Why this algorithm is correct: By assigning the hardest possible task to each staff member in order from highest skill, we avoid wasting skill “surplus” and create as many matchings as possible.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting takes \(O(N \log N)\) and \(O(M \log M)\)
  • The matching process is \(O(N + M)\) since each pointer advances at most the length of its array
• Space complexity: \(O(N + M)\)
  • Required for storing arrays \(A\) and \(B\)

Implementation Notes

• Sorting must be done in descending order (it can also be solved with ascending order using similar logic, but the pointer movement changes)

• When a matching fails, advance only the task pointer \(j\) (you might think the staff pointer should not advance since that staff member might match with an easier task later — but actually advancing \(j\) is correct. A staff member who cannot handle a task with high required skill is better off leaving lower tasks to other staff for overall efficiency)

• The final revenue is calculated as count * C. Be careful about overflow (not an issue in Python)

  Source Code

def solve():
    N, M, C = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # スタッフのスキルレベルを降順にソート
    A.sort(reverse=True)
    # タスクの必要スキルレベルを降順にソート
    B.sort(reverse=True)
    
    # 貪欲法：スキルが高いスタッフから順に、必要スキルが高いタスクを割り当てる
    count = 0
    i = 0  # スタッフのインデックス
    j = 0  # タスクのインデックス
    
    while i < N and j < M:
        if A[i] >= B[j]:
            # スタッフiがタスクjを担当できる
            count += 1
            i += 1
            j += 1
        else:
            # スタッフiはタスクjを担当できない
            # より必要スキルが低いタスクを探す
            j += 1
    
    print(count * C)

solve()

---

This editorial was generated by claude4.5opus.