結果

問題 No.1345 Beautiful BINGO
ユーザー gew1fw
提出日時 2025-06-12 18:34:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,956 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 115,948 KB
最終ジャッジ日時 2025-06-12 18:34:43
合計ジャッジ時間 8,958 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

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 = []
        sum_line = 0
        mask = 0
        for j in range(N):
            sum_line += grid[i][j]
            pos = i * N + j
            mask |= 1 << pos
        lines.append((mask, sum_line))
    
    # Columns
    for j in range(N):
        line = []
        sum_line = 0
        mask = 0
        for i in range(N):
            sum_line += grid[i][j]
            pos = i * N + j
            mask |= 1 << pos
        lines.append((mask, sum_line))
    
    # Main diagonal (top-left to bottom-right)
    sum_line = 0
    mask = 0
    for i in range(N):
        j = i
        sum_line += grid[i][j]
        pos = i * N + j
        mask |= 1 << pos
    lines.append((mask, sum_line))
    
    # Anti-diagonal (top-right to bottom-left)
    sum_line = 0
    mask = 0
    for i in range(N):
        j = N - 1 - i
        sum_line += grid[i][j]
        pos = i * N + j
        mask |= 1 << pos
    lines.append((mask, sum_line))
    
    num_lines = len(lines)
    line_masks = [lm[0] for lm in lines]
    line_sums = [lm[1] for lm in lines]
    
    heap = []
    visited = dict()
    
    for i in range(num_lines):
        line_mask = line_masks[i]
        line_sum = line_sums[i]
        covered = 0
        for j in range(num_lines):
            if (line_masks[j] & line_mask) == line_masks[j]:
                covered |= 1 << j
        if covered not in visited or visited[covered] > line_sum:
            heapq.heappush(heap, (line_sum, covered, line_mask))
            visited[covered] = line_sum
    
    while heap:
        current_sum, covered, union_mask = heapq.heappop(heap)
        count = bin(covered).count('1')
        if count >= M:
            print(current_sum)
            return
        if visited.get(covered, float('inf')) < current_sum:
            continue
        for i in range(num_lines):
            new_union_mask = union_mask | line_masks[i]
            new_sum = current_sum
            for j in range(N*N):
                if (line_masks[i] & (1 << j)) and not (union_mask & (1 << j)):
                    row = j // N
                    col = j % N
                    new_sum += grid[row][col]
            new_covered = 0
            for j in range(num_lines):
                if (new_union_mask & line_masks[j]) == line_masks[j]:
                    new_covered |= 1 << j
            if new_covered not in visited or visited.get(new_covered, float('inf')) > new_sum:
                visited[new_covered] = new_sum
                heapq.heappush(heap, (new_sum, new_covered, new_union_mask))
    
    print(-1)

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