結果

問題 No.269 見栄っ張りの募金活動
ユーザー j6k1
提出日時 2020-08-01 14:11:25
言語 Rust
(1.83.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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");
		}
	}
}
0