結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | H3PO4 |
提出日時 | 2020-09-17 09:47:45 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 462 ms / 2,000 ms |
コード長 | 813 bytes |
コンパイル時間 | 312 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 17,368 KB |
最終ジャッジ日時 | 2024-06-22 06:26:18 |
合計ジャッジ時間 | 5,828 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import itertoolsimport bisectN = int(input())AB = [tuple(map(int, input().split())) for _ in range(N)]# 全列挙def enum(X):res = []for t in itertools.product((0, 1), repeat=len(X)):diff = 0for i, x in enumerate(t):if x:diff += X[i][0]else:diff -= X[i][1]res.append(diff)res.sort()return resif N <= 2:print(abs(min(enum(AB), key=abs)))exit()# 半分全列挙first = enum(AB[:N // 2])second = enum(AB[N // 2:])ans = float('inf')for x in first:idx = bisect.bisect(second, -x)tmp = float('inf')if idx < len(second):tmp = min(tmp, abs(x + second[idx]))if 0 <= idx - 1:tmp = min(tmp, abs(x + second[idx - 1]))ans = min(ans, tmp)print(ans)