結果

問題 No.2100 [Cherry Alpha C] Two-way Steps
コンテスト
ユーザー Akijin_007
提出日時 2022-10-14 21:50:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 380 ms / 2,000 ms
コード長 985 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 99,520 KB
最終ジャッジ日時 2024-06-26 13:41:35
合計ジャッジ時間 13,170 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#int(input())
#map(int, input().split())
#list(map(int, input().split()))

N, M = map(int, input().split())
H = list(map(int, input().split()))

toc = [[] for i in range(N)]
toz = [[] for i in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    toc[x-1].append(y-1)
    toz[y-1].append(x-1)

dp1 = [-1] * N
dp2 = [-1] * N

dp1[0] = 0
dp2[0] = 0

for i in range(N-1):
    for x in toc[i]:
        if H[i] > H[x]:
            dp1[x] = max(dp1[i], dp2[i], dp1[x])
        else:
            if dp1[i] != -1:
                dp2[x] = max(dp2[x], dp1[i] + (H[x] - H[i]))

# print(dp1)
# print(dp2)

print(max(dp1[N-1], dp2[N-1]))

dp1 = [-1] * N
dp2 = [-1] * N

dp1[N-1] = 0
dp2[N-1] = 0

for i in range(N-1, 0, -1):
    for x in toz[i]:
        if H[i] > H[x]:
            dp1[x] = max(dp1[i], dp2[i], dp1[x])
        else:
            if dp1[i] != -1:
                dp2[x] = max(dp2[x], dp1[i] + (H[x] - H[i]))

# print(dp1)
# print(dp2)

print(max(dp1[0], dp2[0]))
0