結果
問題 |
No.838 Noelちゃんと星々3
|
ユーザー |
![]() |
提出日時 | 2023-04-20 11:10:01 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 17,579 ms |
コンパイル使用メモリ | 380,744 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 10:19:14 |
合計ジャッジ時間 | 14,319 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
use std::{i64::MAX, io::stdin}; fn main() { let stdin = stdin(); let mut stdin = stdin.lines().map(Result::unwrap); let n = stdin.next().unwrap().parse::<usize>().unwrap(); let mut a = stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::<i64>().unwrap()) .collect::<Vec<_>>(); a.sort(); let mut dp = vec![MAX; n + 1]; dp[0] = 0; for i in 0..=n { if i == 1 { continue; } for k in 2..=3 { if i + k <= n { change_min!(&mut dp[i + k], dp[i] + a[i + k - 1] - a[i]); } } } let ans = dp[n]; 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 {} } // }}}