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)) }