結果

問題 No.1345 Beautiful BINGO
ユーザー lam6er
提出日時 2025-04-15 22:25:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,670 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 81,948 KB
実行使用メモリ 84,192 KB
最終ジャッジ日時 2025-04-15 22:27:12
合計ジャッジ時間 7,983 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    grid = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        idx += N
        grid.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
    diag1 = []
    diag2 = []
    for i in range(N):
        diag1.append((i, i))
        diag2.append((i, N-1 - i))
    lines.append(diag1)
    lines.append(diag2)
    
    min_sum = float('inf')
    
    # Precompute each line's cells and sum
    line_masks = []
    for line in lines:
        s = 0
        covered = set()
        for (i, j) in line:
            s += grid[i][j]
            covered.add((i, j))
        line_masks.append((covered, s))
    
    # Generate all possible subsets of lines with size >= M
    for k in range(M, len(lines)+1):
        for subset in itertools.combinations(range(len(lines)), k):
            covered = set()
            total = 0
            for line_idx in subset:
                cells, s = line_masks[line_idx]
                for cell in cells:
                    if cell not in covered:
                        total += grid[cell[0]][cell[1]]
                        covered.add(cell)
            if total < min_sum:
                min_sum = total
    
    print(min_sum)

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