結果
問題 | No.2486 Don't come next to me |
ユーザー |
|
提出日時 | 2023-09-29 23:39:53 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 2,181 bytes |
コンパイル時間 | 12,732 ms |
コンパイル使用メモリ | 376,896 KB |
実行使用メモリ | 16,708 KB |
最終ジャッジ日時 | 2024-07-22 17:35:02 |
合計ジャッジ時間 | 16,113 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
pub mod scanner { pub struct Scanner { buf: Vec<String>, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next<T: std::str::FromStr>(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec<String> { source .split_whitespace() .rev() .map(String::from) .collect::<Vec<_>>() } } } use crate::scanner::Scanner; use std::{collections::BTreeMap, io::Write}; fn main() { let mut scanner = Scanner::new(); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let t: usize = 1; for _ in 0..t { solve(&mut scanner, &mut out); } } fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) { let _n = scanner.next::<usize>(); let m = scanner.next::<usize>(); let a = (0..m).map(|_| scanner.next::<usize>()).collect::<Vec<_>>(); fn dfs(memo: &mut BTreeMap<usize, usize>, x: usize) -> usize { if let Some(&res) = memo.get(&x) { return res; } if x <= 1 || x % 2 == 0 { return x; } let mut res = 0; for x1 in [(x - 1) / 2, x / 2] { let res1 = dfs(memo, x1); memo.insert(x1, res1); res += res1; } memo.insert(x, res); return res; } let mut ans = 0usize; let mut memo = BTreeMap::new(); memo.insert(0, 0); memo.insert(1, 1); memo.insert(2, 2); for i in 0..m - 1 { ans += dfs(&mut memo, a[i + 1] - a[i] - 1); } writeln!(out, "{}", ans).unwrap(); }