結果
問題 | No.1043 直列大学 |
ユーザー | monkukui2 |
提出日時 | 2020-05-01 23:00:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 248 ms / 2,000 ms |
コード長 | 2,551 bytes |
コンパイル時間 | 973 ms |
コンパイル使用メモリ | 102,420 KB |
実行使用メモリ | 83,544 KB |
最終ジャッジ日時 | 2023-08-24 05:51:42 |
合計ジャッジ時間 | 5,824 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
7,152 KB |
testcase_01 | AC | 12 ms
6,136 KB |
testcase_02 | AC | 18 ms
9,220 KB |
testcase_03 | AC | 12 ms
6,204 KB |
testcase_04 | AC | 12 ms
6,140 KB |
testcase_05 | AC | 13 ms
6,072 KB |
testcase_06 | AC | 12 ms
6,120 KB |
testcase_07 | AC | 15 ms
7,724 KB |
testcase_08 | AC | 15 ms
7,656 KB |
testcase_09 | AC | 81 ms
44,352 KB |
testcase_10 | AC | 95 ms
57,808 KB |
testcase_11 | AC | 137 ms
78,880 KB |
testcase_12 | AC | 248 ms
83,544 KB |
testcase_13 | AC | 190 ms
81,736 KB |
testcase_14 | AC | 205 ms
81,988 KB |
testcase_15 | AC | 233 ms
80,624 KB |
testcase_16 | AC | 200 ms
73,352 KB |
testcase_17 | AC | 134 ms
60,308 KB |
testcase_18 | AC | 128 ms
63,488 KB |
testcase_19 | AC | 186 ms
80,728 KB |
testcase_20 | AC | 128 ms
61,100 KB |
testcase_21 | AC | 170 ms
79,100 KB |
testcase_22 | AC | 179 ms
76,852 KB |
testcase_23 | AC | 242 ms
82,596 KB |
testcase_24 | AC | 145 ms
65,168 KB |
testcase_25 | AC | 188 ms
73,620 KB |
testcase_26 | AC | 205 ms
81,436 KB |
testcase_27 | AC | 90 ms
51,444 KB |
testcase_28 | AC | 156 ms
75,712 KB |
testcase_29 | AC | 43 ms
28,904 KB |
testcase_30 | AC | 156 ms
76,848 KB |
ソースコード
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <functional> #include <bitset> using namespace std; using lint = long long int; long long int INF = 1001001001001001LL; int inf = 1000000007; long long int MOD = 1000000007LL; double PI = 3.1415926535897932; template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;} template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;} #define ALL(a) a.begin(),a.end() #define RALL(a) a.rbegin(),a.rend() /* do your best */ vector<lint> culc(vector<lint> a) { int n = a.size(); lint m = 100 * 1000; vector<vector<lint>> dp(n + 1, vector<lint> (m + 1, 0)); dp[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j <= m; j++) { if (dp[i][j] == 0) continue; dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= MOD; dp[i + 1][j + a[i]] += dp[i][j]; dp[i + 1][j + a[i]] %= MOD; } } return dp[n]; } // 抽象累積和 // 構築 O(n), get O(1) template<typename T> struct CumSum{ private: size_t n; vector<T> dat; public: CumSum(const vector<T> &v){ n = v.size(); dat.resize(n + 1, 0); for(size_t i = 0; i < n; i++){ dat[i + 1] = dat[i] + v[i]; dat[i + 1] %= MOD; } } T get(size_t r) const { // 0-indexed, [0. r) return dat[r]; } T get(size_t l, size_t r){ // 0-indexed, [l, r) return (dat[r] - dat[l] + MOD) % MOD; } }; int main() { int n, m; cin >> n >> m; vector<lint> v(n); vector<lint> r(m); for (int i = 0; i < n; i++) { cin >> v[i]; } for (int i = 0; i < m; i++) { cin >> r[i]; } lint a, b; cin >> a >> b; auto dp1 = culc(v); auto dp2 = culc(r); CumSum<lint> acc(dp1); for (int i = 1; i <= 100 * 1000; i++) { dp1[i] += dp1[i - 1]; dp1[i] %= MOD; } // 抵抗を決め打ち lint ans = 0; for (int r = 1; r <= 100 * 1000; r++) { // 範囲が決ま lint lb = a * r; lint rb = b * r; if (100 * 1000 < lb) { continue; } rb = min(rb, 100 * 1000LL); lint sum = (dp1[rb] - dp1[lb - 1] + MOD) % MOD; lint sum2 = acc.get(lb, rb + 1); assert(sum == sum2); ans += sum * dp2[r]; ans %= MOD; } cout << ans << endl; return 0; }