結果

問題 No.269 見栄っ張りの募金活動
コンテスト
ユーザー akiradeveloper
提出日時 2019-01-25 20:37:48
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 2,880 bytes
コンパイル時間 13,740 ms
コンパイル使用メモリ 379,208 KB
実行使用メモリ 816,512 KB
最終ジャッジ日時 2024-09-16 04:51:18
合計ジャッジ時間 17,416 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1 -- * 1
other AC * 1 -- * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> src/main.rs:10:186
   |
10 |   macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let mut s = ...
   |                                                                                                                                                                                            ----^
   |                                                                                                                                                                                            |
   |                                                                                                                                                                                            help: remove this `mut`
...
44 | /     input! {
45 | |         n: usize,
46 | |         s: i32,
47 | |         k: i32,
48 | |     };
   | |_____- in this macro invocation
   |
   = note: `#[warn(unused_mut)]` on by default
   = note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let mut s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut iter = s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ iter : expr ) => { } ; ( $ iter : expr , ) => { } ; ( $ iter : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ iter : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ iter , $ t ) ) ,* ) } ; ( $ iter : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ iter , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ iter : expr , chars ) => { read_value ! ( $ iter , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ iter : expr , usize1 ) => { read_value ! ( $ iter , usize ) - 1 } ; ( $ iter : expr , $ t : ty ) => { $ iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

#[derive(Debug)]
struct State {
    n: usize,
    sum: i32,
    donate: i32,
}

// I know this will TLE
fn solve() {
    input! {
        n: usize,
        s: i32,
        k: i32,
    };

    let mut deque = VecDeque::new();
    for don in 0 .. s+1 {
        deque.push_back(State { n: 1, sum: don, donate: don });
    }

    let mut count = 0;

    while let Some(st) = deque.pop_front() {
        // eprintln!("{:?}", st);
        if st.sum == s && st.n == n {
            count += 1;
        }
        for don in st.donate+k .. s+1 {
            if st.sum + don <= s {
                deque.push_back(State { n: st.n+1, sum: st.sum+don, donate: don });
            }
        }
    }

    println!("{}", count);
}
0