AtCoder Beginner Contest 327 E

https://atcoder.jp/contests/abc327/tasks/abc327_e

単なるDPで、を選ぶか選ばないかのときに同じkでRの第1項を記憶しておけばよいです。

// Maximize Rating
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> Vec<f64> {
    let _N: usize = read();
    let P: Vec<f64> = read_vec();
    P
}

fn update_dp(p: f64, dp: Vec<f64>) -> Vec<f64> {
    let K = dp.len();
    let mut new_dp: Vec<f64> = dp.to_vec();
    new_dp.push(0.0);
    for k in 0..K {
        let num = dp[k] * 0.9 + p;
        new_dp[k+1] = if num > new_dp[k+1] { num } else { new_dp[k+1] };
    }
    new_dp
}

fn F(P: Vec<f64>) -> f64 {
    let N = P.len();
    let mut dp: Vec<f64> = vec![0.0];
    for p in P.into_iter() {
        dp = update_dp(p, dp)
    }
    
    let mut dens: Vec<f64> = vec![0.0; N+1];
    for k in 1..N+1 {
        dens[k] = dens[k-1] * 0.9 + 1.0
    }
    (1..N+1).map(|k| dp[k] / dens[k] - 1200.0 / (k as f64).sqrt()).
                max_by(|a, b| a.partial_cmp(b).unwrap()).unwrap()
}

fn main() {
    let P = read_input();
    println!("{}", F(P))
}