結果
問題 |
No.2759 Take Pictures, Elements?
|
ユーザー |
![]() |
提出日時 | 2024-05-28 11:44:38 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 2,234 bytes |
コンパイル時間 | 13,935 ms |
コンパイル使用メモリ | 383,168 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2025-06-20 13:21:52 |
合計ジャッジ時間 | 12,751 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
use std::cmp; use std::collections::HashMap; use std::io::*; use std::io::{stderr, stdin}; use std::str::FromStr; fn main() { let cin = stdin(); let mut sc = Scanner::new(cin.lock()); let n = sc.next::<usize>(); let q = sc.next::<usize>(); let a = sc.vec::<usize>(n); let mut mp = HashMap::new(); for i in 0..n { mp.entry(a[i]).or_insert(vec![]).push(i); } let mut dp = vec![vec![2e9 as usize; n]; q + 1]; dp[0][0] = 0; let mut prv = 0; for i in 0..q { let b = sc.next::<usize>(); if i == 0 { for j in mp.get(&b).unwrap() { dp[i + 1][*j] = cmp::min(dp[i + 1][*j], dp[i][0] + *j); } } else { for j in mp.get(&prv).unwrap() { for k in mp.get(&b).unwrap() { dp[i + 1][*k] = cmp::min( dp[i + 1][*k], dp[i][*j] + (cmp::max(*j, *k) - cmp::min(*j, *k)), ); } } } prv = b; } let mut mi = usize::MAX; for i in mp.get(&prv).unwrap() { mi = cmp::min(mi, dp[q][*i]); } println!("{}", mi); } pub struct Scanner<R: std::io::Read> { reader: R, } #[allow(dead_code)] impl<R: Read> Scanner<R> { fn new(reader: R) -> Scanner<R> { Scanner { reader: reader } } fn read<T: FromStr>(&mut self) -> Option<T> { let token = self .reader .by_ref() .bytes() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::<String>(); if token.is_empty() { None } else { token.parse::<T>().ok() } } fn next<T: FromStr>(&mut self) -> T { if let Some(s) = self.read() { s } else { writeln!(stderr(), "Terminated with EOF").unwrap(); std::process::exit(0); } } fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.next()).collect() } fn char(&mut self) -> char { self.next::<String>().chars().next().unwrap() } }