Overview

This is a problem where you select \(M\) people from \(N\) part-time workers, assign each of them to one of \(M\) tasks, and maximize the total of everyone’s “skill value \(-\) required skill value.” The constraint is that everyone’s satisfaction must be non-negative (skill value \(\geq\) required skill value).

Analysis

The key points for solving this problem are: “which \(M\) people to select” and “how to assign the selected people.”

1. Transforming the total satisfaction formula

Let the skill values of the selected \(M\) people be \(A'_{1}, A'_{2}, \dots, A'_{M}\), and the required skill values of the assigned tasks be \(D_{1}, D_{2}, \dots, D_{M}\). The total satisfaction can be expressed as: $\(\sum_{i=1}^{M} (A'_{i} - D_{i}) = \left( \sum_{i=1}^{M} A'_{i} \right) - \left( \sum_{i=1}^{M} D_{i} \right)\)\( Here, the sum of required skill values \)\sum D_i\( is constant regardless of which workers are assigned. Therefore, **to maximize satisfaction, we simply need to maximize the sum of skill values \)\sum A’_i\( of the chosen \)M$ people**.

To maximize the sum of skill values, we simply choose the \(M\) workers with the highest skill values.

2. Determining whether a valid assignment exists

When selecting the top \(M\) people by skill value, we need to verify whether an assignment satisfying the condition (everyone’s satisfaction is non-negative) exists. Consider the greedy approach of “assigning the person with the highest skill to the task with the highest required skill, and so on in order.” If we sort skill values in descending order as \(A_1, A_2, \dots, A_N\) and required skill values in descending order as \(D_1, D_2, \dots, D_M\), then a valid assignment exists if and only if all of the following conditions hold: - \(A_1 \geq D_1\) - \(A_2 \geq D_2\) - \(\dots\) - \(A_M \geq D_M\)

If \(A_i < D_i\) for some \(i\), then the condition cannot be satisfied even with the top \(M\) people. In this case, mixing in workers with even lower skill values would only make the situation worse, so we can conclude that no valid assignment of \(M\) people is possible.

Algorithm

1. Sort the workers’ skill values \(A\) in descending order.
2. Sort the tasks’ required skill values \(D\) in descending order.
3. For \(i = 1, \dots, M\), check whether there exists any position where \(A_i < D_i\).
   • If such a position exists, a valid assignment is impossible, so output -1 and terminate.
4. If \(A_i \geq D_i\) for all \(i\), compute and output \((\sum_{i=1}^{M} A_i) - (\sum_{j=1}^{M} D_j)\).

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting skill values takes \(O(N \log N)\), and sorting required skill values takes \(O(M \log M)\). The subsequent verification and sum computation take \(O(M)\), so overall the sorting is the dominant factor.
• Space complexity: \(O(N + M)\)
  • This is the size of the arrays needed to store the input values.

Implementation Notes

• Since \(N, M\) can be as large as \(2 \times 10^5\), in Python it is advisable to use fast input methods such as sys.stdin.read().split().

• When computing the total satisfaction, it is efficient to first calculate the sum of the top \(M\) elements of \(A\) and the sum of all elements of \(D\), then perform the subtraction.

  Source Code

import sys

def solve():
    # Reading all input from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of workers, M: number of tasks
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A: Skill values of N workers
    # D: Requirement values of M tasks
    # Using list(map(int, ...)) for faster conversion from string to integer
    A = list(map(int, input_data[2:2+N]))
    D = list(map(int, input_data[2+N:2+N+M]))
    
    # To maximize the sum of satisfaction, we should try to use the M workers 
    # with the largest skill values. If a valid assignment exists for any 
    # set of M workers, it will also exist for the M workers with the highest skills.
    # A set of M workers with skills S_1 >= S_2 >= ... >= S_M can be matched 
    # to M tasks with requirements D_1 >= D_2 >= ... >= D_M if and only if 
    # S_i >= D_i for all i = 0, 1, ..., M-1.
    
    # Sort both workers' skill values and task requirements in descending order.
    A.sort(reverse=True)
    D.sort(reverse=True)
    
    # Check if the M largest skill values can satisfy the M task requirements.
    # If A[i] < D[i] for any i, no valid assignment exists for any set of M workers.
    for i in range(M):
        if A[i] < D[i]:
            print("-1")
            return
    
    # If a valid assignment exists, the satisfaction sum is (sum of skills) - (sum of requirements).
    # Since the requirements are fixed, maximizing the skill sum of the M workers 
    # maximizes the total satisfaction.
    max_satisfaction = sum(A[:M]) - sum(D)
    print(max_satisfaction)

if __name__ == '__main__':
    solve()

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