Overview

This is a problem where \(M\) part-time workers are each assigned to different business days to maximize the total expected sales. Each part-time worker can only work on business days with a skill level requirement at or below their own skill level, and only one worker can be assigned per day.

Analysis

In this problem, it is crucial to determine which business day each part-time worker is assigned to. A naive greedy approach of sequentially selecting business days with the highest expected sales would be inappropriate, as it ignores the skill level constraints.

The key observation is that the following greedy strategy is optimal: “Process part-time workers in ascending order of skill level, and for each worker, select the business day with the highest expected sales among the days they can work.” This works because workers with lower skill levels have fewer candidate business days to choose from, so their limited options should be secured first.

A naive approach that linearly searches for assignable business days each time would result in \(O(NM)\) overall complexity, which would TLE given the large constraints. To efficiently find the maximum sales, we speed things up using a priority queue (heap).

Algorithm

1. Sort the business days in ascending order of required skill level \(H_i\).
2. Sort the part-time workers in ascending order of skill level \(P_j\).
3. Process part-time workers in order from lowest to highest skill level.
4. Add the business days where the current worker can work (\(H_i \leq P_j\)) to a heap that maintains expected sales \(S_i\) in descending order.
5. Select the day with the highest expected sales from the heap and add that sales amount to the answer.
6. If there are no assignable business days, output -1.

Concrete Example

For example, given the following input:

N=3, M=2
H = [2, 1, 3]
S = [100, 200, 300]
P = [2, 3]

• Business days after sorting: \((1, 200), (2, 100), (3, 300)\)
• Worker skills: \([2, 3]\)

The first worker (skill 2) can choose from \((1,200)\) and \((2,100)\), so they select sales of 200. The next worker (skill 3) selects \((3,300)\). The total sales is \(200 + 300 = 500\).

Complexity

• Time complexity: \(O(N \log N + M \log M + N \log N)\) → Overall \(O((N + M) \log N)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Both business days and part-time workers should be sorted by skill level.

• To efficiently retrieve the maximum expected sales, Python’s heapq module is used with negated values to simulate a max-heap.

• For each part-time worker, assignable business days are added to the heap sequentially from the front, ensuring no duplicates in processing.

  Source Code

import sys
from heapq import heappush, heappop

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    H = [0] * N
    S = [0] * N
    index = 2
    for i in range(N):
        H[i] = int(data[index])
        S[i] = int(data[index+1])
        index += 2
    
    P = list(map(int, data[index:index+M]))
    
    # 営業日を (H_i, S_i) のタプルで持つ
    days = [(H[i], S[i]) for i in range(N)]
    # H_i でソートしておく
    days.sort()
    
    # アルバイトもスキルレベルでソート
    P.sort()
    
    # 各アルバイトに対して、割り当て可能な営業日のうち売上見込みが最大のものを選ぶ
    # 売上見込みの最大値を効率的に管理するために、優先度付きキューを使う
    
    # 割り当て可能な営業日を管理するためのヒープ
    # ただし、売上見込みの最大値を取り出すために、-S_i をヒープに入れる
    heap = []
    
    total_profit = 0
    day_index = 0
    
    # スキルレベルが低いアルバイトから順に処理
    for p in P:
        # このアルバイトが割り当て可能な営業日をヒープに追加
        while day_index < N and days[day_index][0] <= p:
            heappush(heap, -days[day_index][1])
            day_index += 1
        
        # 売上見込みが最大のものを割り当てる
        if heap:
            max_profit = -heappop(heap)
            total_profit += max_profit
        else:
            # 割り当て可能な営業日がない場合
            print(-1)
            return
    
    print(total_profit)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.