結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー lam6er
提出日時 2025-04-15 22:02:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,351 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 132,740 KB
最終ジャッジ日時 2025-04-15 22:03:56
合計ジャッジ時間 15,388 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    K = int(data[idx+1])
    idx +=2
    tasks = []
    for _ in range(N):
        T = int(data[idx])
        D = int(data[idx+1])
        tasks.append((T, D))
        idx +=2
    
    # Sort tasks by D in descending order
    tasks_sorted_by_d = sorted(tasks, key=lambda x: (-x[1], x[0]))
    
    schedule = []  # sorted list of T's of selected tasks
    selected_ts = set()
    sum_s = 0
    
    for T, D in tasks_sorted_by_d:
        pos = bisect.bisect_left(schedule, T)
        left_ok = True
        if pos > 0:
            prev_T = schedule[pos-1]
            if T - prev_T < K:
                left_ok = False
        right_ok = True
        if pos < len(schedule):
            next_T = schedule[pos]
            if next_T - T < K:
                right_ok = False
        if left_ok and right_ok:
            bisect.insort(schedule, T)
            selected_ts.add(T)
            sum_s += D
    
    # Compute max_d of remaining tasks
    max_d = 0
    total_d = sum(d for t, d in tasks)
    sum_ame = total_d - sum_s
    
    for t, d in tasks_sorted_by_d:
        if t not in selected_ts:
            max_d = d
            break
    
    print(max_d)
    print(sum_ame)

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