Submission #3008297
Source Code Expand
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Read, Write, BufWriter};
#[allow(dead_code)]
fn getline() -> String {
let mut ret = String::new();
std::io::stdin().read_line(&mut ret).ok().unwrap();
ret
}
fn get_word() -> String {
let mut stdin = std::io::stdin();
let mut u8b: [u8; 1] = [0];
loop {
let mut buf: Vec<u8> = Vec::with_capacity(16);
loop {
let res = stdin.read(&mut u8b);
if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
break;
} else {
buf.push(u8b[0]);
}
}
if buf.len() >= 1 {
let ret = String::from_utf8(buf).unwrap();
return ret;
}
}
}
#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }
const MOD: i64 = 1_000_000_007;
/// Refers to external ::MOD.
/// Verified by: https://beta.atcoder.jp/contests/arc099/submissions/2893648
mod mod_int {
use ::MOD;
use std::ops::*;
#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct ModInt { pub x: i64 }
impl ModInt {
fn check_integrity(self) {
debug_assert!(self.x >= 0);
debug_assert!(self.x < MOD);
}
// x >= 0
pub fn new<T: Into<i64>>(x: T) -> Self { ModInt { x: x.into() % MOD } }
#[allow(dead_code)]
pub fn mul_fast(self, other: Self) -> Self {
self.check_integrity();
other.check_integrity();
ModInt { x: self.x * other.x % MOD }
}
#[allow(dead_code)]
pub fn mul_slow(self, other: Self) -> Self {
// Naive multiplication in order to avoid overflow
self.check_integrity();
other.check_integrity();
let mut sum = ModInt::new(0);
let mut cur = self;
let mut e = other.x;
if self.x < other.x {
cur = other;
e = self.x;
}
while e > 0 {
if e % 2 == 1 {
sum = sum + cur;
}
cur = cur + cur;
e /= 2;
}
sum
}
pub fn pow(self, mut e: i64) -> Self {
self.check_integrity();
debug_assert!(e >= 0);
let mut sum = ModInt::new(1);
let mut cur = ModInt::new(self.x);
while e > 0 {
if e % 2 != 0 {
sum = sum * cur;
}
cur = cur * cur;
e /= 2;
}
sum
}
pub fn inv(self) -> Self { self.pow(MOD - 2) }
}
impl Add for ModInt {
type Output = Self;
fn add(self, other: Self) -> Self {
self.check_integrity();
other.check_integrity();
let mut sum = self.x + other.x;
if sum >= MOD { sum -= MOD; }
ModInt { x: sum }
}
}
impl Sub for ModInt {
type Output = Self;
fn sub(self, other: Self) -> Self {
self.check_integrity();
other.check_integrity();
let mut sum = self.x - other.x;
if sum < 0 { sum += MOD; }
ModInt { x: sum }
}
}
impl Mul for ModInt {
type Output = Self;
fn mul(self, other: Self) -> Self {
self.mul_fast(other)
}
}
impl AddAssign for ModInt {
fn add_assign(&mut self, rhs: ModInt) { *self = *self + rhs; }
}
impl SubAssign for ModInt {
fn sub_assign(&mut self, rhs: ModInt) { *self = *self - rhs; }
}
impl MulAssign for ModInt {
fn mul_assign(&mut self, rhs: ModInt) { *self = *self * rhs; }
}
impl ::std::fmt::Display for ModInt {
fn fmt(&self, f: &mut::std::fmt::Formatter) -> ::std::fmt::Result {
self.x.fmt(f)
}
}
} // mod mod_int
use mod_int::*;
fn solve() {
let out = std::io::stdout();
let mut out = BufWriter::new(out.lock());
macro_rules! puts {
($format:expr) => (write!(out,$format).unwrap());
($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
}
let n = get();
let m = get();
let q = get();
let a: Vec<usize> = (0 .. n).map(|_| get()).collect();
let mut dp = vec![ModInt::new(0); m + 1];
dp[0] = ModInt::new(1);
for i in 0 .. n {
let mut dp2 = vec![ModInt::new(0); m + 1];
for j in 0 .. m + 1 {
dp2[j] += dp[j];
if j + a[i] + 1 <= m {
dp2[j + a[i] + 1] -= dp[j];
}
}
for j in 0 .. m {
dp2[j + 1] += dp2[j];
}
dp = dp2;
}
let mut tbl = vec![vec![ModInt::new(0); m + 1]; n];
for i in 0 .. n {
let mut dp = dp.clone();
for j in (0 .. m).rev() {
dp[j + 1] -= dp[j];
}
for j in 0 .. m - a[i] {
dp[j + a[i] + 1] += dp[j];
}
for j in 0 .. m + 1 { tbl[i][j] = dp[j]; }
}
for _ in 0 .. q {
let k: usize = get::<usize>() - 1;
let x: usize = get();
puts!("{}\n", tbl[k][m - x]);
}
}
fn main() {
// In order to avoid potential stack overflow, spawn a new thread.
let stack_size = 104_857_600; // 100 MB
let thd = std::thread::Builder::new().stack_size(stack_size);
thd.spawn(|| solve()).unwrap().join().unwrap();
}
Submission Info
Submission Time |
|
Task |
D - 注文の多い高橋商店 |
User |
kobae964 |
Language |
Rust (1.15.1) |
Score |
100 |
Code Size |
5516 Byte |
Status |
AC |
Exec Time |
306 ms |
Memory |
54268 KB |
Compile Error
warning: method is never used: `pow`, #[warn(dead_code)] on by default
--> ./Main.rs:78:9
|
78 | pub fn pow(self, mut e: i64) -> Self {
| ^
warning: method is never used: `inv`, #[warn(dead_code)] on by default
--> ./Main.rs:92:9
|
92 | pub fn inv(self) -> Self { self.pow(MOD - 2) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
0 / 0 |
10 / 10 |
20 / 20 |
50 / 50 |
20 / 20 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
Subtask1 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt |
Subtask2 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt |
Subtask3 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt |
Subtask4 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask4_01.txt, subtask4_02.txt, subtask4_03.txt, subtask4_04.txt, subtask4_05.txt, subtask4_06.txt, subtask4_07.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
3 ms |
8572 KB |
sample_02.txt |
AC |
3 ms |
8572 KB |
subtask1_01.txt |
AC |
3 ms |
8572 KB |
subtask1_02.txt |
AC |
3 ms |
8572 KB |
subtask1_03.txt |
AC |
3 ms |
8572 KB |
subtask1_04.txt |
AC |
3 ms |
8572 KB |
subtask1_05.txt |
AC |
3 ms |
8572 KB |
subtask1_06.txt |
AC |
3 ms |
8572 KB |
subtask1_07.txt |
AC |
3 ms |
8572 KB |
subtask1_08.txt |
AC |
3 ms |
8572 KB |
subtask2_01.txt |
AC |
21 ms |
8956 KB |
subtask2_02.txt |
AC |
40 ms |
9468 KB |
subtask2_03.txt |
AC |
41 ms |
9340 KB |
subtask3_01.txt |
AC |
28 ms |
27004 KB |
subtask3_02.txt |
AC |
59 ms |
49532 KB |
subtask3_03.txt |
AC |
53 ms |
49532 KB |
subtask4_01.txt |
AC |
243 ms |
43516 KB |
subtask4_02.txt |
AC |
296 ms |
54268 KB |
subtask4_03.txt |
AC |
200 ms |
10108 KB |
subtask4_04.txt |
AC |
177 ms |
9468 KB |
subtask4_05.txt |
AC |
306 ms |
54268 KB |
subtask4_06.txt |
AC |
254 ms |
50428 KB |
subtask4_07.txt |
AC |
298 ms |
54012 KB |