結果

問題 No.1345 Beautiful BINGO
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:54:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,386 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 196,360 KB
最終ジャッジ日時 2025-03-31 17:56:42
合計ジャッジ時間 7,387 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    A = []
    for _ in range(N):
        A.append(list(map(int, sys.stdin.readline().split())))
    
    lines = []
    # Rows (0-based)
    for i in range(N):
        row = [(i, j) for j in range(N)]
        lines.append(row)
    # Columns
    for j in range(N):
        col = [(i, j) for i in range(N)]
        lines.append(col)
    # Diagonals
    diag1 = [(i, i) for i in range(N)]
    diag2 = [(i, N-1 - i) for i in range(N)]
    lines.append(diag1)
    lines.append(diag2)
    
    # Precompute mask and sum for each line
    lines_info = []
    for line in lines:
        mask = 0
        sum_val = 0
        for (i, j) in line:
            sum_val += A[i][j]
            bit = i * N + j
            mask |= 1 << bit
        lines_info.append({'mask': mask, 'sum_val': sum_val, 'cells': line})
    
    # Priority queue: (current_sum, current_mask)
    heap = []
    heapq.heappush(heap, (0, 0))
    
    # Dictionary to track the minimal sum for each mask
    min_sum = {0: 0}
    found = False
    
    while heap:
        current_sum, current_mask = heapq.heappop(heap)
        # Check if this is the best sum for current_mask
        if min_sum.get(current_mask, float('inf')) < current_sum:
            continue
        
        # Check number of covered lines
        count = 0
        for info in lines_info:
            line_mask = info['mask']
            if (current_mask & line_mask) == line_mask:
                count += 1
        if count >= M:
            print(current_sum)
            found = True
            break
        
        # Explore adding each line
        for info in lines_info:
            line_mask = info['mask']
            new_mask = current_mask | line_mask
            additional_sum = 0
            for (i, j) in info['cells']:
                bit = i * N + j
                if not (current_mask & (1 << bit)):
                    additional_sum += A[i][j]
            new_sum = current_sum + additional_sum
            # Update if this new_mask has a lower sum
            if new_sum < min_sum.get(new_mask, float('inf')):
                min_sum[new_mask] = new_sum
                heapq.heappush(heap, (new_sum, new_mask))
    
    if not found:
        print(-1)  # Should not happen per problem statement

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