結果

問題 No.3697 実力を揃える
コンテスト
ユーザー urectanc
提出日時 2026-09-09 23:20:26
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 105 ms / 5,000 ms
+ 419µs
コード長 1,050 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,770 ms
コンパイル使用メモリ 186,084 KB
実行使用メモリ 18,944 KB
最終ジャッジ日時 2026-09-09 23:21:00
合計ジャッジ時間 7,091 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }

    let (first, second) = a.split_at(n / 2);
    let p = enumerate(&first);
    let q = enumerate(&second);

    let mut ans = i64::MAX;
    for i in 0..=n / 2 {
        let p = &p[i];
        let q = &q[n / 2 - i];

        for &p in p {
            let i = q.partition_point(|&q| p + q < 0);
            if i < q.len() {
                let cand = p + q[i];
                ans = ans.min(cand.abs());
            }

            if i > 0 {
                let cand = p + q[i - 1];
                ans = ans.min(cand.abs());
            }
        }
    }

    println!("{ans}");
}

fn enumerate(a: &[i64]) -> Vec<Vec<i64>> {
    let n = a.len();
    let mut res = vec![vec![]; n + 1];
    for bits in 0usize..1 << n {
        let sum = (0..n)
            .map(|i| if bits >> i & 1 == 0 { a[i] } else { -a[i] })
            .sum::<i64>();
        res[bits.count_ones() as usize].push(sum);
    }
    res.iter_mut().for_each(|v| v.sort_unstable());
    res
}
0