結果

問題 No.2100 [Cherry Alpha C] Two-way Steps
ユーザー ntudantuda
提出日時 2022-10-19 21:53:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,441 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 86,868 KB
実行使用メモリ 121,644 KB
最終ジャッジ日時 2023-09-12 09:38:59
合計ジャッジ時間 19,694 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 73 ms
71,160 KB
testcase_01 AC 73 ms
71,400 KB
testcase_02 AC 73 ms
71,316 KB
testcase_03 AC 72 ms
71,212 KB
testcase_04 AC 352 ms
105,672 KB
testcase_05 AC 296 ms
101,988 KB
testcase_06 AC 165 ms
82,716 KB
testcase_07 AC 175 ms
85,108 KB
testcase_08 AC 323 ms
109,404 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 202 ms
92,676 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 241 ms
96,092 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 426 ms
121,164 KB
testcase_26 WA -
testcase_27 AC 401 ms
121,396 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 262 ms
96,872 KB
testcase_40 AC 261 ms
96,808 KB
testcase_41 AC 262 ms
97,048 KB
testcase_42 AC 263 ms
96,692 KB
testcase_43 AC 266 ms
96,992 KB
testcase_44 AC 256 ms
119,376 KB
testcase_45 AC 257 ms
119,632 KB
testcase_46 AC 234 ms
104,356 KB
testcase_47 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
H = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(M)]
# dp[i][j]:= 足場iにいてその前の移動が昇り:1,下り:0のときの登った回数の最大値
E = [[] for _ in range(N)]
for x, y in XY:
    E[x - 1].append(y - 1)
dp = [[-10 ** 12, -10 ** 12] for _ in range(N)]
for x in range(N - 1):
    for y in E[x]:
        hx = H[x]
        hy = H[y]
        if x == 0:
            if hx < hy:
                dp[y][1] = max(dp[y][1], max(dp[x][0], dp[x][1], 0) + hy - hx)
            else:
                dp[y][0] = max(dp[y][0], dp[x][0], dp[x][1], 0)
        else:
            if hx < hy:
                dp[y][1] = max(dp[y][1], dp[x][0] + hy - hx)
            else:
                dp[y][0] = max(dp[y][0], dp[x][1])
ans = []
ans.append(max(dp[N - 1]))
E = [[] for _ in range(N)]
for x, y in XY:
    E[y - 1].append(x - 1)
dp = [-10 ** 12] * N
for y in reversed(range(1, N)):
    for x in E[y]:
        hx = H[x]
        hy = H[y]
        if y == N - 1:
            if hx > hy:
                dp[x] = max(dp[x], max(dp[y], 0) + hx - hy)
            else:
                dp[x] = max(dp[x], dp[y], 0)
        else:
            if hx > hy:
                dp[x] = max(dp[x], dp[y] + hx - hy)
            else:
                dp[x] = max(dp[x], dp[y])
ans.append(dp[0])
for i in range(2):
    if ans[i] < 0:
        print(-1)
    else:
        print(ans[i])
0