結果
問題 | No.1995 CHIKA Road |
ユーザー |
![]() |
提出日時 | 2023-04-07 05:52:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 761 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 84,440 KB |
最終ジャッジ日時 | 2024-10-02 18:28:53 |
合計ジャッジ時間 | 7,140 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
# Nが大きい、ダイクストラ法ではおそらくできない # a<bであり、start<goalなので、1次元dpで前から決定できるのでは # と思ったがNがまだ大きすぎる # 要はショートカットを何回使えるか、使えた回数分だけ歩数も少なくなる # ショートカットを何回使えるかをどうやって調べるか # グラフ、新たな1次元dpも考えたが区間スケジューリングがよいのでは N, M = map(int, input().split()) AB = [] for i in range(M): a, b = map(int, input().split()) AB.append((a, b)) AB.sort(key = lambda x:x[1]) #print(AB) count = 0 last = -1 for a, b in AB: if a >= last: count += 1 last = b ans = (N-1)*2 - count print(ans)