提出 #33573629

---

ソースコード 拡げる

use proconio::input;

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

    // Hu--Tucker-based na\"ive algorithm

    let mut res = 0;
    let oo = 10_i64.pow(16);
    let mut single = vec![true; n];
    let mut a: Vec<_> = a.iter().map(|&ai| Some(ai)).collect();
    for _ in 1..n {
        let mut pair = (n, n);
        let mut cost = oo;
        for l in 0..n {
            let al = if let Some(c) = a[l] { c } else { continue };
            for r in l + 1..n {
                let ar = if let Some(c) = a[r] { c } else { continue };
                if cost > al + ar {
                    pair = (l, r);
                    cost = al + ar;
                }
                if single[r] {
                    break;
                }
            }
        }

        let (l, r) = pair;
        res += cost;
        a[l] = Some(cost);
        a[r].take();
        single[l] = false;
        single[r] = false;
    }

    println!("{}", res);
}

提出情報

ジャッジ結果