結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー lam6er
提出日時 2025-04-16 15:39:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,827 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 163,520 KB
最終ジャッジ日時 2025-04-16 15:44:52
合計ジャッジ時間 27,570 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class Task:
    def __init__(self, T, D):
        self.T = T
        self.D = D

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    tasks = []
    for _ in range(N):
        T = int(input[ptr])
        ptr += 1
        D = int(input[ptr])
        ptr += 1
        tasks.append(Task(T, D))
    
    tasks_sorted_by_D = sorted(tasks, key=lambda x: (-x.D, x.T))
    total_sum = sum(t.D for t in tasks)
    max_D = max(t.D for t in tasks) if tasks else 0

    low = 0
    high = max_D
    answer_M = max_D
    found_valid = False

    # Binary search for the minimal M
    while low <= high:
        mid = (low + high) // 2
        # Collect mandatory tasks (D > mid)
        mandatory = []
        for t in tasks_sorted_by_D:
            if t.D > mid:
                mandatory.append(t)
            else:
                break  # since sorted descending
        
        # Check if mandatory can be scheduled
        valid = True
        prev_time = -float('inf')
        for t in mandatory:
            if t.T < prev_time + K:
                valid = False
                break
            prev_time = t.T
        
        if not valid:
            low = mid + 1
            continue
        
        # Check if there are tasks with D == mid not in mandatory
        has_mid = False
        for t in tasks:
            if t.D == mid and t not in mandatory:
                has_mid = True
                break
        
        # Handle case when M is 0
        if mid == 0:
            if not mandatory:
                # All tasks are optional, but M is 0, so Ame handles none
                has_mid = False
            else:
                has_mid = any(t.D == 0 for t in tasks if t not in mandatory)
        
        # Check validity
        if mid != 0 or (mid == 0 and mandatory):
            if not has_mid:
                # Check if there are any tasks with D == mid
                has_any_mid = any(t.D == mid for t in tasks)
                if has_any_mid:
                    valid = False
                else:
                    # No tasks with D == mid, so M is determined by the maximum of optional tasks
                    pass
        
        if valid:
            answer_M = mid
            high = mid - 1
            found_valid = True
        else:
            low = mid + 1
    
    # Determine if no tasks are assigned to Ame
    if found_valid and answer_M == 0:
        all_in_mandatory = all(t.D > 0 for t in tasks)
        if all_in_mandatory:
            print(0)
            print(0)
            return
    
    # Compute sum_S and sum_non_S
    mandatory = []
    for t in tasks_sorted_by_D:
        if t.D > answer_M:
            mandatory.append(t)
        else:
            break
    mandatory_sorted = sorted(mandatory, key=lambda x: x.T)
    schedule = [t.T for t in mandatory_sorted]
    sum_S = sum(t.D for t in mandatory_sorted)
    optional = [t for t in tasks if t.D <= answer_M]
    optional_sorted = sorted(optional, key=lambda x: (-x.D, x.T))

    # Insert optional tasks into schedule
    for t in optional_sorted:
        T = t.T
        idx = bisect.bisect_left(schedule, T)
        prev_ok = True
        if idx > 0:
            if T < schedule[idx - 1] + K:
                prev_ok = False
        next_ok = True
        if idx < len(schedule):
            if schedule[idx] < T + K:
                next_ok = False
        if prev_ok and next_ok:
            schedule.insert(idx, T)
            sum_S += t.D
    
    sum_non_S = total_sum - sum_S

    # Handle case where all tasks are handled by Yuki
    if sum_non_S == 0:
        print(0)
        print(0)
    else:
        print(answer_M)
        print(sum_non_S)

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