結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー gew1fw
提出日時 2025-06-12 14:08:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,130 bytes
コンパイル時間 528 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 160,624 KB
最終ジャッジ日時 2025-06-12 14:09:10
合計ジャッジ時間 21,780 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 24 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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 T
    sorted_T = sorted(tasks, key=lambda x: x[0])
    # Sort tasks by D for prefix sum
    sorted_D = sorted(tasks, key=lambda x: x[1])
    max_D = max(d for t, d in sorted_T)
    prefix_D = [0] * (N + 1)
    for i in range(N):
        prefix_D[i+1] = prefix_D[i] + sorted_D[i][1]
    
    def get_total_sum(m):
        left = 0
        right = N - 1
        best = -1
        while left <= right:
            mid = (left + right) // 2
            if sorted_D[mid][1] <= m:
                best = mid
                left = mid + 1
            else:
                right = mid - 1
        if best == -1:
            return 0
        else:
            return prefix_D[best + 1]
    
    def can_schedule(high_tasks):
        if not high_tasks:
            return True
        last_T = high_tasks[0][0]
        for i in range(1, len(high_tasks)):
            current_T = high_tasks[i][0]
            if current_T < last_T + K:
                return False
            last_T = current_T
        return True
    
    def compute_added_sum(high_tasks, m):
        added_sum = 0
        # Precompute T list for binary search
        T_list = [t for t, d in sorted_T]
        # Handle before first high_task
        if high_tasks:
            first_T = high_tasks[0][0]
            start = 0
            end = first_T - K
            if end >= start:
                left = bisect.bisect_left(T_list, start)
                right_idx = bisect.bisect_right(T_list, end) - 1
                if left <= right_idx:
                    for i in range(left, right_idx + 1):
                        t, d = sorted_T[i]
                        if d <= m:
                            added_sum += d
                    # Now, need to select tasks greedily with K spacing
                    # To do this correctly, we need to process the tasks in the window and select optimally
                    # This part was incorrect before, now we need to correctly select the tasks
                    window_tasks = [sorted_T[i] for i in range(left, right_idx + 1) if sorted_T[i][1] <= m]
                    window_tasks.sort(key=lambda x: -x[1])
                    last_selected = -float('inf')
                    current_added = 0
                    for task in window_tasks:
                        if task[0] >= last_selected + K:
                            current_added += task[1]
                            last_selected = task[0]
                    added_sum = current_added
        # Handle between high_tasks
        for i in range(len(high_tasks) - 1):
            prev_T = high_tasks[i][0]
            next_T = high_tasks[i+1][0]
            start = prev_T + K
            end = next_T - K
            if start > end:
                continue
            left = bisect.bisect_left(T_list, start)
            right_idx = bisect.bisect_right(T_list, end) - 1
            if left > right_idx:
                continue
            window_tasks = [sorted_T[i] for i in range(left, right_idx + 1) if sorted_T[i][1] <= m]
            window_tasks.sort(key=lambda x: -x[1])
            last_selected = -float('inf')
            current_added = 0
            for task in window_tasks:
                if task[0] >= last_selected + K:
                    current_added += task[1]
                    last_selected = task[0]
            added_sum += current_added
        # Handle after last high_task
        if high_tasks:
            last_T = high_tasks[-1][0]
            start = last_T + K
            left = bisect.bisect_left(T_list, start)
            window_tasks = [sorted_T[i] for i in range(left, N) if sorted_T[i][1] <= m]
            window_tasks.sort(key=lambda x: -x[1])
            last_selected = -float('inf')
            current_added = 0
            for task in window_tasks:
                if task[0] >= last_selected + K:
                    current_added += task[1]
                    last_selected = task[0]
            added_sum += current_added
        return added_sum
    
    low = 0
    high = max_D
    answer_m = high
    answer_sum = sum(d for t, d in sorted_T)
    
    while low <= high:
        mid = (low + high) // 2
        high_tasks = [task for task in sorted_T if task[1] > mid]
        if can_schedule(high_tasks):
            total_sum = get_total_sum(mid)
            added_sum = compute_added_sum(high_tasks, mid)
            current_sum = total_sum - added_sum
            if mid < answer_m or (mid == answer_m and current_sum < answer_sum):
                answer_m = mid
                answer_sum = current_sum
            high = mid - 1
        else:
            low = mid + 1
    
    if answer_sum == 0 and answer_m == 0:
        print(0)
        print(0)
    else:
        print(answer_m)
        print(answer_sum)

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