結果
問題 | No.979 Longest Divisor Sequence |
ユーザー | set0gut1 |
提出日時 | 2020-01-31 22:20:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,259 bytes |
コンパイル時間 | 977 ms |
コンパイル使用メモリ | 100,004 KB |
実行使用メモリ | 14,624 KB |
最終ジャッジ日時 | 2024-09-17 08:43:06 |
合計ジャッジ時間 | 2,600 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
5,248 KB |
testcase_01 | AC | 9 ms
5,248 KB |
testcase_02 | AC | 10 ms
5,376 KB |
testcase_03 | WA | - |
testcase_04 | AC | 9 ms
5,376 KB |
testcase_05 | AC | 10 ms
5,376 KB |
testcase_06 | AC | 9 ms
5,376 KB |
testcase_07 | AC | 9 ms
5,376 KB |
testcase_08 | AC | 10 ms
5,376 KB |
testcase_09 | AC | 9 ms
5,376 KB |
testcase_10 | AC | 15 ms
5,376 KB |
testcase_11 | AC | 15 ms
5,376 KB |
testcase_12 | AC | 15 ms
5,376 KB |
testcase_13 | AC | 29 ms
5,376 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
ソースコード
#include <algorithm> #include <bitset> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #define MOD (1000000007l) #define ll long long #define rep(i, n) for (ll i = 0; i < (n); i++) using namespace std; void solve() { ll N; cin >> N; ll P = 300010; vector<bool> primes_vec(P+1, true); primes_vec[0] = false; primes_vec[1] = false; for (ll i = 2; i <= P / 2; i++) { if (not primes_vec[i]) continue; for (ll j = 2; i * j <= P; j++) primes_vec[i*j] = false; } set<ll> primes; rep (i, P+1) if (primes_vec[i]) primes.insert(i); unordered_map<ll, ll> memo; rep (i, N) { ll A; cin >> A; if (A == 1) memo[1] = 1; else if (memo[A] == 0 or memo[A] == 1) memo[A] = memo[1] + 1; for (auto it: primes) { if (it * it > A) break; if (A % it) continue; ll tmp = max(memo[it] + 1, memo[A / it] + 1); if (tmp > memo[A]) memo[A] = tmp; } } ll ans = 0; for (auto it: memo) if (ans < it.second) ans = it.second; cout << ans << endl; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); cout.precision(12); cout << fixed; solve(); return 0; }