結果
問題 | 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 stdinN,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 = Mtmp = 0for y in range(N):if 2**y & i > 0:rem -= 1for x in range(N):tmp += B[x][y]B[x][y] = 0y = Nif 2**y & i > 0:rem -= 1for k in range(N):tmp += B[k][k]B[k][k] = 0y = N+1if 2**y & i > 0:rem -= 1for k in range(N):tmp += B[k][N-k-1]B[k][N-k-1] = 0if 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)