結果

問題 No.1345 Beautiful BINGO
ユーザー LyricalMaestro
提出日時 2025-07-26 14:28:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,704 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 77,220 KB
最終ジャッジ日時 2025-07-26 14:28:23
合計ジャッジ時間 13,160 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1345



def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(list(map(int, input().split())))

    col_sums = [0] * N
    for w in range(N):
        for h in range(N):
            col_sums[w] += A[h][w]
    
    answer = sum(col_sums) # 全て開けるも解答の一つ
    for col_bit in range(2 ** N - 1):
        row = [0] * N
        m = 0
        ans = 0
        for w in range(N):
            if col_bit & (1 << w) > 0:
                m += 1
                ans += col_sums[w]
            else:
                for h in range(N):
                    row[h] += A[h][w]
        
        # 斜めを考慮しない場合
        rows = row.copy()
        rows.sort()
        ans0 = ans
        if m < M:
            r = M - m
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

        # 斜めを考慮する場合
        # 1. x + 1
        rows = row.copy()
        ans0 = ans
        for i in range(N):
            if col_bit & (1 << i) == 0:
                ans0 += A[i][i]
                rows[i] -= A[i][i]
        m0 = m + 1
        rows.sort()
        if m0 < M:
            r = M - m0
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

        # 2. x - 1
        rows = row.copy()
        ans0 = ans
        for i in range(N):
            if col_bit & (1 << i) == 0:
                ans0 += A[i][N - 1 - i]
                rows[i] -= A[i][N - 1 - i]

        m0 = m + 1
        rows.sort()
        if m0 < M:
            r = M - m0
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

        # 両方
        rows = row.copy()
        ans0 = ans
        for i in range(N):
            x0 = i
            x1 = N - 1 - i
            if col_bit & (1 << i) == 0:
                ans0 += A[i][x0]
                rows[i] -= A[i][x0]
                if x1 != x0:
                    ans0 += A[i][x1]
                    rows[i] -= A[i][x1]
        m0 = m + 2
        rows.sort()
        if m0 < M:
            r = M - m0
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

    print(answer)





            





if __name__ == "__main__":
    main()
0