結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2017-03-24 22:49:02 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,359 bytes |
コンパイル時間 | 15,629 ms |
コンパイル使用メモリ | 378,724 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 22:14:50 |
合計ジャッジ時間 | 14,695 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
fn main() { let mut scanner = Scanner::new(); let gx = scanner.next_usize(); let gy = scanner.next_usize(); let n = scanner.next_usize(); let f = scanner.next_usize(); let mut x = Vec::new(); let mut y = Vec::new(); let mut c = Vec::new(); for _ in 0..n { x.push(scanner.next_usize()); y.push(scanner.next_usize()); c.push(scanner.next_usize()); } let inf = 1_000000000_000000000_usize; let mut ans = vec![vec![inf; gx+1]; gy+1]; ans[0][0] = 0; for k in 0..n { for i in 0..(gy+1) { for j in 0..gx+1 { let i = gy - i; let j = gx - j; if x[k] <= j && y[k] <= i { ans[i][j] = std::cmp::min(ans[i][j], ans[i-y[k]][j-x[k]] + c[k]) } } } } let mut res = std::usize::MAX; for i in 0..(gy+1) { for j in 0..gx+1 { res = std::cmp::min(res, ans[i][j] + ((gy-i)+(gx-j))*f); } } println!("{}", res); } struct Scanner { reader: std::io::Stdin, tokens: std::collections::VecDeque<String>, } impl Scanner { fn new() -> Self { Scanner { reader: std::io::stdin(), tokens: std::collections::VecDeque::new(), } } fn next(&mut self) -> String { if self.tokens.is_empty() { let mut s = String::new(); loop { self.reader.read_line(&mut s).ok(); let s = s.trim(); if s.len() != 0 { for it in s.split_whitespace() { self.tokens.push_back(it.into()) } break; } } } self.tokens.pop_front().unwrap() } fn next_generics<T>(&mut self) -> T where T: std::str::FromStr + std::marker::Copy, <T as std::str::FromStr>::Err: std::fmt::Debug { self.next().parse().unwrap() } #[allow(dead_code)] fn next_i32(&mut self) -> i32 { self.next_generics::<i32>() } #[allow(dead_code)] fn next_i64(&mut self) -> i64 { self.next_generics::<i64>() } #[allow(dead_code)] fn next_u64(&mut self) -> u64 { self.next_generics::<u64>() } #[allow(dead_code)] fn next_usize(&mut self) -> usize { self.next_generics::<usize>() } }