結果
問題 | No.1194 Replace |
ユーザー |
![]() |
提出日時 | 2025-03-20 21:08:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,172 bytes |
コンパイル時間 | 142 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 186,932 KB |
最終ジャッジ日時 | 2025-03-20 21:08:41 |
合計ジャッジ時間 | 8,002 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 27 |
ソースコード
import sys from collections import defaultdict def main(): input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 M = int(input[idx]) idx += 1 valid_ops = [] for _ in range(M): B = int(input[idx]) idx += 1 C = int(input[idx]) idx += 1 if C > B: valid_ops.append((B, C)) max_replace = defaultdict(int) for B, C in valid_ops: if B in max_replace: if C > max_replace[B]: max_replace[B] = C else: max_replace[B] = C if not max_replace: print(N * (N + 1) // 2) return nodes = set() for B in max_replace: nodes.add(B) nodes.add(max_replace[B]) nodes = sorted(nodes, reverse=True) max_value = {k: k for k in nodes} for k in nodes: if k in max_replace: c = max_replace[k] if max_value[c] > max_value[k]: max_value[k] = max_value[c] original = N * (N + 1) // 2 delta = 0 for B in max_replace: delta += (max_value[B] - B) print(original + delta) if __name__ == "__main__": main()