結果
問題 | No.979 Longest Divisor Sequence |
ユーザー | r1933 |
提出日時 | 2020-02-04 18:31:14 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,267 ms / 2,000 ms |
コード長 | 3,516 bytes |
コンパイル時間 | 1,709 ms |
コンパイル使用メモリ | 168,276 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-21 07:35:53 |
合計ジャッジ時間 | 4,086 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,944 KB |
testcase_02 | AC | 4 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,944 KB |
testcase_04 | AC | 4 ms
6,944 KB |
testcase_05 | AC | 4 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,944 KB |
testcase_08 | AC | 4 ms
6,940 KB |
testcase_09 | AC | 4 ms
6,944 KB |
testcase_10 | AC | 16 ms
6,944 KB |
testcase_11 | AC | 16 ms
6,940 KB |
testcase_12 | AC | 16 ms
6,940 KB |
testcase_13 | AC | 21 ms
6,940 KB |
testcase_14 | AC | 1,267 ms
6,944 KB |
testcase_15 | AC | 422 ms
6,940 KB |
ソースコード
#include "bits/stdc++.h" #pragma GCC optimize("Ofast") // Begin Header {{{ using namespace std; #ifndef DEBUG #define dump(...) #endif #define all(x) x.begin(), x.end() #define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i) #define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template <class T> using MaxHeap = priority_queue<T, vector<T>, less<T>>; template <class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>; inline void input() {} template <class Head, class... Tail> inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward<Tail>(tail)...); } template <class T> inline void input(vector<T> &vec) { for (auto &e: vec) { cin >> e; } } template <class T> inline void input(vector<vector<T>> &mat) { for (auto &vec: mat) { input(vec); } } inline void print() { cout << "\n"; } template <class Head, class... Tail> inline void print(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) { cout << ' '; } print(forward<Tail>(tail)...); } template <class T> inline ostream& operator<<(ostream &strm, const vector<T> &vec) { static constexpr const char *delim[] = {" ", ""}; for (const auto &e: vec) { strm << e << delim[&e == &vec.back()]; } return strm; } template <class T> inline vector<T> make_v(const T &initValue, size_t sz) { return vector<T>(sz, initValue); } template <class T, class... Args> inline auto make_v(const T &initValue, size_t sz, Args... args) { return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...)); } template <class Func> class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {} template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward<Args>(args)...); } }; template <class Func> static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint<Func>{forward<Func>(f)}; } template <class T> inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true); } template <class T> inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true); } template <class T> inline T diff(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } // }}} signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); var(size_t, N); intmax_t res = 0; vector<intmax_t> dp(size_t(3e5) + 1); rep(i, N) { var(intmax_t, a); if (a == 1) { dp[a] = 1; } else { for (intmax_t i = 1; i * i <= a; ++i) { if (a % i == 0) { chmax(dp[a], dp[i] + 1); if (a / i != a) { chmax(dp[a], dp[a / i] + 1); } } } } chmax(res, dp[a]); } print(res); return 0; }