概要

高橋君が、与えられた順番で脚立を使って果物を収穫し、得られるおいしさの合計を最大化する問題です。

考察

この問題では、各収穫チャンスごとに「今届く高さの果物の中から最もおいしいものを選ぶ」のが最適です。しかし、単純に毎回線形探索で最大のおいしさを探すと、最悪ケースで \(O(NM)\) となり、制約が大きいため時間内に処理できません（TLE）。

そこで、「今選べる果物」を効率的に管理するために、優先度付きキュー（最大ヒープ） を使うことを考えます。
さらに、脚立の高さ \(L_j\) が必ずしも昇順で与えられないため、脚立の高さ順にソートして処理することで、徐々に選べる果物を増やしていくことができます。

具体的には： - 果物を高さ \(D_i\) の昇順にソートしておく。 - 収穫チャンスも脚立の高さ \(L_j\) の昇順に処理する。 - 各収穫チャンスにおいて、今使える脚立の高さで届く果物をヒープに追加。 - ヒープから最もおいしさの高い果物を取り出して採用する。

こうすることで、各果物は一度だけヒープに入り、各収穫チャンスで最大の要素を取り出すだけなので、全体で高速に動作します。

アルゴリズム

1. 果物リストを高さ \(D_i\) の昇順にソートする。
2. 収穫チャンスの脚立の高さ \(L_j\) を昇順にソートし、その順序で処理を行う。
3. 最大ヒープ（Pythonでは最小ヒープを負にして使う）を用意し、各収穫チャンスにおいて以下を行う：
   • 現在の脚立の高さ \(L_j\) で届く果物をすべてヒープに追加。
   • ヒープの最大値（最もおいしい果物）を取り出して答えに加える。
4. 全ての収穫チャンスを処理したら、合計値を出力。

例

例えば、果物が \((D, V) = [(1, 3), (2, 5), (3, 2)]\)、脚立が \(L = [2, 3]\) の場合：

• ソート済み果物: \([(1, 3), (2, 5), (3, 2)]\)
• 脚立昇順: \([2, 3]\)

1回目の収穫（\(L=2\)）: 高さ1と2の果物から選べ、おいしさ5を選ぶ → 合計5
2回目の収穫（\(L=3\)）: 高さ3の果物（おいしさ2）を選択可能 → 合計7

よって最大値は7。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 果物のソート: \(O(N \log N)\)
  • 収穫チャンスのソート: \(O(M \log M)\)
  • ヒープ操作（最大でN回追加、M回取り出し）: \(O((N + M) \log N)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• Pythonの heapq は最小ヒープなので、最大ヒープとして使うには要素を負にして管理する。

• 果物の追加と収穫は、ソート順を守って行う必要があるため、二つのリストを事前にソートしておく。

• ヒープが空かどうかのチェックを忘れずに（何も取れない場合はパス）。

  ソースコード

import heapq
import sys

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    fruits = []
    idx = 2
    for _ in range(N):
        D = int(data[idx])
        V = int(data[idx+1])
        fruits.append((D, V))
        idx += 2
    
    L = list(map(int, data[idx:idx+M]))
    
    # 果物を高さDでソート
    fruits.sort()
    
    # 収穫チャンスを高さLでソートしたインデックスを取得
    sorted_indices = sorted(range(M), key=lambda x: L[x])
    
    # 各収穫チャンスで選べる果物候補を管理するためのヒープ
    heap = []
    fruit_idx = 0
    total_deliciousness = 0
    
    # 高さが低い収穫チャンスから順に処理
    for i in sorted_indices:
        l = L[i]
        # 現在の脚立の高さで届く果物を全てヒープに追加（おいしさを負にして最大ヒープ）
        while fruit_idx < N and fruits[fruit_idx][0] <= l:
            heapq.heappush(heap, -fruits[fruit_idx][1])
            fruit_idx += 1
        
        # その収穫チャンスで最もおいしさの高い果物を選択
        if heap:
            total_deliciousness += -heapq.heappop(heap)
    
    print(total_deliciousness)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。