結果
問題 | No.1043 直列大学 |
ユーザー |
![]() |
提出日時 | 2020-05-01 22:09:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 498 ms / 2,000 ms |
コード長 | 1,227 bytes |
コンパイル時間 | 2,118 ms |
コンパイル使用メモリ | 172,568 KB |
実行使用メモリ | 8,040 KB |
最終ジャッジ日時 | 2024-12-22 19:31:04 |
合計ジャッジ時間 | 11,385 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long MOD = 1000000007; long long MAX = 200000; long long modsub(long long A, long long B){ return (A % MOD - B % MOD + MOD) % MOD; } int main(){ int N, M; cin >> N >> M; vector<int> V(N); for (int i = 0; i < N; i++){ cin >> V[i]; } vector<int> R(M); for (int i = 0; i < M; i++){ cin >> R[i]; } long long A, B; cin >> A >> B; vector<long long> dpV(MAX, 0); dpV[0] = 1; for (int i = 0; i < N; i++){ vector<long long> dp2 = dpV; for (int j = V[i]; j < MAX - V[i]; j++){ dp2[j] = (dp2[j] + dpV[j - V[i]]) % MOD; } dpV = dp2; } vector<long long> dpR(MAX, 0); dpR[0] = 1; for (int i = 0; i < M; i++){ vector<long long> dp2 = dpR; for (int j = R[i]; j < MAX - R[i]; j++){ dp2[j] = (dp2[j] + dpR[j - R[i]]) % MOD; } dpR = dp2; } vector<long long> sum(MAX, 0); sum[0] = dpV[0]; for (int i = 1; i < MAX; i++){ sum[i] = (sum[i - 1] + dpV[i]) % MOD; } long long ans = 0; for (int i = 1; i < MAX; i++){ long long ub = sum[min(MAX - 1, B * i)]; long long lb = sum[min(MAX - 1, A * i - 1)]; ans = (ans + dpR[i] * modsub(ub, lb) % MOD) % MOD; } cout << ans << endl; }