結果
問題 |
No.1676 Coin Trade (Single)
|
ユーザー |
|
提出日時 | 2022-10-20 22:38:05 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 12,685 ms |
コンパイル使用メモリ | 402,232 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-06-30 13:27:15 |
合計ジャッジ時間 | 16,000 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
warning: unused variable: `k` --> src/main.rs:9:9 | 9 | let k = nk[1]; | ^ help: if this is intentional, prefix it with an underscore: `_k` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `i` --> src/main.rs:12:9 | 12 | for i in 0..n { | ^ help: if this is intentional, prefix it with an underscore: `_i`
ソースコード
const INF: isize = 1isize << 60; fn main() { let mut nk = String::new(); std::io::stdin().read_line(&mut nk).ok(); let nk: Vec<usize> = nk.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nk[0]; let k = nk[1]; let mut avals = Vec::with_capacity(n); let mut bs = Vec::with_capacity(n); for i in 0..n { let mut am = String::new(); std::io::stdin().read_line(&mut am).ok(); let am: Vec<isize> = am.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = am[0]; let mut b = String::new(); std::io::stdin().read_line(&mut b).ok(); let b: Vec<usize> = b.trim().split_whitespace().map(|s| s.parse::<usize>().unwrap()-1).collect(); avals.push(a); bs.push(b); } let mut paths = vec![vec![]; n]; for u in 0..n { for &v in bs[u].iter() { paths[v].push((u, avals[v] - avals[u])); } if u+1 < n { paths[u].push((u+1, 0)); } } let mut result = vec![INF; n]; result[0] = 0; for u in 0..n { for &(v, cost) in paths[u].iter() { if v <= u { continue; } result[v] = result[v].min(result[u] + cost); } } println!("{}", -result[n-1]); }