結果
問題 | No.2218 Multiple LIS |
ユーザー |
![]() |
提出日時 | 2023-02-17 21:46:44 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 3,000 ms |
コード長 | 640 bytes |
コンパイル時間 | 9,101 ms |
コンパイル使用メモリ | 277,052 KB |
最終ジャッジ日時 | 2025-02-10 16:39:55 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; void solve() { } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; constexpr int K = 100005; vector<int> dp(N, 1), lst(K, -1); for( int i = 0; i < N; i++ ) { int A; cin >> A; vector<int> d; for( int p = 1; p*p <= A; p++ ) { if( A%p == 0 ) { d.emplace_back(p); d.emplace_back(A/p); } } for( int& d_ : d ) { if( lst[d_] != -1 ) { dp[i] = max(dp[i], dp[lst[d_]]+1); } } lst[A] = i; } cout << *max_element(dp.begin(), dp.end()) << endl; }