結果
問題 | No.1532 Different Products |
ユーザー | sten_san |
提出日時 | 2021-06-04 22:44:57 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,209 ms / 4,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 4,651 ms |
コンパイル使用メモリ | 218,184 KB |
実行使用メモリ | 67,768 KB |
最終ジャッジ日時 | 2023-08-12 16:07:51 |
合計ジャッジ時間 | 45,542 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 205 ms
15,272 KB |
testcase_02 | AC | 2 ms
4,384 KB |
testcase_03 | AC | 1 ms
4,384 KB |
testcase_04 | AC | 1 ms
4,384 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 3 ms
4,380 KB |
testcase_08 | AC | 6 ms
4,384 KB |
testcase_09 | AC | 60 ms
7,028 KB |
testcase_10 | AC | 260 ms
17,368 KB |
testcase_11 | AC | 196 ms
13,664 KB |
testcase_12 | AC | 613 ms
35,576 KB |
testcase_13 | AC | 319 ms
21,956 KB |
testcase_14 | AC | 970 ms
53,752 KB |
testcase_15 | AC | 9 ms
4,388 KB |
testcase_16 | AC | 242 ms
16,964 KB |
testcase_17 | AC | 196 ms
13,156 KB |
testcase_18 | AC | 133 ms
11,056 KB |
testcase_19 | AC | 596 ms
34,404 KB |
testcase_20 | AC | 985 ms
55,072 KB |
testcase_21 | AC | 339 ms
19,936 KB |
testcase_22 | AC | 380 ms
24,924 KB |
testcase_23 | AC | 177 ms
13,676 KB |
testcase_24 | AC | 914 ms
51,192 KB |
testcase_25 | AC | 524 ms
32,408 KB |
testcase_26 | AC | 68 ms
7,356 KB |
testcase_27 | AC | 462 ms
27,672 KB |
testcase_28 | AC | 348 ms
22,400 KB |
testcase_29 | AC | 345 ms
21,012 KB |
testcase_30 | AC | 617 ms
35,768 KB |
testcase_31 | AC | 615 ms
35,824 KB |
testcase_32 | AC | 697 ms
38,916 KB |
testcase_33 | AC | 555 ms
33,280 KB |
testcase_34 | AC | 842 ms
44,628 KB |
testcase_35 | AC | 692 ms
38,572 KB |
testcase_36 | AC | 826 ms
42,776 KB |
testcase_37 | AC | 219 ms
14,516 KB |
testcase_38 | AC | 880 ms
47,944 KB |
testcase_39 | AC | 780 ms
41,600 KB |
testcase_40 | AC | 801 ms
41,800 KB |
testcase_41 | AC | 1,142 ms
62,744 KB |
testcase_42 | AC | 1,012 ms
56,044 KB |
testcase_43 | AC | 1,060 ms
58,824 KB |
testcase_44 | AC | 1,182 ms
66,732 KB |
testcase_45 | AC | 1,190 ms
66,692 KB |
testcase_46 | AC | 1,133 ms
61,580 KB |
testcase_47 | AC | 1,209 ms
67,664 KB |
testcase_48 | AC | 1,174 ms
66,800 KB |
testcase_49 | AC | 1,183 ms
66,920 KB |
testcase_50 | AC | 1,173 ms
66,672 KB |
testcase_51 | AC | 1,184 ms
67,412 KB |
testcase_52 | AC | 1,159 ms
66,348 KB |
testcase_53 | AC | 1,203 ms
67,648 KB |
testcase_54 | AC | 1,157 ms
66,472 KB |
testcase_55 | AC | 1,182 ms
67,036 KB |
testcase_56 | AC | 1,127 ms
61,404 KB |
testcase_57 | AC | 1,136 ms
62,292 KB |
testcase_58 | AC | 1,183 ms
66,600 KB |
testcase_59 | AC | 1,092 ms
60,384 KB |
testcase_60 | AC | 1,201 ms
67,768 KB |
testcase_61 | AC | 1 ms
4,384 KB |
testcase_62 | AC | 1 ms
4,380 KB |
testcase_63 | AC | 1,187 ms
66,680 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct iofast_t { iofast_t() { ios::sync_with_stdio(false); cin.tie(nullptr); } } iofast; struct uns_t {} uns; template <typename Element, typename Head, typename ...Args> auto vec(Element init, Head arg, Args ...args) { if constexpr (sizeof...(Args) == 0) return std::vector(arg, init); else return std::vector(arg, vec(init, args...)); } template <typename Element, typename Head, typename ...Args> auto vec(uns_t, Head arg, Args ...args) { return vec(Element(), arg, args...); } template <typename T, typename Compare = less<T>> T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); } template <typename T, typename Compare = less<T>> T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); } int main() { int64_t n, k; cin >> n >> k; auto update = vec<int64_t>(uns, n + 1, 0); update[n].push_back(k); for (int i = n; 0 < i; --i) { auto s = vec<int64_t>(uns, 0); for (auto v : update[i]) { s.push_back(v); s.push_back(v / i); } sort(begin(s), end(s)); s.erase(unique(begin(s), end(s)), end(s)); for (auto v : s) { update[i - 1].push_back(v); } } unordered_map<int64_t, int64_t> dp1; for (auto v : update[0]) { dp1[v] = 0 < v; } for (int i = 1; i <= n; ++i) { unordered_map<int64_t, int64_t> dp2; for (auto v : update[i]) { dp2[v] = dp1[v] + dp1[v / i]; } swap(dp1, dp2); } cout << dp1[k] - 1 << endl; }