結果

問題 No.1345 Beautiful BINGO
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:20:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,893 bytes
コンパイル時間 457 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 71,636 KB
最終ジャッジ日時 2025-06-12 13:22:36
合計ジャッジ時間 5,540 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
    
    # Precompute rows, columns, and diagonals
    rows = []
    for i in range(N):
        s = sum(A[i])
        rows.append((s, i))
    rows.sort()  # sorted by sum
    
    cols = []
    for j in range(N):
        s = sum(A[i][j] for i in range(N))
        cols.append((s, j))
    
    main_diag = []
    anti_diag = []
    for i in range(N):
        main_diag.append(A[i][i])
        anti_diag.append(A[i][N-1 - i])
    sum_main = sum(main_diag)
    sum_anti = sum(anti_diag)
    
    min_total = float('inf')
    
    # Iterate over all possible numbers of rows
    for r in range(N+1):
        if r > 0:
            selected_rows = [row[1] for row in rows[:r]]
            sum_r = sum(row[0] for row in rows[:r])
        else:
            selected_rows = []
            sum_r = 0
        
        # Compute adjusted column sums
        adjusted_cols = []
        for j in range(N):
            col_sum = 0
            for i in range(N):
                if i not in selected_rows:
                    col_sum += A[i][j]
            adjusted_cols.append((col_sum, j))
        adjusted_cols.sort()  # sort by adjusted sum
        
        # Iterate over all possible numbers of columns
        for c in range(N+1):
            if c > 0:
                selected_cols = [col[1] for col in adjusted_cols[:c]]
                sum_c = sum(col[0] for col in adjusted_cols[:c])
            else:
                selected_cols = []
                sum_c = 0
            
            # Compute adjusted diagonal sums
            main_sum = 0
            for i in range(N):
                j = i
                if i not in selected_rows and j not in selected_cols:
                    main_sum += A[i][j]
            anti_sum = 0
            for i in range(N):
                j = N-1 - i
                if i not in selected_rows and j not in selected_cols:
                    anti_sum += A[i][j]
            
            diag_sums = [(main_sum, 0), (anti_sum, 1)]
            diag_sums.sort()  # sort by sum
            
            # Check d=0,1,2
            for d in range(3):
                total_d = 0
                for k in range(d):
                    if k < len(diag_sums):
                        total_d += diag_sums[k][0]
                total = sum_r + sum_c + total_d
                if (r + c + d) >= M and total < min_total:
                    min_total = total
    
    # Check cases where we select only diagonals
    # Also consider combinations without rows or columns
    # But the above loops should have covered all possibilities
    
    print(min_total)

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