結果

問題 No.2100 [Cherry Alpha C] Two-way Steps
ユーザー 👑 rin204rin204
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 -= 1
y -= 1
X[x].append(y)
Y[y].append(x)
dpu = [-1 << 60] * n
dpd = [-1 << 60] * n
dpu[0] = 0
dpd[0] = 0
for 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 = -1
print(ans)
dpu = [-1 << 60] * n
dpd = [-1 << 60] * n
dpu[-1] = 0
dpd[-1] = 0
for 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 = -1
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0