結果
問題 | No.1995 CHIKA Road |
ユーザー |
![]() |
提出日時 | 2022-07-01 21:40:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 263 ms / 2,000 ms |
コード長 | 480 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 156,416 KB |
最終ジャッジ日時 | 2024-11-26 04:24:56 |
合計ジャッジ時間 | 6,482 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
compress = lambda arr: {e: i for i, e in enumerate(sorted(set(arr)))} n, m = map(int, input().split()) t = (n - 1) * 2 a = [0] * m b = [0] * m for i in range(m): a[i], b[i] = map(int, input().split()) cp = compress([1] + a + b + [n]) n = len(cp) g = [[] for _ in range(n)] for i in range(m): g[cp[a[i]]].append(cp[b[i]]) dp = [0] * n for i in range(n - 1): dp[i + 1] = max(dp[i + 1], dp[i]) for j in g[i]: dp[j] = max(dp[j], dp[i] + 1) print(t - dp[n - 1])