結果

問題 No.705 ゴミ拾い Hard
コンテスト
ユーザー 37kt
提出日時 2025-03-20 12:29:12
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 80 ms / 1,500 ms
コード長 1,958 bytes
コンパイル時間 29,071 ms
コンパイル使用メモリ 402,396 KB
実行使用メモリ 21,740 KB
最終ジャッジ日時 2025-03-20 12:29:44
合計ジャッジ時間 15,864 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

// verification-helper: PROBLEM https://yukicoder.me/problems/no/705

pub use __cargo_equip::prelude::*;

use larsch_simple::larsch;
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [i64; n],
        x: [i64; n],
        y: [i64; n],
    }
    let cube = |x: i64| x.abs().pow(3);
    let w = |j, i| cube(a[i - 1] - x[j]) + cube(y[j]);
    let f = |i, j, &x: &i64| x + w(j, i);
    let min = larsch(n, f, 0);
    let res = min[n].0;
    println!("{}", res);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `larsch_simple 0.1.0 (path+████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::larsch_simple`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod larsch_simple {pub fn larsch<T:PartialOrd>(n:usize,mut f:impl FnMut(usize,usize,&T)->T,init:T,)->Vec<(T,usize)>{let mut min=(0..n+1).map(|_|(None,0)).collect::<Vec<_>>();min[0]=(Some(init),0);check(n,0,&mut f,&mut min);solve(0,n,&mut f,&mut min);min.into_iter().map(|(x,j)|(x.unwrap(),j)).collect()}fn check<T:PartialOrd>(i:usize,j:usize,f:&mut impl FnMut(usize,usize,&T)->T,min:&mut[(Option<T>,usize)],){let x=f(i,j,min[j].0.as_ref().unwrap());if min[i].0.is_none()||min[i].0.as_ref().unwrap()>&x{min[i]=(Some(x),j);}}fn solve<T:PartialOrd>(l:usize,r:usize,f:&mut impl FnMut(usize,usize,&T)->T,min:&mut[(Option<T>,usize)],){if l+1>=r{return;}let m=(l+r)/2;for j in min[l].1..=min[r].1{check(m,j,f,min);}solve(l,m,f,min);for j in l+1..=m{check(r,j,f,min);}solve(m,r,f,min);}}
    }

    pub(crate) mod macros {
        pub mod larsch_simple {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod larsch_simple {}
    }
}
0