結果
問題 | No.572 妖精の演奏 |
ユーザー |
|
提出日時 | 2017-10-06 23:01:53 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,433 bytes |
コンパイル時間 | 11,606 ms |
コンパイル使用メモリ | 384,540 KB |
実行使用メモリ | 91,008 KB |
最終ジャッジ日時 | 2024-11-17 01:54:06 |
合計ジャッジ時間 | 22,134 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 WA * 1 |
ソースコード
#[allow(dead_code)]const MOD: usize = 1_000000000 + 7;fn main() {let mut cin = Scanner::new();let n = cin.next_usize() - 1;let m = cin.next_usize();let a = (0..m).map(|_| (0..m).map(|_| { cin.next_usize() }).collect::<Vec<_>>()).collect::<Vec<_>>();let max = 12*m*m+1;let mut dp = vec![vec![vec![0; m]; m]; max];for k in 1..max {for i in 0..m {for j in 0..m {for l in 0..m {dp[k][i][j] = if k == 1 {std::cmp::max(dp[k][i][j], a[i][j])} else {std::cmp::max(dp[k][i][j], dp[k-1][i][l] + a[l][j])}}}}}let mut ans = 0;for k in 1..max {for i in 0..m {for j in 0..m {let q = n / k;let r = n % k;ans = std::cmp::max(ans, dp[k][i][i] * q + dp[r][i][j]);}}}println!("{}", ans);}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 whereT: 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>() }#[allow(dead_code)] fn next_isize(&mut self) -> isize { self.next_generics::<isize>() }}