結果
問題 |
No.1043 直列大学
|
ユーザー |
|
提出日時 | 2022-11-30 00:21:49 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,721 bytes |
コンパイル時間 | 14,128 ms |
コンパイル使用メモリ | 378,012 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-07 09:02:31 |
合計ジャッジ時間 | 14,629 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 vcnt = vec![0usize; LIMIT+1]; let mut rcnt = vec![0usize; LIMIT+1]; vcnt[0] = 1; rcnt[0] = 1; for i in 0..n { for j in (0..=LIMIT).rev() { if j+v[i] <= LIMIT { vcnt[j+v[i]] += vcnt[j]; vcnt[j+v[i]] %= MOD; } } } for i in 0..m { for j in (0..=LIMIT).rev() { if j+r[i] <= LIMIT { rcnt[j+r[i]] += rcnt[j]; rcnt[j+r[i]] %= MOD; } } } for i in 0..LIMIT { rcnt[i+1] += rcnt[i]; rcnt[i+1] %= MOD; } let mut result = 0usize; for i in 1..=LIMIT { if vcnt[i] == 0 { continue; } let left = i / b + if i % b > 0 { 1 } else { 0 }; let right = i / a; result += vcnt[i] * (MOD + rcnt[right] - rcnt[left-1]) % MOD; } println!("{}", result % MOD); }