結果
問題 | No.90 品物の並び替え |
ユーザー |
![]() |
提出日時 | 2018-11-07 20:27:03 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 122 ms / 5,000 ms |
コード長 | 1,497 bytes |
コンパイル時間 | 11,771 ms |
コンパイル使用メモリ | 404,004 KB |
実行使用メモリ | 45,568 KB |
最終ジャッジ日時 | 2024-11-20 20:51:26 |
合計ジャッジ時間 | 12,854 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
use std::io::Read;fn main() {let mut buf = String::new();let mut stdin = std::io::stdin();stdin.read_to_string(&mut buf).unwrap();let mut iter = buf.split_whitespace();let n: usize = iter.next().unwrap().parse().unwrap();let m: usize = iter.next().unwrap().parse().unwrap();let mut board: Vec<Vec<usize>> = vec![vec![0; n]; n];let mut row: usize = 0;while row < m {let front: usize = iter.next().unwrap().parse().unwrap();let back: usize = iter.next().unwrap().parse().unwrap();let score: usize = iter.next().unwrap().parse().unwrap();board[front][back] = score;row += 1;}let mut max: usize = 0;for perm in permutation(n) {let mut total_score: usize = 0;let mut is_set: Vec<bool> = vec![false; n];for num in perm {for b in (0..n).filter(|&b| !is_set[b]) {total_score += board[num][b];}is_set[num] = true;}if total_score > max {max = total_score;}}println!("{}", max);}fn permutation(n: usize) -> Vec<Vec<usize>> {if n == 1 {return vec![vec![0]]}let mut vec: Vec<Vec<usize>> = Vec::new();for p in permutation(n-1).iter_mut() {p.push(n-1);vec.push(p.clone());for i in (1..n).rev() {p.swap(i, i-1);vec.push(p.clone());}}vec}