結果
問題 |
No.1043 直列大学
|
ユーザー |
![]() |
提出日時 | 2020-05-02 01:00:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,303 bytes |
コンパイル時間 | 772 ms |
コンパイル使用メモリ | 71,168 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-22 19:58:03 |
合計ジャッジ時間 | 2,401 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <vector> const long long MOD = 1000000007; const long long DP_MAX = 100000; int main() { int N, M; std::cin >> N >> M; std::vector<int> V(N), R(M); for (int i = 0; i < N; i++) std::cin >> V[i]; for (int i = 0; i < M; i++) std::cin >> R[i]; long long A, B; std::cin >> A >> B; std::vector<long long> dp_V(DP_MAX + 1), dp_R(DP_MAX + 1); dp_V[0] = dp_R[0] = 1; for (int i = 0; i < N; i++) { for (int j = DP_MAX; j >= 0; j--) { if (j + V[i] <= DP_MAX) { dp_V[j + V[i]] += dp_V[j]; dp_V[j + V[i]] %= MOD; } } } for (int i = 0; i < M; i++) { for (int j = DP_MAX; j >= 0; j--) { if (j + R[i] <= DP_MAX) { dp_R[j + R[i]] += dp_R[j]; dp_R[j + R[i]] %= MOD; } } } for (int i = 0; i < DP_MAX; i++) { dp_V[i + 1] += dp_V[i]; dp_V[i + 1] %= MOD; } long long ans = 0; for (long long i = 1; i <= DP_MAX; i++) { long long left = i * A - 1; if (left > DP_MAX) break; long long right = std::min(DP_MAX, i * B); ans += (dp_V[right] - dp_V[left] + MOD) * dp_R[i] % MOD; ans %= MOD; } std::cout << ans << "\n"; }