結果

問題 No.1345 Beautiful BINGO
ユーザー gew1fw
提出日時 2025-06-12 20:54:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,331 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 85,404 KB
最終ジャッジ日時 2025-06-12 20:58:21
合計ジャッジ時間 6,374 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    M = int(data[idx+1])
    idx +=2
    
    grid = []
    for _ in range(N):
        row = list(map(int, data[idx:idx+N]))
        grid.append(row)
        idx += N
    
    # Generate all lines
    lines = []
    
    # Rows
    for i in range(N):
        squares = [(i, j) for j in range(N)]
        lines.append(squares)
    
    # Columns
    for j in range(N):
        squares = [(i, j) for i in range(N)]
        lines.append(squares)
    
    # Diagonals
    diag1 = [(i, i) for i in range(N)]
    lines.append(diag1)
    
    diag2 = [(i, N-1 -i) for i in range(N)]
    lines.append(diag2)
    
    min_total = float('inf')
    len_lines = len(lines)
    # Iterate over all combinations of M lines
    for selected in itertools.combinations(lines, M):
        # Compute the union of all squares in selected lines
        union = set()
        for line in selected:
            for (i,j) in line:
                union.add((i,j))
        # Sum the A[i][j] for squares in the union
        total = 0
        for (i,j) in union:
            total += grid[i][j]
        if total < min_total:
            min_total = total
    
    print(min_total)

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