結果
問題 |
No.1043 直列大学
|
ユーザー |
![]() |
提出日時 | 2022-11-01 03:14:12 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,494 bytes |
コンパイル時間 | 1,311 ms |
コンパイル使用メモリ | 142,368 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-16 00:21:11 |
合計ジャッジ時間 | 2,932 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; const ll MOD = 1000000007; int main() { int N, M; cin >> N >> M; int V[N]; for (int i = 0; i < N; ++i) { cin >> V[i]; } int R[M]; for (int i = 0; i < M; ++i) { cin >> R[i]; } int A, B; cin >> A >> B; ll dp1[100010]; memset(dp1, 0, sizeof(dp1)); dp1[0] = 1; for (int i = 0; i < N; ++i) { int v = V[i]; for (int i = 100000 - v; i >= 0; --i) { dp1[i + v] += dp1[i]; dp1[i + v] %= MOD; } } ll dp2[100010]; memset(dp2, 0, sizeof(dp2)); dp2[0] = 1; for (int i = 0; i < M; ++i) { int r = R[i]; for (int i = 100000 - r; i >= 0; --i) { dp2[i + r] += dp2[i]; dp2[i + r] %= MOD; } } for (int r = 1; r <= 100000; ++r) { dp2[r] += dp2[r - 1]; dp2[r] %= MOD; } ll ans = 0; for (int v = 1; v <= 100000; ++v) { if (dp1[v] == 0) continue; // v / B <= r && r <= v / A; int left = max(1, min(100000, (v + B - 1) / B)); int right = min(100000, v / A); ll v_cnt = dp1[v]; ll r_cnt = (dp2[right] - dp2[left - 1] + MOD) % MOD; // fprintf(stderr, "v: %d, left: %d, right: %d, v_cnt: %lld, r_cnt: %lld\n", v, left, right, v_cnt, r_cnt); ans += v_cnt * r_cnt; ans %= MOD; } cout << ans << endl; return 0; }