結果
問題 | No.1043 直列大学 |
ユーザー |
![]() |
提出日時 | 2020-05-01 22:10:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 920 bytes |
コンパイル時間 | 1,903 ms |
コンパイル使用メモリ | 169,612 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-22 19:31:17 |
合計ジャッジ時間 | 3,497 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll, ll> P; typedef vector<ll> VI; typedef vector<VI> VVI; const ll MOD = 1000000007; const ll INF = 2147483647; const ll LINF = 9223372036854775807; #define REP(i, n) for (int i = 0; i < n; i++) #define ALL(v) v.begin(), v.end() const ll MAX=100000; int main() { int n, m; cin >> n >> m; VI v(n), r(m); REP(i,n) cin >> v[i]; REP(i,m) cin >> r[i]; ll a, b; cin >> a >> b; VI pv(MAX+1,0), pr(MAX+1,0); pv[0]=1; pr[0]=1; REP(i,n)for(int j=MAX;j>=v[i];j--){ pv[j]+=pv[j-v[i]]; pv[j]%=MOD; } REP(i,m)for(int j=MAX;j>=r[i];j--){ pr[j]+=pr[j-r[i]]; pr[j]%=MOD; } REP(i,MAX){ pv[i+1]+=pv[i]; pv[i+1]%=MOD; } ll ans=0; for(int i=1;i<=MAX;i++){ if(pr[i]==0) continue; ll l=a*i, rr=min(MAX,b*i); if(l>MAX) break; ans+=pr[i]*((pv[rr]-pv[l-1])+2*MOD)%MOD; ans%=MOD; } cout << ans << endl; return 0; }