結果
問題 | No.1331 Moving Penguin |
ユーザー | Strorkis |
提出日時 | 2021-01-09 17:40:46 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 162 ms / 1,500 ms |
コード長 | 3,568 bytes |
コンパイル時間 | 918 ms |
コンパイル使用メモリ | 160,000 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-25 05:04:40 |
合計ジャッジ時間 | 8,104 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 0 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 138 ms
5,376 KB |
testcase_05 | AC | 140 ms
5,376 KB |
testcase_06 | AC | 137 ms
5,376 KB |
testcase_07 | AC | 138 ms
5,376 KB |
testcase_08 | AC | 138 ms
5,376 KB |
testcase_09 | AC | 137 ms
5,376 KB |
testcase_10 | AC | 139 ms
5,376 KB |
testcase_11 | AC | 138 ms
5,376 KB |
testcase_12 | AC | 137 ms
5,376 KB |
testcase_13 | AC | 137 ms
5,376 KB |
testcase_14 | AC | 137 ms
5,376 KB |
testcase_15 | AC | 136 ms
5,376 KB |
testcase_16 | AC | 139 ms
5,376 KB |
testcase_17 | AC | 138 ms
5,376 KB |
testcase_18 | AC | 137 ms
5,376 KB |
testcase_19 | AC | 139 ms
5,376 KB |
testcase_20 | AC | 137 ms
5,376 KB |
testcase_21 | AC | 136 ms
5,376 KB |
testcase_22 | AC | 136 ms
5,376 KB |
testcase_23 | AC | 139 ms
5,376 KB |
testcase_24 | AC | 139 ms
5,376 KB |
testcase_25 | AC | 138 ms
5,376 KB |
testcase_26 | AC | 143 ms
5,376 KB |
testcase_27 | AC | 142 ms
5,376 KB |
testcase_28 | AC | 142 ms
5,376 KB |
testcase_29 | AC | 138 ms
5,376 KB |
testcase_30 | AC | 29 ms
5,376 KB |
testcase_31 | AC | 61 ms
5,376 KB |
testcase_32 | AC | 24 ms
5,376 KB |
testcase_33 | AC | 43 ms
5,376 KB |
testcase_34 | AC | 79 ms
5,376 KB |
testcase_35 | AC | 151 ms
5,376 KB |
testcase_36 | AC | 153 ms
5,376 KB |
testcase_37 | AC | 152 ms
5,376 KB |
testcase_38 | AC | 31 ms
5,376 KB |
testcase_39 | AC | 134 ms
5,376 KB |
testcase_40 | AC | 52 ms
5,376 KB |
testcase_41 | AC | 137 ms
5,376 KB |
testcase_42 | AC | 153 ms
5,376 KB |
testcase_43 | AC | 152 ms
5,376 KB |
testcase_44 | AC | 152 ms
5,376 KB |
testcase_45 | AC | 161 ms
5,376 KB |
testcase_46 | AC | 162 ms
5,376 KB |
testcase_47 | AC | 161 ms
5,376 KB |
testcase_48 | AC | 137 ms
5,376 KB |
ソースコード
struct Scanner<R> { r: R, buf: Vec<u8> } impl<R: std::io::BufRead> Scanner<R> { fn new(r: R) -> Scanner<R> { Scanner { r, buf: Vec::with_capacity(8000) } } fn next(&mut self) -> &str { self.buf.clear(); loop { let (done, used) = { let available = self.r.fill_buf().unwrap(); match available.iter().position(|b| !b.is_ascii_whitespace()) { Some(i) => (true, i), None => (false, available.len()), } }; self.r.consume(used); if done || used == 0 { break; } } loop { let (done, used) = { let available = self.r.fill_buf().unwrap(); match available.iter().position(|b| b.is_ascii_whitespace()) { Some(i) => { self.buf.extend_from_slice(&available[..i]); (true, i) } None => { self.buf.extend_from_slice(&available); (false, available.len()) } } }; self.r.consume(used); if done || used == 0 { unsafe { return std::str::from_utf8_unchecked(&self.buf); } } } } } macro_rules! parse { ($s:expr, Chars) => ($s.chars().collect::<Vec<_>>()); ($s:expr, Bytes) => ($s.bytes().collect::<Vec<_>>()); ($s:expr, Usize1) => (parse!($s, usize) - 1); ($s:expr, $t:ty) => ($s.parse::<$t>().unwrap()); } macro_rules! read { ($sc:expr, [$t:tt; $n:expr]) => ( (0..$n).map(|_| read!($sc, $t)).collect::<Vec<_>>() ); ($sc:expr, ($($t:tt),*)) => (($(read!($sc, $t)),*)); ($sc:expr, $t:ident) => (parse!($sc.next(), $t)); ($sc:expr, $($t:tt),*) => (($(read!($sc, $t)),*)); } #[derive(Clone, Copy)] struct ModInt(usize); impl ModInt { const MOD: usize = 1_000_000_007; } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: Self) -> Self { let x = self.0 + other.0; if x < Self::MOD { Self(x) } else { Self(x - Self::MOD) } } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: Self) { *self = *self + other; } } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } } fn main() { use std::io::Write; let (stdin, stdout) = (std::io::stdin(), std::io::stdout()); let mut scanner = Scanner::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); macro_rules! scan { ($($t:tt)*) => (read!(scanner, $($t)*)); } macro_rules! println { ($($arg:tt)*) => (writeln!(writer, $($arg)*).ok()); } let n = scan!(usize); let k = (n as f64).sqrt() as usize; let mut dp = vec![ModInt(0); n + 1]; dp[0] = ModInt(1); let mut sum = vec![vec![ModInt(0); k + 1]; k + 1]; for i in 0..n { let a = scan!(usize); for (j, sum) in sum.iter().enumerate().skip(1) { dp[i] += sum[i % j]; } if i + 1 == n { break; } let val = dp[i]; if a <= k { sum[a][i % a] += dp[i]; } else { for dp in dp[i..n].iter_mut().step_by(a) { *dp += val; } } if a != 1 { dp[i + 1] += val; } } println!("{}", dp[n - 1]); }