結果

問題 No.2094 Symmetry
ユーザー lam6er
提出日時 2025-03-20 18:57:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 2,711 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 123,240 KB
最終ジャッジ日時 2025-03-20 18:58:55
合計ジャッジ時間 7,167 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, K = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(2*N):
        grid.append(sys.stdin.readline().strip())
    C = []
    for _ in range(2*N):
        row = list(map(int, sys.stdin.readline().split()))
        C.append(row)
    
    # Compute initial k and initial_sum
    initial_k = 0
    initial_sum = 0
    for i in range(2*N):
        for j in range(2*N):
            if grid[i][j] == '#':
                initial_sum += C[i][j]
                initial_k += 1
    
    # Precompute for symmetric case
    symmetric_possible = (initial_k % 2 == 0)
    symmetric_max = -float('inf')
    if symmetric_possible:
        pairs = []
        for i in range(2*N):
            for j in range(N):  # Since j ranges from 0 to N-1 for 2N columns (0-based)
                j2 = 2*N - 1 - j  # 0-based symmetric
                if j >= j2:
                    continue  # avoid duplicate
                c1 = C[i][j]
                c2 = C[i][j2]
                pairs.append(c1 + c2)
        x = initial_k // 2
        if len(pairs) < x:
            symmetric_possible = False
        else:
            # Sort in descending order
            pairs.sort(reverse=True)
            selected = pairs[:x]
            sum_selected = sum(selected)
            symmetric_max = sum_selected + K
    
    # Precompute for non-symmetric case
    groupA = []
    groupB = []
    for i in range(2*N):
        for j in range(2*N):
            if grid[i][j] == '.':
                # s=0, delta is C[i][j]
                groupA.append(C[i][j])
            else:
                # s=1, delta is -C[i][j]
                groupB.append(-C[i][j])
    # Sort groupA in descending order
    groupA.sort(reverse=True)
    # Sort groupB in descending order (which is ascending of original C)
    groupB.sort(reverse=True)
    
    # Precompute prefix sums for groupA and groupB
    prefixA = [0]
    for c in groupA:
        prefixA.append(prefixA[-1] + c)
    prefixB = [0]
    for c in groupB:
        prefixB.append(prefixB[-1] + c)
    
    max_delta = -float('inf')
    max_x = min(len(groupA), len(groupB))
    for x in range(0, max_x + 1):
        if x > len(prefixA)-1 or x > len(prefixB)-1:
            continue
        current = prefixA[x] + prefixB[x]
        if current > max_delta:
            max_delta = current
    non_symmetric_sum = initial_sum + max_delta if max_delta != -float('inf') else -float('inf')
    
    # Compare symmetric and non-symmetric
    candidates = []
    if symmetric_possible:
        candidates.append(symmetric_max)
    candidates.append(non_symmetric_sum)
    result = max(candidates)
    print(result)

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