結果

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

ソースコード

diff # 

from collections import deque

SIZE = 5
d = deque([1])
cakes = [False] * (1 << (SIZE * SIZE))
C = []
for _ in range(SIZE):
    C.extend(list(map(int, input().split())))
S = sum(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[v] = True
    for x in range(SIZE):
        for y in range(SIZE):
            idx = y * SIZE + x
            if (v >> idx) & 1:
                continue
            w = v | (1 << idx)
            if cakes[w]:
                continue
            if is_connected(v, x, y):
                d.append(w)

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