#1055921 (PyPy3) No.448 ゆきこーだーの雨と雪 (3)

• 問題: No.448 ゆきこーだーの雨と雪 (3)
• ユーザー: lam6er
• 提出日時: 2025-03-20 20:43:20
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 5,202 bytes
• コンパイル時間: 178 ms
• コンパイル使用メモリ: 82,532 KB
• 実行使用メモリ: 209,148 KB
• 最終ジャッジ日時: 2025-03-20 20:44:06
• 合計ジャッジ時間: 16,401 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 2 WA * 33

ソースコード

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    tasks = []
    for _ in range(N):
        T, D = int(input[ptr]), int(input[ptr+1])
        tasks.append( (T, D) )
        ptr +=2
    
    tasks.sort()
    sorted_by_t = tasks.copy()
    maxD = max(d for t, d in tasks)
    low = 0
    high = maxD
    best_max_d = maxD
    best_sum = sum(d for t, d in tasks)
    
    while low <= high:
        mid = (low + high) //2
        # Split into mandatory and optional
        mandatory = [ (t, d) for t, d in sorted_by_t if d > mid ]
        if not mandatory:
            # All can be handled by Ame
            candidate_max = 0
            candidate_sum =0
            valid = True
        else:
            # Check if mandatory can be scheduled
            prev_t = mandatory[0][0]
            valid_mandatory = True
            for i in range(1, len(mandatory)):
                if mandatory[i][0] < prev_t + K:
                    valid_mandatory = False
                    break
                prev_t = mandatory[i][0]
            if not valid_mandatory:
                # mid is too small
                low = mid +1
                continue
            # Schedule is possible. Now, sort mandatory by T.
            mandatory_times = [t for t, d in mandatory]
            optional = [ (t, d) for t, d in sorted_by_t if d <= mid ]
            optional.sort()
            # Build merged schedule
            merged = []
            if mandatory:
                merged = mandatory_times.copy()
                # Insert optional tasks
                # Insert before first
                prev = -float('inf')
                for t in optional:
                    inserted = False
                    # Check if can insert before first
                    if t[0] >= 0 and (len(merged) ==0 or t[0] + K <= merged[0]):
                        merged.insert(0, t[0])
                        inserted = True
                    else:
                        # Find position where merged[i] <= t[0] - K and merged[i+1] >= t[0] + K
                        # Using binary search
                        pos = bisect.bisect_right(merged, t[0] - K) -1
                        if pos == -1:
                            # insert after pos (before 0)
                            if len(merged) ==0:
                                merged.append(t[0])
                                inserted = True
                            else:
                                # Need t[0] + K <= merged[0]
                                if t[0] + K <= merged[0]:
                                    merged.insert(0, t[0])
                                    inserted = True
                        else:
                            after_pos = pos +1
                            if after_pos < len(merged):
                                # merged[pos] <= t[0] - K
                                if merged[pos] + K <= t[0] and t[0] + K <= merged[after_pos]:
                                    merged.insert(after_pos, t[0])
                                    inserted = True
                            else:
                                if merged[pos] + K <= t[0]:
                                    merged.append(t[0])
                                    inserted = True
                    if inserted:
                        # Maintain sorted
                        pass
            # Now, check if merged is valid (each consecutive is >= K)
            valid_merged = True
            for i in range(1, len(merged)):
                if merged[i] < merged[i-1] + K:
                    valid_merged = False
                    break
            if not valid_merged:
                low = mid +1
                continue
            # Now, find which tasks are in the merged list
            # Mandatory are already in merged
            # Optional are those in optional where their T is in merged list
            # Prepare a set of all T in merged
            merged_set = set(merged)
            # Find tasks not in merged_set
            ame_tasks = []
            for t, d in tasks:
                if d > mid:
                    continue
                if t not in merged_set:
                    # Check if d <= mid
                    ame_tasks.append(d)
            # Also include mandatory tasks if not in merged (but mandatory is already in merged)
            max_current = 0
            sum_current =0
            for d in ame_tasks:
                if d > max_current:
                    max_current = d
                sum_current +=d
            if max_current <= mid:
                valid = True
                candidate_max = mid
                candidate_sum = sum_current
            else:
                valid = False
        
        if valid:
            if candidate_max < best_max_d or (candidate_max == best_max_d and candidate_sum < best_sum):
                best_max_d = candidate_max
                best_sum = candidate_sum
            high = mid -1
        else:
            low = mid +1

    print(best_max_d)
    print(best_sum)

if __name__ == '__main__':
    main()