結果

問題 No.1345 Beautiful BINGO
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:06:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,379 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 76,508 KB
最終ジャッジ日時 2025-06-12 16:07:04
合計ジャッジ時間 5,926 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    M = int(input[idx])
    idx +=1

    A = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        idx += N
        A.append(row)
    
    lines = []
    # Rows
    for i in range(N):
        line = []
        for j in range(N):
            line.append((i, j))
        lines.append(line)
    # Columns
    for j in range(N):
        line = []
        for i in range(N):
            line.append((i, j))
        lines.append(line)
    # Diagonals
    if N >=1:
        diag1 = []
        for i in range(N):
            diag1.append((i, i))
        lines.append(diag1)
        diag2 = []
        for i in range(N):
            diag2.append((i, N-1 -i))
        lines.append(diag2)
    
    min_total = float('inf')
    for k in range(M, len(lines)+1):
        if k > len(lines):
            break
        for subset in itertools.combinations(lines, k):
            covered = set()
            for line in subset:
                for cell in line:
                    covered.add(cell)
            total = sum(A[i][j] for i,j in covered)
            if total < min_total:
                min_total = total
        if min_total != float('inf'):
            break
    
    print(min_total)

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