結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー gew1fw
提出日時 2025-06-12 16:03:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,219 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 139,608 KB
最終ジャッジ日時 2025-06-12 16:04:11
合計ジャッジ時間 11,888 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    tasks = []
    max_D = 0
    sum_all = 0
    for _ in range(N):
        T = int(input[ptr])
        ptr += 1
        D = int(input[ptr])
        ptr += 1
        tasks.append((T, D))
        sum_all += D
        if D > max_D:
            max_D = D
    
    # Binary search for minimal max_D
    low = 0
    high = max_D
    answer_max = 0
    answer_sum = 0

    def can_schedule(mandatory, K):
        if not mandatory:
            return True
        sorted_mandatory = sorted(mandatory, key=lambda x: x[0])
        last = sorted_mandatory[0][0]
        for task in sorted_mandatory[1:]:
            if task[0] < last + K:
                return False
            last = task[0]
        return True

    while low < high:
        mid = (low + high) // 2
        mandatory = [task for task in tasks if task[1] > mid]
        if can_schedule(mandatory, K):
            high = mid
        else:
            low = mid + 1
    max_D_candidate = low

    # Check if the mandatory tasks can be scheduled
    mandatory = [task for task in tasks if task[1] > max_D_candidate]
    if not can_schedule(mandatory, K):
        print(0)
        print(0)
        return

    # Now construct S
    # Sort mandatory by T
    mandatory_sorted = sorted(mandatory, key=lambda x: x[0])
    scheduled_mandatory = []
    for task in mandatory_sorted:
        if not scheduled_mandatory:
            scheduled_mandatory.append(task[0])
        else:
            if task[0] >= scheduled_mandatory[-1] + K:
                scheduled_mandatory.append(task[0])
            else:
                # This should not happen because can_schedule passed
                pass

    # Process optional tasks in order of decreasing D
    optional = [task for task in tasks if task[1] <= max_D_candidate]
    optional_sorted = sorted(optional, key=lambda x: -x[1])

    current_schedule = scheduled_mandatory.copy()
    sum_S = sum(task[1] for task in mandatory_sorted)

    for task in optional_sorted:
        T, D = task
        # Find where T can be inserted
        idx = bisect.bisect_left(current_schedule, T)
        can_add = False

        # Check before first
        if idx == 0:
            if T + K <= current_schedule[0]:
                can_add = True
        # Check between idx-1 and idx
        elif idx < len(current_schedule):
            prev = current_schedule[idx-1]
            next_t = current_schedule[idx]
            if T >= prev + K and T + K <= next_t:
                can_add = True
        # Check after last
        else:
            if T >= current_schedule[-1] + K:
                can_add = True

        if can_add:
            bisect_idx = bisect.bisect_left(current_schedule, T)
            current_schedule.insert(bisect_idx, T)
            sum_S += D

    sum_Ame = sum_all - sum_S

    # If max_D_candidate is such that all tasks are optional, sum_S could be zero
    if max_D_candidate == 0 and sum_S == 0:
        print(0)
        print(0)
    else:
        print(max_D_candidate)
        print(sum_Ame)

if __name__ == "__main__":
    main()
0