結果

問題 No.545 ママの大事な二人の子供
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:05:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 1,015 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 108,100 KB
最終ジャッジ日時 2025-03-20 21:06:07
合計ジャッジ時間 3,299 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n = int(input())
items = []
for _ in range(n):
    a, b = map(int, input().split())
    items.append((a, b))

# 分割物品为前半和后半
m = n // 2
first_part = items[:m]
second_part = items[m:]

def get_diffs(items_part):
    diffs = {0}
    for a, b in items_part:
        new_diffs = set()
        for d in diffs:
            new_diffs.add(d + a)
            new_diffs.add(d - b)
        diffs = new_diffs
    return diffs

s1 = get_diffs(first_part)
s2 = get_diffs(second_part)

s2_sorted = sorted(s2)
min_abs = float('inf')

for d1 in s1:
    target = -d1
    pos = bisect.bisect_left(s2_sorted, target)
    # 检查pos和pos-1的位置
    if pos < len(s2_sorted):
        candidate = s2_sorted[pos]
        current_abs = abs(d1 + candidate)
        if current_abs < min_abs:
            min_abs = current_abs
    if pos > 0:
        candidate = s2_sorted[pos-1]
        current_abs = abs(d1 + candidate)
        if current_abs < min_abs:
            min_abs = current_abs

print(min_abs)
0