結果
問題 | No.979 Longest Divisor Sequence |
ユーザー |
![]() |
提出日時 | 2020-01-31 22:12:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 478 ms / 2,000 ms |
コード長 | 562 bytes |
コンパイル時間 | 1,472 ms |
コンパイル使用メモリ | 169,524 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-09-17 08:30:56 |
合計ジャッジ時間 | 2,782 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } int main() { int n = ri(); int a[n]; for (auto &i : a) i = ri(); static int max[300001]; for (int i = 0; i < n; i++) { std::vector<int> divs; for (int j = 1; j * j <= a[i]; j++) { if (a[i] % j == 0) { if (j != a[i]) divs.push_back(j); if (j > 1) divs.push_back(a[i] / j); } } int cur = 0; for (auto j : divs) cur = std::max(cur, max[j]); max[a[i]] = std::max(max[a[i]], cur + 1); } printf("%d\n", *std::max_element(max, max + 300001)); return 0; }