結果
問題 | No.1345 Beautiful BINGO |
ユーザー |
![]() |
提出日時 | 2021-01-16 13:40:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,658 ms / 2,000 ms |
コード長 | 1,059 bytes |
コンパイル時間 | 473 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 79,588 KB |
最終ジャッジ日時 | 2024-12-06 17:45:15 |
合計ジャッジ時間 | 32,511 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
ソースコード
""" bitdpではだめ 斜めは4通り試せばよいか フローで解けないか…? 貪欲…? 最後の1方向は貪欲でおk あ、 2**18 * 貪欲 """ from sys import stdin N,M = map(int,stdin.readline().split()) A = [] ans = float("inf") for i in range(N): A.append(list(map(int,stdin.readline().split()))) for i in range(2**(N+2)): B = [[A[i][j] for j in range(N)] for i in range(N)] rem = M tmp = 0 for y in range(N): if 2**y & i > 0: rem -= 1 for x in range(N): tmp += B[x][y] B[x][y] = 0 y = N if 2**y & i > 0: rem -= 1 for k in range(N): tmp += B[k][k] B[k][k] = 0 y = N+1 if 2**y & i > 0: rem -= 1 for k in range(N): tmp += B[k][N-k-1] B[k][N-k-1] = 0 if rem < 0: ans = min(ans,tmp) else: lis = [sum(B[j]) for j in range(N)] lis.sort() tmp += sum(lis[:rem]) ans = min(ans,tmp) print (ans)