結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
|
提出日時 | 2019-10-31 12:54:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 865 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 81,912 KB |
実行使用メモリ | 84,096 KB |
最終ジャッジ日時 | 2024-09-14 22:03:37 |
合計ジャッジ時間 | 3,735 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
from bisect import * n = int(input()) AB = [tuple(map(int, input().split())) for _ in range(n)] AB1, AB2 = AB[:n//2], AB[n//2:] diff1, diff2 = [], [] for i in range(2**len(AB1)): A, B = 0, 0 for j in range(len(AB1)): if (i>>j)&1: A += AB1[j][0] else: B += AB1[j][1] diff1.append(A-B) for i in range(2**len(AB2)): A, B = 0, 0 for j in range(len(AB2)): if (i>>j)&1: A += AB2[j][0] else: B += AB2[j][1] diff2.append(A-B) diff2.sort() ans = 10**18 for diff1_i in diff1: m = bisect_left(diff2, -diff1_i) if m == 0: ans = min(ans, abs(diff1_i+diff2[m])) elif m == len(diff2): ans = min(ans, abs(diff1_i+diff2[m-1])) else: ans = min(ans, abs(diff1_i+diff2[m-1]), abs(diff1_i+diff2[m])) print(ans)