結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
|
提出日時 | 2024-02-19 22:12:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 322 ms / 2,000 ms |
コード長 | 725 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 109,204 KB |
最終ジャッジ日時 | 2024-09-29 02:08:32 |
合計ジャッジ時間 | 6,497 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import sysfrom itertools import permutationsfrom heapq import heappop,heappushfrom collections import dequeimport randomimport bisectinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())H,W = mi()A = [li() for i in range(H)]INF = 10**9dp = [[-INF]*W for i in range(H)]idx = [(i,j) for i in range(H) for j in range(W)]idx.sort(key=lambda x:A[x[0]][x[1]])for (i,j) in idx[::-1]:dp[i][j] = 1for dx,dy in [(-1,0),(0,1),(1,0),(0,-1)]:ni,nj = i+dx,j+dyif 0 <= ni < H and 0 <= nj < W and dp[ni][nj]!=-INF and A[ni][nj] > A[i][j]:dp[i][j] = max(dp[i][j],dp[ni][nj]+1)res = max(max(dp[i]) for i in range(H))print(res)