結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    tasks = []
    for _ in range(N):
        T = int(input[idx])
        idx += 1
        D = int(input[idx])
        idx += 1
        tasks.append((T, D))
    
    sum_total = sum(d for t, d in tasks)
    max_D = max(d for t, d in tasks)
    
    # Binary search for the minimal D_candidate
    low = 0
    high = max_D
    best_candidate = max_D
    
    while low <= high:
        mid = (low + high) // 2
        mandatory = []
        for t, d in tasks:
            if d > mid:
                mandatory.append(t)
        # Check if mandatory is valid
        valid = True
        for i in range(1, len(mandatory)):
            if mandatory[i] - mandatory[i-1] < K:
                valid = False
                break
        if valid:
            best_candidate = mid
            high = mid - 1
        else:
            low = mid + 1
    
    # Now process the best_candidate
    mandatory_times = [t for t, d in tasks if d > best_candidate]
    optional = [(t, d) for t, d in tasks if d <= best_candidate]
    
    # Sort optional by descending D, then ascending T
    optional_sorted = sorted(optional, key=lambda x: (-x[1], x[0]))
    
    s_times = sorted(mandatory_times)
    sum_S = sum(d for t, d in tasks if d > best_candidate)
    
    for t, d in optional_sorted:
        pos = bisect.bisect_left(s_times, t)
        left_ok = True
        right_ok = True
        if pos > 0:
            if t - s_times[pos - 1] < K:
                left_ok = False
        if pos < len(s_times):
            if s_times[pos] - t < K:
                right_ok = False
        if left_ok and right_ok:
            bisect.insort(s_times, t)
            sum_S += d
    
    # Compute max_ame
    max_ame = 0
    for t, d in optional:
        idx_pos = bisect.bisect_left(s_times, t)
        if idx_pos < len(s_times) and s_times[idx_pos] == t:
            continue
        else:
            if d > max_ame:
                max_ame = d
    
    if len(s_times) == N:
        print(0)
        print(0)
    else:
        print(max_ame)
        print(sum_total - sum_S)

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