結果

問題 No.2100 [Cherry Alpha C] Two-way Steps
コンテスト
ユーザー rin204
提出日時 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)
0