結果

問題 No.861 ケーキカット
コンテスト
ユーザー H3PO4
提出日時 2022-08-20 12:50:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,112 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 249,732 KB
最終ジャッジ日時 2024-10-09 05:56:01
合計ジャッジ時間 4,953 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

d = deque([1])
cakes = set()
SIZE = 5
C = tuple(tuple(map(int, input().split())) for _ in range(SIZE))
S = sum(sum(x for x in row) for row in C)


def is_connected(v, x, y):
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        xdx = x + dx
        ydy = y + dy
        if not (0 <= xdx < SIZE and 0 <= ydy < SIZE):
            continue
        neighbor_idx = ydy * SIZE + xdx
        if (v >> neighbor_idx) & 1:
            return True
    return False


while d:
    v = d.pop()
    cakes.add(v)
    for x in range(SIZE):
        for y in range(SIZE):
            idx = y * SIZE + x
            if (v >> idx) & 1:
                continue
            w = v | (1 << idx)
            if w in cakes:
                continue
            if is_connected(v, x, y):
                d.append(w)

ans = 10 ** 18
for c in cakes:
    tmp = 0
    for x in range(SIZE):
        for y in range(SIZE):
            idx = y * SIZE + x
            if (c >> idx) & 1:
                tmp += C[x][y]
    tmp_ans = abs(tmp - (S - tmp))
    if ans > tmp_ans:
        ans = tmp_ans
print(ans)
0