Overview

Given \(N\) staff members and \(M\) tasks, the problem asks to pair them under the skill level constraint (staff’s skill \(\geq\) task’s required skill), maximize the total number of pairs, and compute the revenue (number of pairs \(\times C\)).

Analysis

The core of this problem lies in “which staff should be assigned to which task for maximum efficiency.”

For example, if a highly skilled staff member handles an easy task, there might be no one left to handle a difficult task that comes later. Therefore, the following greedy approach is effective:

1. Focus on staff members with lower skills first.
2. Among the tasks that staff member can handle, assign the one with the lowest required skill.

If a staff member cannot handle even the easiest remaining task, that staff member cannot take on any task, so we move on to the next (more skilled) staff member. Conversely, if multiple staff members can handle a given task, assigning the least skilled one preserves the more skilled staff for later, which is optimal.

To implement this strategy efficiently, it is important to sort both the staff’s skill levels and the tasks’ required skill levels in ascending order beforehand.

Algorithm

Using two pointers (one for the current staff member and one for the current task) to scan through the sorted arrays:

1. Sort the staff’s skills \(A\) and the tasks’ required skills \(B\) in ascending order.
2. Initialize the staff pointer staff_idx and the task pointer task_idx to \(0\).
3. Repeat the following until either pointer reaches the end:
   • If A[staff_idx] >= B[task_idx]:
     • That staff member can handle that task.
     • Increment the pair count by \(+1\) and advance both pointers.
   • Otherwise (skill is insufficient):
     • That staff member cannot handle the current task.
     • Advance only staff_idx to try a more skilled staff member.
4. The answer is the final pair count multiplied by \(C\).

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting the staff and tasks takes \(O(N \log N)\) and \(O(M \log M)\) respectively.
  • The two-pointer scan takes \(O(N + M)\).
  • Overall, the sorting complexity dominates.
• Space complexity: \(O(N + M)\)
  • Depends on the size of the lists holding the input skill levels.

Implementation Notes

• Fast I/O: Since \(N, M\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Sort order: It is also possible to sort in descending order, but sorting in ascending order and matching “weaker with weaker” first is more intuitive and less prone to implementation errors.

  Source Code

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    C = int(input_data[2])
    
    # スタッフのスキルレベル A
    A = []
    for i in range(N):
        A.append(int(input_data[3 + i]))
        
    # タスクの必要スキルレベル B
    B = []
    for j in range(M):
        B.append(int(input_data[3 + N + j]))
        
    # スキルレベルを昇順にソート
    A.sort()
    B.sort()
    
    # 2つのポインタを用いて、割り当て可能な最大タスク数を求める
    # 貪欲法：スキルレベルの低いスタッフから順に、
    # そのスタッフがこなせる最も必要スキルレベルが低いタスクを割り当てる
    staff_idx = 0
    task_idx = 0
    count = 0
    
    while staff_idx < N and task_idx < M:
        if A[staff_idx] >= B[task_idx]:
            # スタッフがタスクを担当できる場合
            count += 1
            staff_idx += 1
            task_idx += 1
        else:
            # スタッフのスキルが足りない場合、次の（よりスキルの高い）スタッフを確認する
            staff_idx += 1
            
    # 最大売上金額を出力
    print(count * C)

if __name__ == "__main__":
    solve()

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