AtCoder Beginner Contest 267 D

https://atcoder.jp/contests/abc267/tasks/abc267_d

各Aに対して部分列の長さごとに最大値を求めればよいです。

// Index × A(Not Continuous ver.)
#![allow(non_snake_case)]

use std::cmp::{min, max};


//////////////////// 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() -> (usize, Vec<i64>) {
    let v = read_vec();
    let M: usize = v[1];
    let A: Vec<i64> = read_vec();
    (M, A)
}

fn update(a: &i64, i: usize, dp: Vec<i64>) -> Vec<i64> {
    let mut new_dp = dp.to_vec();
    for j in 0..(min(i+1, dp.len()-1)) {
        let val = dp[j] + a * ((j+1) as i64);
        new_dp[j+1] = if j == i { val } else { max(val, dp[j+1]) }
    }
    new_dp
}

fn f(M: usize, A: Vec<i64>) -> i64 {
    let mut dp: Vec<i64> = (0..(M+1)).map(|_| 0).collect();
    for (i, a) in A.iter().enumerate() {
        dp = update(a, i, dp);
    }
    dp[M]
}

fn main() {
    let (M, A) = read_input();
    println!("{}", f(M, A))
}