結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:05:19 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,415 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,732 KB |
実行使用メモリ | 131,100 KB |
最終ジャッジ日時 | 2025-06-12 16:05:28 |
合計ジャッジ時間 | 8,365 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 WA * 33 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 K = int(data[idx]) idx += 1 tasks = [] for _ in range(N): T = int(data[idx]) idx += 1 D = int(data[idx]) idx += 1 tasks.append((T, D)) tasks.sort() # Ensure tasks are sorted by T total_sum = sum(d for t, d in tasks) max_D = max(d for t, d in tasks) low = 0 high = max_D answer_M = max_D def is_valid(mandatory, K): for i in range(1, len(mandatory)): if mandatory[i][0] - mandatory[i-1][0] < K: return False return True while low <= high: mid = (low + high) // 2 mandatory = [(t, d) for t, d in tasks if d > mid] if is_valid(mandatory, K): answer_M = mid high = mid - 1 else: low = mid + 1 if answer_M == 0: print(0) print(0) return mandatory = [(t, d) for t, d in tasks if d > answer_M] if not is_valid(mandatory, K): print(answer_M) print(total_sum) return included = [False] * N for i in range(N): if tasks[i][1] > answer_M: included[i] = True sum_S = sum(d for t, d in mandatory) mand_T = [t for t, d in mandatory] for i in range(N): if not included[i] and tasks[i][1] <= answer_M: t_i = tasks[i][0] d_i = tasks[i][1] pos = bisect.bisect_left(mand_T, t_i) can_include = False if pos == 0: if not mand_T or t_i + K <= mand_T[0]: can_include = True elif pos < len(mand_T): prev = mand_T[pos - 1] next_t = mand_T[pos] if t_i >= prev + K and t_i + K <= next_t: can_include = True else: if not mand_T or t_i >= mand_T[-1] + K: can_include = True if can_include: sum_S += d_i included[i] = True bisect.insort(mand_T, t_i) max_Ame = 0 for i in range(N): if not included[i]: if tasks[i][1] > max_Ame: max_Ame = tasks[i][1] ame_sum = total_sum - sum_S print(max_Ame) print(ame_sum) if __name__ == '__main__': main()