#523128 (Rust) No.269 見栄っ張りの募金活動

• 問題: No.269 見栄っ張りの募金活動
• ユーザー: j6k1
• 提出日時: 2020-08-01 14:11:25
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 38 ms / 5,000 ms
• コード長: 1,824 bytes
• コンパイル時間: 13,564 ms
• コンパイル使用メモリ: 376,872 KB
• 実行使用メモリ: 18,304 KB
• 最終ジャッジ日時: 2024-07-08 01:23:07
• 合計ジャッジ時間: 14,069 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	12 ms; 8,064 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	38 ms; 18,304 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	4 ms; 5,376 KB
testcase_16	AC	0 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	9 ms; 7,552 KB
testcase_19	AC	3 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	3 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB

ソースコード

use std::fmt;
use std::io::stdin;
use std::io::BufRead;
use std::str;
use std::str::FromStr;

const M:usize = 1000_000_007;

fn main() {
    let stdin = stdin();
    let mut scan = InputScanner::new(stdin.lock(),256);

	let n:usize = scan.next();
	let s:usize = scan.next();
	let k:usize = scan.next();

	let m = n;
	let d:usize = (n * (n - 1)) / 2 * k;

	if d > s {
		println!("0");
	} else {
		let n = s - d;

		let mut dp: Vec<Vec<usize>> = (0..(n + 1)).map(|_| (0..(m + 1)).map(|_| 0).collect()).collect();

		dp[0][0] = 1;

		for j in 1..(m + 1) {
			for i in 0..(n + 1) {
				if i >= j {
					dp[i][j] = (dp[i - j][j] + dp[i][j - 1]) % M;
				} else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}

		println!("{}", dp[n][m]);
	}
}
struct InputScanner<R: BufRead> {
	reader: R,
	buf: Vec<u8>, // Should never be empty
	pos: usize,   // Should never be out of bounds as long as the input ends with '\n'
}
impl<R: BufRead> InputScanner<R> {
	fn new(reader: R, capacity: usize) -> Self {
		InputScanner {
			reader: reader,
			buf: Vec::with_capacity(capacity),
			pos: 0,
		}
	}

	#[inline]
	fn next<T: FromStr>(&mut self) -> T
	where
		T::Err: fmt::Debug,
	{
		if self.buf.is_empty() {
			self._read_next_line();
		}
		let mut start = None;
		loop {
			match (self.buf[self.pos], start.is_some()) {
				(b' ', true) | (b'\n', true) | (b'\r', true) => break,
				(_, true) | (b' ', false) => self.pos += 1,
				(b'\n', false) | (b'\r', false) => self._read_next_line(),
				(_, false) => start = Some(self.pos),
			}
		}
		let target = &self.buf[start.unwrap()..self.pos];
		unsafe { str::from_utf8_unchecked(target) }.parse().unwrap()
	}

	#[inline]
	fn _read_next_line(&mut self) {
		self.pos = 0;
		self.buf.clear();
		if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 {
			panic!("Reached EOF");
		}
	}
}