結果

問題 No.545 ママの大事な二人の子供
コンテスト
ユーザー yuushi narazaki
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0