結果
問題 | No.1598 4×4 Grid |
ユーザー |
|
提出日時 | 2021-07-14 22:51:48 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 761 bytes |
コンパイル時間 | 141 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 848,316 KB |
最終ジャッジ日時 | 2024-07-03 23:33:04 |
合計ジャッジ時間 | 3,656 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | MLE * 1 -- * 6 |
ソースコード
k = int(input()) M = 216*4 dp = [[0]*(2*M+5) for i in range(1<<16)] dp[0][0] = 1 mi = 0 for i in range(1<<16): for j in range(-M,M+1): if dp[i][j] == 0: continue b = bin(i).count("1") for c in range(16): if i >> c & 1: continue x,y = divmod(c,4) count = 0 for dx,dy in ((-1,0),(0,-1),(0,1),(1,0)): nx = x+dx ny = y+dy if nx < 0 or ny < 0 or nx > 3 or ny > 3: continue if i >> (nx*4+ny) & 1: count += b+1 else: count -= b+1 dp[i|1<<c][count+j] += dp[i][j] mi = min(mi,count+j) print(dp[-1][k])