結果
問題 |
No.1043 直列大学
|
ユーザー |
|
提出日時 | 2022-11-29 01:16:51 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,759 bytes |
コンパイル時間 | 16,071 ms |
コンパイル使用メモリ | 388,424 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-06 04:39:33 |
合計ジャッジ時間 | 13,379 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
const MOD: usize = 1e9 as usize + 7; const LIMIT: usize = 100000; fn main() { let mut nm = String::new(); std::io::stdin().read_line(&mut nm).ok(); let nm: Vec<usize> = nm.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nm[0]; let m = nm[1]; let mut v = String::new(); std::io::stdin().read_line(&mut v).ok(); let v: Vec<usize> = v.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let mut r = String::new(); std::io::stdin().read_line(&mut r).ok(); let r: Vec<usize> = r.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let mut ab = String::new(); std::io::stdin().read_line(&mut ab).ok(); let ab: Vec<usize> = ab.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = ab[0]; let b = ab[1]; let mut vcnts = vec![0usize; LIMIT+1]; let mut rcnts = vec![0usize; LIMIT+1]; vcnts[0] = 1; rcnts[0] = 1; for i in 0..n { for j in (0..=LIMIT).rev() { if v[i] + j <= LIMIT { vcnts[v[i]+j] += vcnts[j]; vcnts[v[i]+j] %= MOD; } } } for i in 0..m { for j in (0..=LIMIT).rev() { if r[i] + j <= LIMIT { rcnts[r[i]+j] += rcnts[j]; rcnts[r[i]+j] %= MOD; } } } for i in 0..LIMIT { rcnts[i+1] += rcnts[i]; rcnts[i+1] %= MOD; } let mut result = 0usize; for i in 1..=LIMIT { if vcnts[i] == 0 { continue; } let left = i / b + if i % b > 0 { 1 } else { 0 }; let right = i / a; result += vcnts[i] * (MOD + rcnts[right] - rcnts[left-1]) % MOD; result %= MOD; } println!("{}", result); }