結果

問題 No.390 最長の数列
ユーザー vjudge1
提出日時 2025-04-18 00:26:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,756 ms / 5,000 ms
コード長 924 bytes
コンパイル時間 7,047 ms
コンパイル使用メモリ 476,436 KB
実行使用メモリ 74,332 KB
最終ジャッジ日時 2025-04-18 00:27:05
合計ジャッジ時間 14,905 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h> 
#define int long long 
#define MAXN 100005 
using namespace std; 

inline int read(){ 
    int x=0; 
    char c=getchar(); 
    while(c<'0' || c>'9'){ 
        c=getchar(); 
    } 
    while(c>='0' && c<='9'){ 
        x=(x<<1)+(x<<3)+(c^48); 
        c=getchar(); 
    } 
    return x; 
}


vector<int>dp(1e6+5,1); 
map<int,int>mp; 

signed main(){ 
    int n; 
    n=read(); 
    int res=0; 
vector<int>a(n); 
    for(int i=0;i<n;i++){ 
        a[i]=read(); 
    } 
    for(int i=0;i<n;i++){ 
        mp[a[i]]=1; 
    } 
    int maxn=*max_element(a.begin(),a.end()); 
    sort(a.begin(),a.end()); 
    for(int i=0;i<n;i++){ 
        int x=a[i]; 
        int k=2; 
        for(int k=2;x*k<=maxn;k++){ 
            int j=x*k; 
            if(mp[j]){ 
                dp[j]=max(dp[j],dp[x]+1); 
            } 
        } 
    }
    printf("%lld\n",*max_element(dp.begin(),dp.end())); 
    return 0; 
}
0