提出 #68048186

---

ソースコード 拡げる

import sys
import heapq
from typing import List, Tuple


def get_max_earnings(n: int, d: int, jobs: List[Tuple[int, int]]) -> int:
    """
    最大収益を計算する関数

    Parameters:
    - n: int - 仕事の数
    - d: int - 就業可能日数
    - jobs: List[Tuple[int, int]] - 各仕事の情報 (開始日Xi, 報酬Yi)

    Returns:
    - int - 得られる最大報酬の合計
    """

    # 各日ごとの仕事リストに分類
    job_by_day: List[List[int]] = [[] for _ in range(d + 1)]
    for x, y in jobs:
        if x <= d:
            job_by_day[x].append(y)

    # 最大ヒープ（heapqで負値にして使用）
    max_heap: List[int] = []
    total: int = 0

    for day in range(1, d + 1):
        # 今日から可能な仕事をヒープに追加
        for reward in job_by_day[day]:
            heapq.heappush(max_heap, -reward)  # 最大ヒープのためマイナス

        # 今日やるべき最大報酬の仕事を選択
        if max_heap:
            total += -heapq.heappop(max_heap)

    return total


def main() -> None:
    """
    標準入力からデータを受け取り、最大収益を出力するメイン関数
    """

    input_data = sys.stdin.read().strip().split('\n')
    n, d = map(int, input_data[0].split())
    jobs: List[Tuple[int, int]] = [tuple(map(int, line.split())) for line in input_data[1:]]

    result: int = get_max_earnings(n, d, jobs)
    print(result)


if __name__ == "__main__":
    main()

提出情報

ジャッジ結果