結果
問題 | No.1345 Beautiful BINGO |
ユーザー |
👑 |
提出日時 | 2022-04-16 17:28:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,094 ms / 2,000 ms |
コード長 | 2,336 bytes |
コンパイル時間 | 890 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 78,124 KB |
最終ジャッジ日時 | 2024-12-25 21:17:46 |
合計ジャッジ時間 | 15,593 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
ソースコード
def popcount(x):x = x - ((x >> 1) & 0x55555555)x = (x & 0x33333333) + ((x >> 2) & 0x33333333)x = (x + (x >> 4)) & 0x0f0f0f0fx += x >> 8x += x >> 16return x & 0x0000003fn, m = map(int, input().split())A = [list(map(int, input().split())) for _ in range(n)]ans = 1 << 30for bit in range(1 << n):pc = popcount(bit)if pc > m or pc + n < m:continuetmp = 0lst = [0] * nfor i in range(n):if bit >> i & 1:for j in range(n):tmp += A[i][j]else:for j in range(n):lst[j] += A[i][j]lst.sort()tmp += sum(lst[:m - pc])ans = min(ans, tmp)x = 0for i in range(n):x += A[i][i]for bit in range(1 << n):pc = popcount(bit) + 1if pc > m or pc + n < m:continuetmp = xlst = [0] * nfor i in range(n):if bit >> i & 1:for j in range(n):if i != j:tmp += A[i][j]else:for j in range(n):if i != j:lst[j] += A[i][j]lst.sort()tmp += sum(lst[:m - pc])ans = min(ans, tmp)x = 0for i in range(n):x += A[i][n - 1 - i]for bit in range(1 << n):pc = popcount(bit) + 1if pc > m or pc + n < m:continuetmp = xlst = [0] * nfor i in range(n):if bit >> i & 1:for j in range(n):if i != n - 1 - j:tmp += A[i][j]else:for j in range(n):if i != n - 1 - j:lst[j] += A[i][j]lst.sort()tmp += sum(lst[:m - pc])ans = min(ans, tmp)x = 0for i in range(n):x += A[i][i]if i != n - 1 - i:x += A[i][n - 1 - i]for bit in range(1 << n):pc = popcount(bit) + 2if pc > m or pc + n < m:continuetmp = xlst = [0] * nfor i in range(n):if bit >> i & 1:for j in range(n):if i != n - 1 - j and i != j:tmp += A[i][j]else:for j in range(n):if i != n - 1 - j and i != j:lst[j] += A[i][j]lst.sort()tmp += sum(lst[:m - pc])ans = min(ans, tmp)print(ans)