結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
![]() |
提出日時 | 2020-03-18 04:45:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 725 bytes |
コンパイル時間 | 960 ms |
コンパイル使用メモリ | 82,536 KB |
実行使用メモリ | 88,772 KB |
最終ジャッジ日時 | 2024-12-14 01:22:43 |
合計ジャッジ時間 | 3,830 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
n = int(input()) A = [0]*n B = [0]*n for i in range(n): a, b = map(int, input().split()) A[i] = a B[i] = b p = n//2 q = n-p A1 = A[0:p] A2 = A[p:n] B1 = B[0:p] B2 = B[p:n] D1 = [] D2 = [] for i in range(2**p): a = 0 b = 0 for j in range(p): if (i >> j) & 1: a += A1[j] else: b += B1[j] D1.append(a-b) for i in range(2**q): a = 0 b = 0 for j in range(q): if (i >> j) & 1: a += A2[j] else: b += B2[j] D2.append(a-b) D2.sort() D2 = [-10**18] + D2 + [10**18] import bisect ans = 10**18 for d in D1: id = bisect.bisect_right(D2, -d) ans = min(ans, min(abs(D2[id-1]+d), abs(D2[id]+d))) print(ans)