結果
問題 | No.783 門松計画 |
ユーザー | ngtkana |
提出日時 | 2023-04-30 18:40:59 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 1,612 ms / 2,000 ms |
コード長 | 2,884 bytes |
コンパイル時間 | 12,618 ms |
コンパイル使用メモリ | 387,532 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-11-19 08:26:01 |
合計ジャッジ時間 | 18,781 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 768 ms
6,400 KB |
testcase_11 | AC | 1,612 ms
6,528 KB |
testcase_12 | AC | 1,184 ms
6,528 KB |
testcase_13 | AC | 111 ms
5,248 KB |
testcase_14 | AC | 370 ms
5,504 KB |
testcase_15 | AC | 30 ms
5,248 KB |
testcase_16 | AC | 10 ms
5,248 KB |
testcase_17 | AC | 211 ms
6,016 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 206 ms
5,248 KB |
testcase_20 | AC | 1 ms
5,248 KB |
testcase_21 | AC | 5 ms
5,248 KB |
testcase_22 | AC | 5 ms
5,248 KB |
testcase_23 | AC | 1 ms
5,248 KB |
testcase_24 | AC | 61 ms
5,248 KB |
testcase_25 | AC | 41 ms
5,248 KB |
testcase_26 | AC | 227 ms
5,376 KB |
ソースコード
use cmpmore::CmpMore; use std::{convert::TryFrom, io::stdin}; fn main() { let mut stdin = stdin().lines().map(Result::unwrap); let [_n, wmax] = <[_; 2]>::try_from( stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::<usize>().unwrap()) .collect::<Vec<_>>() .as_slice(), ) .unwrap(); let ls = stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::<usize>().unwrap()) .collect::<Vec<_>>(); let lmax = ls.iter().max().unwrap() + 1; let ws = stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::<usize>().unwrap()) .collect::<Vec<_>>(); let mut dp = vec![vec![vec![None; lmax + 1]; lmax + 1]; wmax + 1]; for (&l1, &dw1) in ls.iter().zip(&ws) { for (&l2, &dw2) in ls.iter().zip(&ws) { for (&l3, &dw3) in ls.iter().zip(&ws) { for w in dw1 + dw2 + dw3..=wmax { if (l1 > l2 && l2 < l3 && l1 != l3) || (l1 < l2 && l2 > l3 && l1 != l3) { dp[w - dw1 - dw2 - dw3][l1][l2].change_max(Some(l1 + l2 + l3)); } } } } } for _ in 0..=wmax { let mut swp = dp.clone(); for (&l, &dw) in ls.iter().zip(&ws) { for w in dw..=wmax { for l1 in 0..=lmax { for l2 in 0..=lmax { if (l2 > l1 && l1 < l && l2 != l) || (l2 < l1 && l1 > l && l2 != l) { swp[w - dw][l][l1].change_max(dp[w][l1][l2].map(|x| x + l)); } } } } } dp = swp; } let ans = dp.iter().flatten().flatten().max().unwrap().unwrap_or(0); println!("{}", ans); } // cmpmore {{{ #[allow(dead_code)] mod cmpmore { pub fn change_min<T: PartialOrd>(lhs: &mut T, rhs: T) { if *lhs > rhs { *lhs = rhs; } } pub fn change_max<T: PartialOrd>(lhs: &mut T, rhs: T) { if *lhs < rhs { *lhs = rhs; } } #[macro_export] macro_rules! change_min { ($lhs:expr, $rhs:expr) => { let rhs = $rhs; let lhs = $lhs; $crate::cmpmore::change_min(lhs, rhs); }; } #[macro_export] macro_rules! change_max { ($lhs:expr, $rhs:expr) => { let rhs = $rhs; let lhs = $lhs; $crate::cmpmore::change_max(lhs, rhs); }; } pub trait CmpMore: PartialOrd + Sized { fn change_min(&mut self, rhs: Self) { change_min(self, rhs) } fn change_max(&mut self, rhs: Self) { change_max(self, rhs) } } impl<T: PartialOrd + Sized> CmpMore for T {} } // }}}