結果
問題 |
No.1194 Replace
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:39:31 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 992 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 81,856 KB |
実行使用メモリ | 206,824 KB |
最終ジャッジ日時 | 2025-06-12 20:39:43 |
合計ジャッジ時間 | 7,351 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 27 |
ソースコード
import sys sys.setrecursionlimit(1 << 25) def main(): import sys input = sys.stdin.read data = input().split() n = int(data[0]) m = int(data[1]) index = 2 max_c = {} for _ in range(m): b = int(data[index]) c = int(data[index + 1]) index += 2 if b in max_c: if c > max_c[b]: max_c[b] = c else: max_c[b] = c parent = {} for x in max_c: c = max_c[x] if c > x: parent[x] = c else: parent[x] = x dp = {} def get_max(x): if x in dp: return dp[x] if x in max_c and max_c[x] > x: res = get_max(max_c[x]) dp[x] = res else: dp[x] = x return dp[x] sum_diff = 0 for x in max_c: y = get_max(x) sum_diff += (y - x) total = n * (n + 1) // 2 + sum_diff print(total) if __name__ == "__main__": main()