結果
問題 |
No.1043 直列大学
|
ユーザー |
![]() |
提出日時 | 2022-01-14 03:15:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 995 bytes |
コンパイル時間 | 527 ms |
コンパイル使用メモリ | 70,216 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-18 08:50:47 |
合計ジャッジ時間 | 2,081 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long; constexpr ll MOD = 1'000'000'007; int main(){ int n, m; cin >> n >> m; vector<ll> v(n), r(m); for(auto &it: v) cin >> it; for(auto &it: r) cin >> it; int a, b; cin >> a >> b; const int lim = 100010; vector<ll> vdp(lim, 0), rdp(lim, 0); vdp[0] = 1; rdp[0] = 1; for(auto &it: v){ for(int j = lim-1; j >= 0; j--){ if(j-it >= 0) vdp[j] = (vdp[j]+vdp[j-it])%MOD; } } for(auto &it: r){ for(int j = lim-1; j >= 0; j--){ if(j-it >= 0) rdp[j] = (rdp[j]+rdp[j-it])%MOD; } } for(int i = 1; i < lim; i++) vdp[i] = (vdp[i-1]+vdp[i])%MOD; ll ans = 0; for(ll i = 1; i < lim; i++){ ll va = i*a, vb = i*b; if(va >= 100000) continue; if(vb >= lim) vb = lim-1; ans += (vdp[vb]-vdp[va-1]+MOD)%MOD*rdp[i]%MOD; ans %= MOD; } cout << ans << endl; return 0; }