結果

問題 No.2639 Longest Increasing Walk
ユーザー LyricalMaestro
提出日時 2025-04-12 17:29:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 469 ms / 2,000 ms
コード長 1,120 bytes
コンパイル時間 491 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 138,192 KB
最終ジャッジ日時 2025-04-12 17:30:06
合計ジャッジ時間 8,966 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2639

DIRECTIONS = ((-1, 0), (1, 0), (0, 1), (0, -1))

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))

    a_map = {}
    for h in range(H):
        for w in range(W):
            a = A[h][w]
            if a not in a_map:
                a_map[a] = []
            a_map[a].append((h, w))
    a_array = [(a, array) for a, array in a_map.items()]
    a_array.sort(key=lambda x : x[0])

    dp = [[-10] * W for _ in range(H)]
    for _, array in a_array:
        ans_arrays = []
        for h, w in array:
            ans = 1

            for dh, dw in DIRECTIONS:
                new_h = dh + h
                new_w = dw + w
                if 0 <= new_h < H and 0 <= new_w < W:
                    ans = max(ans, dp[new_h][new_w] + 1)
            ans_arrays.append((h, w, ans))
        
        for h, w, v in ans_arrays:
            dp[h][w] = v
    
    answer = 0
    for h in range(H):
        answer = max(max(dp[h]), answer )
    print(answer)
    





if __name__ == "__main__":
    main()
0