結果
問題 |
No.3076 Goodstuff Deck Builder
|
ユーザー |
|
提出日時 | 2025-03-28 22:56:00 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 326 ms / 3,000 ms |
コード長 | 2,068 bytes |
コンパイル時間 | 13,364 ms |
コンパイル使用メモリ | 406,912 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-28 22:56:31 |
合計ジャッジ時間 | 19,121 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
use std::cmp::Reverse; use proconio::input; // コストが正のカードは高々9枚しか使用できない const MAX_NUM_CARDS: usize = 9; fn main() { input! { (n, m): (usize, usize), cd: [(usize, usize); n], } let mut costless_damage = 0_usize; let mut cards = vec![]; for &(c, d) in &cd { if c == 0 { costless_damage += d; } else { cards.push(Card { cost: c, damage: d }); } } cards.sort_unstable_by_key(|card| Reverse(card.cost)); // dp[i][j]: i枚使用してコストの合計がjのときの合計ダメージ let mut dp = vec![vec![None::<usize>; m + 1]; MAX_NUM_CARDS + 1]; dp[0][0] = Some(0); for &card in &cards { let mut next_dp = dp.clone(); for num_card in 1..=MAX_NUM_CARDS { let raised_cost = card.cost << (num_card - 1); for sum_cost in raised_cost..=m { if let Some(prev_sum_damage) = dp[num_card - 1][sum_cost - raised_cost] { chmax_for_option( &mut next_dp[num_card][sum_cost], prev_sum_damage + card.damage, ); } } } dp = next_dp; } let add_damage = dp .iter() .flatten() .filter_map(|&damage| damage) .max() .unwrap(); println!("{}", costless_damage + add_damage); } #[derive(Debug, Clone, Copy)] struct Card { cost: usize, damage: usize, } /// If `value` is `None` or contains a value less than `cand_value`, update it to `Some(cand_value)`. /// /// Returns whether `value` has been updated or not as a bool value. /// /// # Arguments /// /// * `value` - Reference variable to be updated. /// * `cand_value` - Candidate value for update. pub fn chmax_for_option<T>(value: &mut Option<T>, cand_value: T) -> bool where T: PartialOrd, { if value.as_ref().is_some_and(|cost| cost >= &cand_value) { return false; } *value = Some(cand_value); true }