結果

問題 No.952 危険な火薬庫
コンテスト
ユーザー 37kt
提出日時 2025-03-20 09:38:40
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 436 ms / 2,000 ms
コード長 2,180 bytes
コンパイル時間 13,257 ms
コンパイル使用メモリ 402,800 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-20 09:38:58
合計ジャッジ時間 18,026 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

pub use __cargo_equip::prelude::*;

use monotone_minima::monotone_minima;
use proconio::{fastout, input};

const INF: i64 = 1 << 60;

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut b = vec![0; n + 1];
    for i in 0..n {
        b[i + 1] = b[i] + a[i];
    }

    let mut dp = vec![INF; n + 2];
    dp[0] = 0;

    // ループ 1 回ごとに開けないドアを 1 つ選ぶ
    let mut res = vec![INF; n + 1];
    for k in 1..=n {
        let f = |i: usize, j: usize| {
            if i > j {
                dp[j] + (b[i - 1] - b[j]).pow(2)
            } else {
                INF
            }
        };
        let select = |i, j, k| f(i, j) > f(i, k);
        let argmin = monotone_minima(n + 2, n + 2, select);
        dp = (0..n + 2).map(|i| f(i, argmin[i])).collect();
        res[n + 1 - k] = dp[n + 1];
    }

    for i in 1..=n {
        println!("{}", res[i]);
    }
}

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

///  # Bundled libraries
/// 
///  - `monotone_minima 0.1.0 (path+██████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::monotone_minima`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod monotone_minima {pub fn monotone_minima(h:usize,w:usize,mut select:impl FnMut(usize,usize,usize)->bool,)->Vec<usize>{let mut argmin=vec![0;h];dfs(0,h,0,w,&mut select,&mut argmin);argmin}fn dfs(il:usize,ir:usize,jl:usize,jr:usize,select:&mut impl FnMut(usize,usize,usize)->bool,argmin:&mut[usize],){if il>=ir{return;}let im=(il+ir)/2;argmin[im]=jl;for j in jl+1..jr{if select(im,argmin[im],j){argmin[im]=j;}}dfs(il,im,jl,argmin[im]+1,select,argmin);dfs(im+1,ir,argmin[im],jr,select,argmin);}}
    }

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

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

    mod preludes {
        pub mod monotone_minima {}
    }
}
0