結果

問題 No.269 見栄っ張りの募金活動
ユーザー j6k1j6k1
提出日時 2020-08-01 14:11:25
言語 Rust
(1.77.0)
結果
AC  
実行時間 38 ms / 5,000 ms
コード長 1,824 bytes
コンパイル時間 1,600 ms
コンパイル使用メモリ 144,244 KB
実行使用メモリ 18,264 KB
最終ジャッジ日時 2023-09-22 09:10:32
合計ジャッジ時間 3,068 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 12 ms
8,008 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 38 ms
18,264 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 4 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 4 ms
4,380 KB
testcase_14 AC 3 ms
4,384 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 9 ms
7,748 KB
testcase_19 AC 3 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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