結果
問題 | No.1949 足し算するだけのパズルゲーム(2) |
ユーザー | ygd. |
提出日時 | 2022-05-24 00:04:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 802 ms / 3,000 ms |
コード長 | 1,979 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 102,148 KB |
最終ジャッジ日時 | 2023-10-20 17:49:45 |
合計ジャッジ時間 | 7,240 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,508 KB |
testcase_01 | AC | 38 ms
53,508 KB |
testcase_02 | AC | 39 ms
53,508 KB |
testcase_03 | AC | 39 ms
53,508 KB |
testcase_04 | AC | 39 ms
53,508 KB |
testcase_05 | AC | 39 ms
53,508 KB |
testcase_06 | AC | 40 ms
53,508 KB |
testcase_07 | AC | 413 ms
82,084 KB |
testcase_08 | AC | 72 ms
76,628 KB |
testcase_09 | AC | 307 ms
81,304 KB |
testcase_10 | AC | 368 ms
81,332 KB |
testcase_11 | AC | 373 ms
81,596 KB |
testcase_12 | AC | 383 ms
82,048 KB |
testcase_13 | AC | 415 ms
81,732 KB |
testcase_14 | AC | 498 ms
101,276 KB |
testcase_15 | AC | 494 ms
101,276 KB |
testcase_16 | AC | 66 ms
76,952 KB |
testcase_17 | AC | 802 ms
102,148 KB |
testcase_18 | AC | 65 ms
76,952 KB |
testcase_19 | AC | 39 ms
53,508 KB |
testcase_20 | AC | 40 ms
53,508 KB |
testcase_21 | AC | 41 ms
53,508 KB |
testcase_22 | AC | 574 ms
91,952 KB |
testcase_23 | AC | 40 ms
53,508 KB |
testcase_24 | AC | 284 ms
81,424 KB |
testcase_25 | AC | 390 ms
81,232 KB |
ソースコード
import sys #input = sys.stdin.readline input = sys.stdin.buffer.readline #文字列はダメ #sys.setrecursionlimit(1000000) #import bisect #import itertools #import random from heapq import heapify, heappop, heappush #from collections import defaultdict #from collections import deque #import copy #import math #from functools import lru_cache #@lru_cache(maxsize=None) #MOD = pow(10,9) + 7 #MOD = 998244353 dx = [1,0,-1,0] dy = [0,1,0,-1] #dx8 = [1,1,0,-1,-1,-1,0,1] #dy8 = [0,1,1,1,0,-1,-1,-1] base = 505 def main(): H,W,Y,X = map(int,input().split()); INF = pow(10,18) X -= 1; Y -= 1 A = [list(map(int,input().split())) for _ in range(H)] PQ = [] heappush(PQ,(0,Y*base+X)) ok = [[0]*W for _ in range(H)] power = A[Y][X] while PQ: dummy,idx = heappop(PQ) y = idx//base x = idx%base #print(x,y,A[y][x],"P",power) if ok[y][x] == 1: continue if (y,x) != (Y,X): if power <= A[y][x]: continue else: power += A[y][x] ok[y][x] = 1 for d in range(4): ny = y + dy[d] nx = x + dx[d] if ny < 0 or ny >= H or nx < 0 or nx >= W: continue if ok[ny][nx] == 1: continue #既に倒している。 if A[ny][nx] < power: power += A[ny][nx] ok[ny][nx] = 1 for dd in range(4): nny = ny + dy[dd] nnx = nx + dx[dd] if nny < 0 or nny >= H or nnx < 0 or nnx >= W: continue if ok[nny][nnx] == 1: continue #既に倒している。 heappush(PQ, (A[nny][nnx],nny*base + nnx)) else: heappush(PQ, (A[ny][nx], ny*base + nx)) #print(power) #print(ok) for i in range(H): for j in range(W): if ok[i][j] == 0: print('No') exit() print('Yes') if __name__ == '__main__': main()