結果
問題 | No.20 砂漠のオアシス |
ユーザー | 6soukiti29 |
提出日時 | 2017-07-26 23:28:58 |
言語 | Nim (2.0.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,804 bytes |
コンパイル時間 | 3,526 ms |
コンパイル使用メモリ | 71,260 KB |
実行使用メモリ | 6,124 KB |
最終ジャッジ日時 | 2023-09-12 13:37:08 |
合計ジャッジ時間 | 4,561 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 3 ms
4,380 KB |
testcase_02 | AC | 3 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,404 KB |
testcase_04 | AC | 4 ms
4,384 KB |
testcase_05 | AC | 18 ms
5,752 KB |
testcase_06 | AC | 17 ms
5,976 KB |
testcase_07 | WA | - |
testcase_08 | AC | 17 ms
6,124 KB |
testcase_09 | AC | 17 ms
5,984 KB |
testcase_10 | AC | 3 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 3 ms
4,376 KB |
testcase_13 | AC | 4 ms
4,440 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 4 ms
4,544 KB |
testcase_18 | WA | - |
testcase_19 | AC | 5 ms
4,552 KB |
testcase_20 | WA | - |
コンパイルメッセージ
/home/judge/data/code/Main.nim(23, 25) Warning: Number of spaces around '<=' is not consistent [Spacing]
ソースコード
import sequtils,strutils type zahyou = tuple[x : int, y : int] type priorityQue[I:static[int];T:tuple] = array[I + 1,T] item = tuple[cost: int,ID : zahyou] proc push[T](A:var priorityQue; b: T;)= const key = 0 A[0][0] += 1 A[A[0][0]] = b # A[0][0]はsize、最大のIndex var index = A[0][0] while index > 1 and A[index][key] > A[index div 2][key]: (A[index],A[index div 2]) = (A[index div 2],A[index]) index = index div 2 proc pop(A: var priorityQue):item = #戻り値を書き換える const key = 0 result = A[1] A[1] = A[A[0][0]] A[A[0][0]] = (0,(0,0)) A[0][0] -= 1 var index = 1 while index * 2 <= A[0][0]: if index * 2 + 1<= A[0][0]: if A[index][key] < A[index * 2][key] and A[index * 2 + 1][key] <= A[index * 2][key]: (A[index],A[index * 2]) = (A[index * 2],A[index]) index = index * 2 elif A[index][key] < A[index * 2 + 1][key]: (A[index],A[index * 2 + 1]) = (A[index * 2 + 1],A[index]) index = index * 2 + 1 else: break elif index * 2 <= A[0][0]: if A[index][key] < A[index * 2][key]: (A[index],A[index * 2]) = (A[index * 2],A[index]) break else: break proc size(A : priorityQue):int= return A[0][0] var N,V,Ox,Oy : int sabaku : array[202,array[202,int]] line : seq[int] D = [[1,0],[0,1],[-1,0],[0,-1]] startcost : seq[seq[int]] gorlcost : seq[seq[int]] p : zahyou r : item (N,V,Ox,Oy) = stdin.readline.split.map(parseInt) for i in 0..201: for j in 0..201: sabaku[i][j] = 1000000 for i in 0..<N: line = stdin.readline.strip.split.map(parseInt) for j in 0..<N: sabaku[i + 1][j + 1] = line[j] for i in 0..1: var S = newSeqWith(N + 2,newSeqWith(N + 2,-1000000)) pq : priorityQue[40000,item] flag = newSeqWith(N + 2,newSeqWith(N + 2,false)) if i == 0: p = (1,1) pq.push((0,p)) S[1][1] = 0 else: p = (N,N) pq.push((-sabaku[N][N],p)) S[N][N] = -sabaku[N][N] while pq.size > 0: r = pq.pop p = r.ID flag[p.y][p.x] = true if S[p.y][p.x] > r.cost: continue for d in D: if S[p.y + d[0]][p.x + d[1]] < r.cost - sabaku[p.y + d[0]][p.x + d[1]]: S[p.y + d[0]][p.x + d[1]] = r.cost - sabaku[p.y + d[0]][p.x + d[1]] pq.push((S[p.y + d[0]][p.x + d[1]],(p.y + d[0],p.x + d[1]))) if i == 0: startcost = S else: gorlcost = S var Vo = V + startcost[Oy][Ox] Vo *= 2 Vo += sabaku[Oy][Ox] if Vo > -gorlcost[Oy][Ox] or -startcost[N][N] < V: echo "YES" else: echo "NO"