結果
問題 | No.1532 Different Products |
ユーザー | to-omer |
提出日時 | 2021-06-04 23:11:36 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 526 ms / 4,000 ms |
コード長 | 10,174 bytes |
コンパイル時間 | 13,636 ms |
コンパイル使用メモリ | 399,500 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-20 06:46:16 |
合計ジャッジ時間 | 31,181 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 89 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | AC | 1 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,816 KB |
testcase_06 | AC | 1 ms
6,820 KB |
testcase_07 | AC | 1 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 27 ms
6,816 KB |
testcase_10 | AC | 115 ms
6,816 KB |
testcase_11 | AC | 84 ms
6,816 KB |
testcase_12 | AC | 275 ms
6,820 KB |
testcase_13 | AC | 141 ms
6,820 KB |
testcase_14 | AC | 432 ms
6,820 KB |
testcase_15 | AC | 5 ms
6,816 KB |
testcase_16 | AC | 102 ms
6,816 KB |
testcase_17 | AC | 86 ms
6,820 KB |
testcase_18 | AC | 59 ms
6,816 KB |
testcase_19 | AC | 265 ms
6,820 KB |
testcase_20 | AC | 436 ms
6,816 KB |
testcase_21 | AC | 145 ms
6,820 KB |
testcase_22 | AC | 156 ms
6,820 KB |
testcase_23 | AC | 78 ms
6,816 KB |
testcase_24 | AC | 399 ms
6,816 KB |
testcase_25 | AC | 226 ms
6,820 KB |
testcase_26 | AC | 29 ms
6,816 KB |
testcase_27 | AC | 197 ms
6,816 KB |
testcase_28 | AC | 152 ms
6,816 KB |
testcase_29 | AC | 137 ms
6,816 KB |
testcase_30 | AC | 262 ms
6,820 KB |
testcase_31 | AC | 267 ms
6,816 KB |
testcase_32 | AC | 317 ms
6,816 KB |
testcase_33 | AC | 238 ms
6,820 KB |
testcase_34 | AC | 369 ms
6,816 KB |
testcase_35 | AC | 300 ms
6,816 KB |
testcase_36 | AC | 359 ms
6,816 KB |
testcase_37 | AC | 87 ms
6,816 KB |
testcase_38 | AC | 389 ms
6,816 KB |
testcase_39 | AC | 339 ms
6,820 KB |
testcase_40 | AC | 355 ms
6,816 KB |
testcase_41 | AC | 499 ms
6,820 KB |
testcase_42 | AC | 445 ms
6,816 KB |
testcase_43 | AC | 471 ms
6,816 KB |
testcase_44 | AC | 505 ms
6,816 KB |
testcase_45 | AC | 515 ms
6,816 KB |
testcase_46 | AC | 499 ms
6,820 KB |
testcase_47 | AC | 524 ms
6,816 KB |
testcase_48 | AC | 512 ms
6,820 KB |
testcase_49 | AC | 518 ms
6,820 KB |
testcase_50 | AC | 506 ms
6,816 KB |
testcase_51 | AC | 519 ms
6,820 KB |
testcase_52 | AC | 508 ms
6,816 KB |
testcase_53 | AC | 520 ms
6,816 KB |
testcase_54 | AC | 506 ms
6,820 KB |
testcase_55 | AC | 510 ms
6,816 KB |
testcase_56 | AC | 495 ms
6,816 KB |
testcase_57 | AC | 493 ms
6,816 KB |
testcase_58 | AC | 499 ms
6,820 KB |
testcase_59 | AC | 475 ms
6,820 KB |
testcase_60 | AC | 526 ms
6,816 KB |
testcase_61 | AC | 1 ms
6,816 KB |
testcase_62 | AC | 1 ms
6,816 KB |
testcase_63 | AC | 503 ms
6,820 KB |
ソースコード
fn main() { #![allow(unused_imports, unused_macros)] prepare_io!(_in_buf, scanner, _out); macro_rules ! print { ($ ($ arg : tt) *) => (:: std :: write ! (_out , $ ($ arg) *) . expect ("io error")) } macro_rules ! println { ($ ($ arg : tt) *) => (:: std :: writeln ! (_out , $ ($ arg) *) . expect ("io error")) } scan!(scanner, n, k); let mut dp = BTreeMap::new(); dp.insert(k, 1usize); for i in (1..=n).rev() { for k in dp.keys().cloned().collect::<Vec<_>>() { if k >= i { *dp.entry(k / i).or_default() += dp[&k]; } } } let ans = dp.values().sum::<usize>() - 1; println!("{}", ans); } mod main_macros { #[macro_export] macro_rules! prepare_io { ($ in_buf : ident , $ scanner : ident , $ out : ident) => { use std::io::{stdout, BufWriter, Write as _}; let $in_buf = read_stdin_all_unchecked(); let mut $scanner = Scanner::new(&$in_buf); let $out = stdout(); let mut $out = BufWriter::new($out.lock()); }; } } pub fn echo<T: std::fmt::Display>( mut writer: impl std::io::Write, iter: impl IntoIterator<Item = T>, sep: impl std::fmt::Display, ) -> std::io::Result<()> { let mut iter = iter.into_iter(); if let Some(item) = iter.next() { write!(writer, "{}", item)?; } for item in iter { write!(writer, "{}{}", sep, item)?; } writeln!(writer) } pub fn read_stdin_all_unchecked() -> String { use std::io::Read as _; let mut buf = Vec::new(); std::io::stdin().read_to_end(&mut buf).expect("io error"); unsafe { String::from_utf8_unchecked(buf) } } pub fn read_stdin_line() -> String { let mut s = String::new(); std::io::stdin().read_line(&mut s).expect("io error"); s } use std::collections::BTreeMap; pub use scanner_impls::{IterScan, MarkedIterScan, Scanner}; mod scanner_impls { pub trait IterScan: Sized { type Output; fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>; } pub trait MarkedIterScan: Sized { type Output; fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output>; } #[derive(Clone, Debug)] pub struct Scanner<'a> { iter: std::str::SplitAsciiWhitespace<'a>, } impl<'a> Scanner<'a> { #[inline] pub fn new(s: &'a str) -> Self { let iter = s.split_ascii_whitespace(); Self { iter } } #[inline] pub fn scan<T>(&mut self) -> <T as IterScan>::Output where T: IterScan, { <T as IterScan>::scan(&mut self.iter).expect("scan error") } #[inline] pub fn mscan<T>(&mut self, marker: T) -> <T as MarkedIterScan>::Output where T: MarkedIterScan, { marker.mscan(&mut self.iter).expect("scan error") } #[inline] pub fn scan_vec<T>(&mut self, size: usize) -> Vec<<T as IterScan>::Output> where T: IterScan, { (0..size) .map(|_| <T as IterScan>::scan(&mut self.iter).expect("scan error")) .collect() } #[inline] pub fn iter<'b, T>(&'b mut self) -> ScannerIter<'a, 'b, T> where T: IterScan, { ScannerIter { inner: self, _marker: std::marker::PhantomData, } } } macro_rules ! iter_scan_impls { ($ ($ t : ty) *) => { $ (impl IterScan for $ t { type Output = Self ; # [inline] fn scan <'a , I : Iterator < Item = &'a str >> (iter : & mut I) -> Option < Self > { iter . next () ?. parse ::<$ t > () . ok () } }) * } ; } iter_scan_impls ! (char u8 u16 u32 u64 usize i8 i16 i32 i64 isize f32 f64 u128 i128 String); macro_rules ! iter_scan_tuple_impl { ($ ($ T : ident) *) => { impl <$ ($ T : IterScan) ,*> IterScan for ($ ($ T ,) *) { type Output = ($ (<$ T as IterScan >:: Output ,) *) ; # [inline] fn scan <'a , It : Iterator < Item = &'a str >> (_iter : & mut It) -> Option < Self :: Output > { Some (($ (<$ T as IterScan >:: scan (_iter) ?,) *)) } } } ; } iter_scan_tuple_impl!(); iter_scan_tuple_impl!(A); iter_scan_tuple_impl ! (A B); iter_scan_tuple_impl ! (A B C); iter_scan_tuple_impl ! (A B C D); iter_scan_tuple_impl ! (A B C D E); iter_scan_tuple_impl ! (A B C D E F); iter_scan_tuple_impl ! (A B C D E F G); iter_scan_tuple_impl ! (A B C D E F G H); iter_scan_tuple_impl ! (A B C D E F G H I); iter_scan_tuple_impl ! (A B C D E F G H I J); iter_scan_tuple_impl ! (A B C D E F G H I J K); pub struct ScannerIter<'a, 'b, T> { inner: &'b mut Scanner<'a>, _marker: std::marker::PhantomData<fn() -> T>, } impl<'a, 'b, T> Iterator for ScannerIter<'a, 'b, T> where T: IterScan, { type Item = <T as IterScan>::Output; #[inline] fn next(&mut self) -> Option<Self::Item> { <T as IterScan>::scan(&mut self.inner.iter) } } #[macro_export] macro_rules ! scan_value { ($ scanner : expr , ($ ($ t : tt) ,*)) => { ($ ($ crate :: scan_value ! ($ scanner , $ t)) ,*) } ; ($ scanner : expr , [$ t : tt ; $ len : expr]) => { (0 ..$ len) . map (| _ | $ crate :: scan_value ! ($ scanner , $ t)) . collect ::< Vec < _ >> () } ; ($ scanner : expr , [$ t : ty ; $ len : expr]) => { $ scanner . scan_vec ::<$ t > ($ len) } ; ($ scanner : expr , [$ t : ty]) => { $ scanner . iter ::<$ t > () } ; ($ scanner : expr , { $ e : expr }) => { $ scanner . mscan ($ e) } ; ($ scanner : expr , $ t : ty) => { $ scanner . scan ::<$ t > () } ; } #[macro_export] macro_rules ! scan { ($ scanner : expr) => { } ; ($ scanner : expr ,) => { } ; ($ scanner : expr , mut $ var : tt : $ t : tt) => { let mut $ var = $ crate :: scan_value ! ($ scanner , $ t) ; } ; ($ scanner : expr , $ var : tt : $ t : tt) => { let $ var = $ crate :: scan_value ! ($ scanner , $ t) ; } ; ($ scanner : expr , mut $ var : tt : $ t : tt , $ ($ rest : tt) *) => { let mut $ var = $ crate :: scan_value ! ($ scanner , $ t) ; scan ! ($ scanner , $ ($ rest) *) } ; ($ scanner : expr , $ var : tt : $ t : tt , $ ($ rest : tt) *) => { let $ var = $ crate :: scan_value ! ($ scanner , $ t) ; scan ! ($ scanner , $ ($ rest) *) } ; ($ scanner : expr , mut $ var : tt) => { let mut $ var = $ crate :: scan_value ! ($ scanner , usize) ; } ; ($ scanner : expr , $ var : tt) => { let $ var = $ crate :: scan_value ! ($ scanner , usize) ; } ; ($ scanner : expr , mut $ var : tt , $ ($ rest : tt) *) => { let mut $ var = $ crate :: scan_value ! ($ scanner , usize) ; scan ! ($ scanner , $ ($ rest) *) } ; ($ scanner : expr , $ var : tt , $ ($ rest : tt) *) => { let $ var = $ crate :: scan_value ! ($ scanner , usize) ; scan ! ($ scanner , $ ($ rest) *) } ; } } pub use marker_impls::{CharWithBase, Chars, CharsWithBase, Collect, SizedCollect, Usize1}; mod marker_impls { use super::*; use std::{ iter::{repeat_with, FromIterator}, marker::PhantomData, }; #[derive(Debug, Copy, Clone)] pub struct Usize1; impl IterScan for Usize1 { type Output = usize; #[inline] fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> { <usize as IterScan>::scan(iter)?.checked_sub(1) } } #[derive(Debug, Copy, Clone)] pub struct CharWithBase(pub char); impl MarkedIterScan for CharWithBase { type Output = usize; #[inline] fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> { Some((<char as IterScan>::scan(iter)? as u8 - self.0 as u8) as usize) } } #[derive(Debug, Copy, Clone)] pub struct Chars; impl IterScan for Chars { type Output = Vec<char>; #[inline] fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> { Some(iter.next()?.chars().collect()) } } #[derive(Debug, Copy, Clone)] pub struct CharsWithBase(pub char); impl MarkedIterScan for CharsWithBase { type Output = Vec<usize>; #[inline] fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> { Some( iter.next()? .chars() .map(|c| (c as u8 - self.0 as u8) as usize) .collect(), ) } } #[derive(Debug, Copy, Clone)] pub struct Collect<T, B = Vec<<T as IterScan>::Output>> where T: IterScan, B: FromIterator<<T as IterScan>::Output>, { size: usize, _marker: PhantomData<fn() -> (T, B)>, } impl<T, B> Collect<T, B> where T: IterScan, B: FromIterator<<T as IterScan>::Output>, { pub fn new(size: usize) -> Self { Self { size, _marker: PhantomData, } } } impl<T, B> MarkedIterScan for Collect<T, B> where T: IterScan, B: FromIterator<<T as IterScan>::Output>, { type Output = B; #[inline] fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> { repeat_with(|| <T as IterScan>::scan(iter)) .take(self.size) .collect() } } #[derive(Debug, Copy, Clone)] pub struct SizedCollect<T, B = Vec<<T as IterScan>::Output>> where T: IterScan, B: FromIterator<<T as IterScan>::Output>, { _marker: PhantomData<fn() -> (T, B)>, } impl<T, B> IterScan for SizedCollect<T, B> where T: IterScan, B: FromIterator<<T as IterScan>::Output>, { type Output = B; #[inline] fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> { let size = usize::scan(iter)?; repeat_with(|| <T as IterScan>::scan(iter)) .take(size) .collect() } } }