結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー |
|
提出日時 | 2022-10-14 21:57:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 484 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 107,908 KB |
最終ジャッジ日時 | 2024-06-26 13:54:41 |
合計ジャッジ時間 | 14,944 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
N,M = map(int,input().split())H = list(map(int,input().split()))G = [[] for _ in range(N)]for _ in range(M):x,y = map(int,input().split())x -= 1y -= 1G[x].append(y)G[y].append(x)dp = [[-1] * 2 for _ in range(N)]dp[0][0] = 0dp[0][1] = 0for i in range(N):for x in G[i]:if x < i:continueif H[x] > H[i]:if dp[i][0] != -1:dp[x][1] = max(dp[x][1],dp[i][0] + H[x] - H[i])else:dp[x][0] = max(dp[x][0],max(dp[i]))dp2 = [[-1] * 2 for _ in range(N)]dp2[-1][0] = 0dp2[-1][1] = 0for i in range(N - 1,-1,-1):for x in G[i]:if x > i:continueif H[x] > H[i]:if dp2[i][0] != -1:dp2[x][1] = max(dp2[x][1],dp2[i][0] + H[x] - H[i])else:dp2[x][0] = max(dp2[x][0],max(dp2[i]))print(max(dp[-1]))print(max(dp2[0]))