fn main() { input!{ // 問題数, 選ぶ個数, 美しさ nn: usize, dd: usize, kk: usize, a: [i64; nn], c: [i64; nn], } // DP[問題i個みた][美しさj][選択個数k] = 満足度のmax let mut dp = vec![vec![vec![-INF; dd+1]; kk+1]; nn+1]; dp[0][0][0] = 0; // くばるDP for i in 0..nn { for j in 0..=kk { for k in 0..=dd { // 不可能なところは遷移しない if dp[i][j][k] == -INF { continue; } // 採用しない場合 dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k]); // 採用する場合 if k < dd { let nj = min(j as i64+c[i], kk as i64) as usize; dp[i+1][nj][k+1] = max(dp[i+1][nj][k+1], dp[i][j][k] + a[i]); } } } } if dp[nn][kk][dd] == -INF { println!("No"); } else { println!("{}", dp[nn][kk][dd]); } } // const MOD17: usize = 1000000007; // const MOD93: usize = 998244353; const INF: i64 = 1 << 60; // let dx = vec![!0, 0, 1, 0]; // 上左下右 // let dy = vec![0, !0, 0, 1]; // 上左下右 // let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右 #[allow(unused)] use proconio::{input, marker::Chars, marker::Usize1}; #[allow(unused)] use std::{ mem::swap, cmp::min, cmp::max, cmp::Reverse, collections::HashSet, collections::BTreeSet, collections::HashMap, collections::BTreeMap, collections::BinaryHeap, collections::VecDeque, iter::FromIterator, };