結果
問題 | No.861 ケーキカット |
ユーザー |
|
提出日時 | 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 |
ソースコード
from collections import dequeSIZE = 5d = 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 + dxydy = y + dyif not (0 <= xdx < SIZE and 0 <= ydy < SIZE):continueneighbor_idx = ydy * SIZE + xdxif (v >> neighbor_idx) & 1:return Truereturn Falsewhile d:v = d.pop()cakes[v] = Truefor x in range(SIZE):for y in range(SIZE):idx = y * SIZE + xif (v >> idx) & 1:continuew = v | (1 << idx)if cakes[w]:continueif is_connected(v, x, y):d.append(w)ans = 10 ** 18for c, flag in enumerate(cakes):if flag:tmp = 0for idx in range(SIZE * SIZE):if (c >> idx) & 1:tmp += C[idx]ans = min(ans, abs(tmp - (S - tmp)))print(ans)