結果
問題 | No.20 砂漠のオアシス |
ユーザー | titia |
提出日時 | 2021-11-07 01:42:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 291 ms / 5,000 ms |
コード長 | 1,017 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 13,184 KB |
最終ジャッジ日時 | 2024-11-08 01:33:23 |
合計ジャッジ時間 | 2,809 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import heapqN,V,cx,cy=map(int,input().split())MAP=[list(map(int,input().split())) for i in range(N)]cx-=1cy-=1DP1=[[0]*N for i in range(N)]DP2=[[0]*N for i in range(N)]DP1[0][0]=VQ=[(-V,0,0,1)]while Q:hp,x,y,c=heapq.heappop(Q)hp=-hpif c==1:for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:if 0<=z<N and 0<=w<N:if DP1[z][w]<hp-MAP[z][w]:DP1[z][w]=hp-MAP[z][w]heapq.heappush(Q,(-DP1[z][w],z,w,1))if z==cy and w==cx and DP2[z][w]<(hp-MAP[z][w])*2:DP2[z][w]=(hp-MAP[z][w])*2heapq.heappush(Q,(-DP2[z][w],z,w,2))else:for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:if 0<=z<N and 0<=w<N:if DP2[z][w]<hp-MAP[z][w]:DP2[z][w]=hp-MAP[z][w]heapq.heappush(Q,(-DP2[z][w],z,w,2))if DP1[N-1][N-1]>0 or DP2[N-1][N-1]>0:print("YES")else:print("NO")