Overview

Given \(N\) part-time workers, select \(M\) of them and assign them one-to-one to \(M\) tasks. The goal is to maximize the total satisfaction (skill value − required skill value) while ensuring that everyone’s satisfaction is non-negative.

Analysis

Key Insight ①: Decomposing the Total Satisfaction

The total satisfaction can be written as:

\[\sum_{(i,j) \in \text{assignment}} (A_i - D_j) = \sum_{\text{selected } i} A_i - \sum_{j=1}^{M} D_j\]

Here, \(\sum D_j\) is a constant independent of the assignment. Therefore, to maximize the total satisfaction, we should make the sum of skill values of the chosen \(M\) people as large as possible. In other words, selecting the top \(M\) people by skill value is optimal.

Key Insight ②: If the Top \(M\) People Can’t Do It, No Set of \(M\) People Can

If a valid assignment cannot be constructed with the top \(M\) people, replacing any of them with a worker having a smaller skill value would only make things worse, so no solution exists.

Key Insight ③: Feasibility Check

We need to determine whether the chosen \(M\) people and \(M\) tasks can be paired such that \(A_i \geq D_j\) holds for every pair.

This is a well-known result from classical greedy algorithms:

Let the skill values of the selected workers sorted in ascending order be \(A'_1 \leq A'_2 \leq \cdots \leq A'_M\), and the required skill values of the tasks sorted in ascending order be \(D_1 \leq D_2 \leq \cdots \leq D_M\). A valid assignment exists ⟺ \(A'_k \geq D_k\) for all \(k\).

Intuitively, matching the hardest task to the most skilled person, the second hardest task to the second most skilled person, and so on, is the most likely way to satisfy all constraints.

Concrete Example: \(N=4, M=3\), \(A = [10, 7, 5, 3]\), \(D = [2, 4, 6]\)

• Top 3 people: \(A' = [5, 7, 10]\) (ascending), \(D = [2, 4, 6]\) (ascending)
• \(5 \geq 2\), \(7 \geq 4\), \(10 \geq 6\) → All OK
• Total satisfaction \(= (10+7+5) - (2+4+6) = 22 - 12 = 10\)

Algorithm

1. Sort \(A\) in descending order and \(D\) in ascending order.
2. Select the top \(M\) people (\(A[0], A[1], \ldots, A[M-1]\)).
3. Check feasibility: For each \(i = 0, 1, \ldots, M-1\), verify that \(A[i] \geq D[M-1-i]\).
   • This pairs \(A[0]\) (largest) with \(D[M-1]\) (largest), \(A[1]\) (2nd largest) with \(D[M-2]\) (2nd largest), and so on.
4. If all conditions are satisfied, the answer is \(\sum_{i=0}^{M-1} A[i] - \sum_{j=0}^{M-1} D[j]\). Otherwise, the answer is \(-1\).

Complexity

• Time complexity: \(O(N \log N + M \log M)\) (dominated by sorting)
• Space complexity: \(O(N + M)\)

Implementation Notes

• By sorting \(A\) in descending order and \(D\) in ascending order, the feasibility check simply compares A[i] with D[M-1-i], making the code straightforward.

• Since skill values and required values can be up to \(10^9\) and the number of people can be up to \(2 \times 10^5\), the total can reach approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    D = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    A.sort(reverse=True)
    D.sort()
    
    # To maximize the total satisfaction sum(A_i - D_j), we want to maximize sum(A_i) - sum(D_j).
    # sum(D_j) is fixed, so we want to maximize sum(A_i) of the chosen M workers.
    # We should pick the top M skilled workers and assign them to tasks.
    # But we need each assigned worker to have A_i >= D_j for their assigned task.
    
    # Greedy: Sort A descending, sort D ascending.
    # Try to assign the top M workers to tasks. Pair the largest A with the smallest D (to maximize sum and satisfy constraints).
    # Actually, to maximize the sum of A_i, we want to use the top M workers.
    # Pair them: A sorted descending with D sorted ascending -> A[0] with D[0], A[1] with D[1], ...
    # Wait, that pairs the best worker with the easiest task. The satisfaction per pair is A[i]-D[i].
    # We need A[i] >= D[i] for all pairs.
    
    # But actually, to maximize sum(A_i) we want the top M workers. Then we need a valid assignment.
    # For the top M workers (sorted descending) and tasks (sorted ascending), 
    # the optimal pairing to check feasibility is: pair the k-th largest worker with the k-th largest task.
    # i.e., A[0] with D[M-1], A[1] with D[M-2], ..., A[M-1] with D[0].
    # Wait no. Let me think again.
    
    # We want to maximize sum of A values used. So greedily pick top M workers.
    # For feasibility, we need to check if there's a valid matching where each worker can handle their task.
    # With A sorted descending and D sorted ascending:
    # A valid matching exists iff for each i in 0..M-1: A[i] >= D[M-1-i]
    # (pair largest A with largest D, second largest with second largest, etc.)
    # Actually the condition for a valid matching to exist (by Hall's theorem / greedy matching):
    # Sort both A (the chosen subset) and D in ascending order. Then A[i] >= D[i] for all i.
    
    # So: take top M from A, sort them ascending. Sort D ascending. Check A[i] >= D[i] for all i.
    # Top M from A sorted descending: A[0] >= A[1] >= ... >= A[M-1]
    # In ascending: A[M-1] <= ... <= A[0]
    # D ascending: D[0] <= D[1] <= ... <= D[M-1]
    # Condition: A[M-1-i] >= D[i] for ascending pairing, i.e. for i in 0..M-1: A_asc[i] >= D[i]
    # which means A[M-1] >= D[0], A[M-2] >= D[1], ..., A[0] >= D[M-1]
    
    # If top M workers can handle it, great. If not, we need to consider swapping some workers.
    # But actually if the top M can't do it, can a different subset do it?
    # If A[k] < D[M-1-k] for some k, replacing A[k] with a smaller value won't help.
    # So if top M doesn't work, no valid assignment exists.
    
    # Check feasibility: pair A[i] (desc) with D[M-1-i] (asc), i.e. A[i] with D[M-1-i]
    feasible = True
    for i in range(M):
        if A[i] < D[M - 1 - i]:
            feasible = False
            break
    
    if not feasible:
        print(-1)
        return
    
    # Maximum satisfaction = sum of top M A values - sum of all D values
    total = sum(A[:M]) - sum(D)
    print(total)

solve()

---

This editorial was generated by claude4.6opus-thinking.