結果

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

ソースコード

diff # 

n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

half = n // 2
group1 = items[:half]
group2 = items[half:]

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

s1 = generate_diffs(group1)
s2 = generate_diffs(group2)
s2.sort()

min_diff = float('inf')

for s in s1:
    target = -s
    left, right = 0, len(s2) - 1
    best = None
    while left <= right:
        mid = (left + right) // 2
        if s2[mid] == target:
            best = mid
            break
        elif s2[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    candidates = []
    if best is not None:
        candidates.append(s2[best])
    else:
        if left < len(s2):
            candidates.append(s2[left])
        if right >= 0:
            candidates.append(s2[right])
    for delta in (-1, 0, 1):
        if 0 <= left + delta < len(s2):
            candidates.append(s2[left + delta])
        if 0 <= right + delta < len(s2):
            candidates.append(s2[right + delta])
    candidates = list(set(candidates))
    for c in candidates:
        current = abs(s + c)
        if current < min_diff:
            min_diff = current

print(min_diff)
0