結果
問題 | No.3014 岩井満足性問題 |
ユーザー |
|
提出日時 | 2025-01-25 15:50:21 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 440 ms / 3,000 ms |
コード長 | 1,450 bytes |
コンパイル時間 | 24,388 ms |
コンパイル使用メモリ | 378,112 KB |
実行使用メモリ | 6,016 KB |
最終ジャッジ日時 | 2025-01-25 23:48:47 |
合計ジャッジ時間 | 27,426 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
fn main() {input!{// 問題数, 選ぶ個数, 美しさnn: usize, dd: usize, kk: usize,a: [i64; nn],c: [i64; nn],}// DP[美しさj][選択個数k] = 満足度のmaxlet mut now_dp = vec![vec![-INF; dd+1]; kk+1];now_dp[0][0] = 0;// くばるDPfor i in 0..nn {let mut next_dp = vec![vec![-INF; dd+1]; kk+1];for j in 0..=kk {for k in 0..=dd {// 不可能なところからは遷移しないif now_dp[j][k] == -INF { continue; }// 採用しない場合next_dp[j][k] = max(next_dp[j][k], now_dp[j][k]);// 採用する場合if k < dd {let nj = min(j as i64+c[i], kk as i64) as usize;next_dp[nj][k+1] = max(next_dp[nj][k+1], now_dp[j][k] + a[i]);}}}swap(&mut now_dp, &mut next_dp);}if now_dp[kk][dd] == -INF {println!("No");}else {println!("{}", now_dp[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,};