結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー |
👑 |
提出日時 | 2022-10-16 16:02:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 392 ms / 2,000 ms |
コード長 | 877 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,076 KB |
実行使用メモリ | 99,700 KB |
最終ジャッジ日時 | 2024-06-27 11:15:25 |
合計ジャッジ時間 | 14,833 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
n, m = map(int, input().split())H = list(map(int, input().split()))X = [[] for _ in range(n)]Y = [[] for _ in range(n)]for _ in range(m):x, y = map(int, input().split())x -= 1y -= 1X[x].append(y)Y[y].append(x)dpu = [-1 << 60] * ndpd = [-1 << 60] * ndpu[0] = 0dpd[0] = 0for y in range(1, n):for x in Y[y]:if H[x] > H[y]:dpd[y] = max(dpd[y], dpd[x], dpu[x])else:dpu[y] = max(dpu[y], dpd[x] + H[y] - H[x])ans = max(dpu[-1], dpd[-1])if ans < 0:ans = -1print(ans)dpu = [-1 << 60] * ndpd = [-1 << 60] * ndpu[-1] = 0dpd[-1] = 0for x in range(n - 2, -1, -1):for y in X[x]:if H[y] > H[x]:dpd[x] = max(dpd[x], dpd[y], dpu[y])else:dpu[x] = max(dpu[x], dpd[y] + H[x] - H[y])ans = max(dpu[0], dpd[0])if ans < 0:ans = -1print(ans)