結果

問題 No.861 ケーキカット
ユーザー lam6er
提出日時 2025-03-31 17:54:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,938 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 63,292 KB
最終ジャッジ日時 2025-03-31 17:56:06
合計ジャッジ時間 2,207 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

def main():
    grid = []
    for _ in range(5):
        grid.append(list(map(int, sys.stdin.readline().split())))
    total = sum(sum(row) for row in grid)
    
    # Precompute all connected regions
    regions = []
    # For each possible starting cell
    for i in range(5):
        for j in range(5):
            visited = [[False]*5 for _ in range(5)]
            q = [(i, j)]
            visited[i][j] = True
            sum_val = grid[i][j]
            cells = [(i, j)]
            for (x, y) in q:
                for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    nx, ny = x + dx, y + dy
                    if 0<=nx<5 and 0<=ny<5 and not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx, ny))
                        sum_val += grid[nx][ny]
                        cells.append((nx, ny))
            regions.append((frozenset(cells), sum_val))
    
    # Deduplicate regions and filter out subsets
    unique_regions = {}
    for r in regions:
        key = tuple(sorted(r[0]))
        if key not in unique_regions:
            unique_regions[key] = r[1]
    regions = [(set(k), v) for k, v in unique_regions.items()]
    
    # Now check all possible pairs of regions (A1, A2)
    min_diff = float('inf')
    len_regions = len(regions)
    
    for i in range(len_regions):
        A1_set, A1_sum = regions[i]
        for j in range(i + 1, len_regions):
            A2_set, A2_sum = regions[j]
            if A1_set.isdisjoint(A2_set):
                A_total = A1_sum + A2_sum
                B_total = total - A_total
                current_diff = abs(A_total - B_total)
                if current_diff < min_diff:
                    min_diff = current_diff
                if min_diff == 0:
                    print(0)
                    return
    
    print(min_diff)

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