結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
|
提出日時 | 2025-02-28 16:23:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 1,107 bytes |
コンパイル時間 | 379 ms |
コンパイル使用メモリ | 82,840 KB |
実行使用メモリ | 84,568 KB |
最終ジャッジ日時 | 2025-02-28 16:23:39 |
合計ジャッジ時間 | 4,200 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
import bisect N = int(input()) satis = [tuple(map(int, input().split())) for _ in range(N)] half = N // 2 left = satis[:half] right = satis[half:] right_sum = [] left_sum = [] # 左半分の全組み合わせを計算 for i in range(2**len(left)): R, L = 0, 0 for j in range(len(left)): if (i >> j) & 1: R += left[j][0] # 赤側 else: L += left[j][1] # 青側 left_sum.append(R - L) # 右半分の全組み合わせを計算 for i in range(2**len(right)): R, L = 0, 0 for j in range(len(right)): if (i >> j) & 1: R += right[j][0] # 赤側 else: L += right[j][1] # 青側 right_sum.append(R - L) right_sum.sort() # bisectを使うためソート # 最小差分を求める ans = float('inf') for x in left_sum: pos = bisect.bisect_left(right_sum, -x) # 取得した位置とその前後を確認(範囲チェック付き) if pos < len(right_sum): ans = min(ans, abs(x + right_sum[pos])) if pos > 0: ans = min(ans, abs(x + right_sum[pos - 1])) print(ans)