結果
問題 |
No.962 LCPs
|
ユーザー |
|
提出日時 | 2019-12-25 22:35:08 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,851 bytes |
コンパイル時間 | 11,481 ms |
コンパイル使用メモリ | 378,088 KB |
実行使用メモリ | 13,076 KB |
最終ジャッジ日時 | 2024-10-01 08:28:59 |
合計ジャッジ時間 | 13,739 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 WA * 31 |
ソースコード
use std::io::Read; fn main() { let mut s: String = String::new(); std::io::stdin().read_to_string(&mut s).ok(); let mut itr = s.trim().split_whitespace(); let n: usize = itr.next().unwrap().parse().unwrap(); let s: Vec<Vec<char>> = (0..n) .map(|_| itr.next().unwrap().chars().collect()) .collect(); let mut ans: u64 = 0; let mut stack: Vec<(u64, u64)> = Vec::new(); for i in 0..n { ans += s[i].len() as u64; if i == n - 1 { while let Some((cnt, pos)) = stack.pop() { let mut a: u64 = i as u64 - pos + 1; let mut b: u64 = 1; while a > 1 { ans += cnt * a * b; a -= 1; b += 1; } } break; } let mut m: u64 = 0; let k = std::cmp::min(s[i].len(), s[i + 1].len()); for j in 0..k { if s[i][j] != s[i + 1][j] { break; } m += 1; } if m > 0 { // 今よりマッチ数が小さくなるまでpop let mut need: bool = true; while let Some((cnt, pos)) = stack.pop() { if cnt == m { need = false; stack.push((cnt, pos)); break; } else if cnt < m { stack.push((cnt, pos)); break; } let mut a: u64 = i as u64 - pos + 1; let mut b: u64 = 1; while a > 1 { ans += (cnt - m) * a * b; a -= 1; b += 1; } } if need { stack.push((m, i as u64)); } } } println!("{}", ans); }