結果

問題 No.519 アイドルユニット
ユーザー lam6er
提出日時 2025-03-31 17:28:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 182 ms / 1,000 ms
コード長 1,204 bytes
コンパイル時間 130 ms
コンパイル使用メモリ 82,736 KB
実行使用メモリ 195,968 KB
最終ジャッジ日時 2025-03-31 17:29:46
合計ジャッジ時間 3,574 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

n = int(sys.stdin.readline())
f = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

max_mask = 1 << n
dp = [-1] * max_mask
initial_mask = (1 << n) - 1
dp[initial_mask] = 0

for mask in range(initial_mask, -1, -1):
    current_score = dp[mask]
    if current_score == -1:
        continue
    
    # Find the first available idol (a)
    lsb = mask & -mask
    if lsb == 0:
        continue  # No bits set
    a = (lsb).bit_length() - 1
    
    # Remaining idols after a
    remaining_mask = mask >> (a + 1)
    current_j = a + 1  # Starting position in original mask
    
    while remaining_mask:
        lsb_j = remaining_mask & -remaining_mask
        if lsb_j == 0:
            break
        
        offset = (lsb_j).bit_length() - 1
        j = current_j + offset
        
        if j >= n:
            break  # Out of bounds
        
        # Calculate new mask and score
        new_mask = mask ^ ((1 << a) | (1 << j))
        added_score = f[a][j]
        new_total = current_score + added_score
        
        if new_total > dp[new_mask]:
            dp[new_mask] = new_total
        
        # Move to the next bit
        remaining_mask ^= lsb_j

print(dp[0])
0