結果
問題 | No.1043 直列大学 |
ユーザー |
![]() |
提出日時 | 2020-05-01 22:40:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 2,133 bytes |
コンパイル時間 | 963 ms |
コンパイル使用メモリ | 95,320 KB |
実行使用メモリ | 75,008 KB |
最終ジャッジ日時 | 2024-12-22 19:36:53 |
合計ジャッジ時間 | 3,045 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
//#include <bits/stdc++.h> #include <iostream> #include <fstream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <map> #include <iomanip> #include <stdlib.h> #include <stdio.h> #include <queue> #include <deque> #include <set> #include <stack> #include <time.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> Pii; typedef pair<int, ll> Pil; typedef pair<ll, ll> Pll; typedef pair<ll, int> Pli; #define fi first #define se second #define mp make_pair const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const ll INF = 1ll << 60; const double PI = 2 * asin(1); void yes() {printf("yes\n");} void no() {printf("no\n");} void Yes() {printf("Yes\n");} void No() {printf("No\n");} void YES() {printf("YES\n");} void NO() {printf("NO\n");} int N, M, V[105], R[105]; ll A, B; ll DPV[105][100005], DPR[105][100005]; ll SumV[int(1e5 + 5)], SumR[int(1e5 + 5)]; int main(){ scanf("%d%d", &N, &M); for (int i = 1; i <= N; i++) scanf("%d", V + i); for (int i = 1; i <= M; i++) scanf("%d", R + i); scanf("%lld%lld", &A, &B); DPV[0][0] = 1; for (int i = 1; i <= N; i++){ for (int j = 0; j <= 1e5; j++){ if (DPV[i - 1][j] == 0) continue; DPV[i][j] += DPV[i - 1][j]; if (j + V[i] <= 1e5) DPV[i][j + V[i]] += DPV[i - 1][j]; DPV[i][j] %= MOD; } } DPR[0][0] = 1; for (int i = 1; i <= M; i++){ for (int j = 0; j <= 1e5; j++){ if (DPR[i - 1][j] == 0) continue; DPR[i][j] += DPR[i - 1][j]; if (j + R[i] <= 1e5) DPR[i][j + R[i]] += DPR[i - 1][j]; DPR[i][j] %= MOD; } } for (int i = 1; i <= 1e5; i++){ SumV[i] = SumV[i - 1] + DPV[N][i]; SumV[i] %= MOD; SumR[i] = SumR[i - 1] + DPR[M][i]; SumR[i] %= MOD; } ll ans = 0; for (ll i = 1; i <= 1e5; i++){ if (SumR[i] == SumR[i - 1]) continue; ll now = SumR[i] - SumR[i - 1]; ll nowA = A * i, nowB = B * i; if (nowA > 1e5) break; nowA--; if (nowB > 1e5) nowB = 1e5; ans += now * (SumV[nowB] - SumV[nowA]); ans %= MOD; } if (ans < 0) ans += MOD; cout << ans << endl; return 0; }