結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
![]() |
提出日時 | 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()