結果
問題 | No.1598 4×4 Grid |
ユーザー | aaaaaaaaaa2230 |
提出日時 | 2021-07-14 22:53:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,548 ms / 4,000 ms |
コード長 | 719 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 87,272 KB |
実行使用メモリ | 307,904 KB |
最終ジャッジ日時 | 2023-09-17 01:23:10 |
合計ジャッジ時間 | 39,917 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3,531 ms
307,856 KB |
testcase_01 | AC | 3,536 ms
307,700 KB |
testcase_02 | AC | 3,548 ms
307,840 KB |
testcase_03 | AC | 3,543 ms
307,600 KB |
testcase_04 | AC | 3,536 ms
307,904 KB |
testcase_05 | AC | 3,525 ms
307,732 KB |
testcase_06 | AC | 3,525 ms
307,736 KB |
testcase_07 | AC | 3,533 ms
307,692 KB |
testcase_08 | AC | 3,529 ms
307,836 KB |
testcase_09 | AC | 3,524 ms
307,600 KB |
ソースコード
k = int(input()) M = 216 dp = [[0]*(2*M+5) for i in range(1<<16)] dp[0][0] = 1 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] print(dp[-1][k])