結果

問題 No.390 最長の数列
コンテスト
ユーザー @abcde
提出日時 2019-04-30 22:37:58
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 73 ms / 5,000 ms
コード長 1,553 bytes
コンパイル時間 1,481 ms
コンパイル使用メモリ 161,324 KB
実行使用メモリ 7,756 KB
最終ジャッジ日時 2024-12-31 10:57:25
合計ジャッジ時間 3,095 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int LIMIT = 1e6 + 1;
int DP[LIMIT];

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    int X[N];
    int debug = 0;
    for(int i = 0; i < N; i++){
        int x;
        cin >> x;
        X[i] = x;
        DP[x] = 1;
        debug++;
    }
    // DP[x]++; と記載すると, 何故か, DP[1000000]=80 のように出力される場合があった
    // ため, DP[x] = 1 のように修正.
    // cout << "DP[1000000]=" << DP[1000000] << endl;
    sort(X, X + N);
    
    // 2. 良い数列を選定.
    int ans = 0;
    for(int i = 0; i < N; i++){
        int u1 = X[N - 1] / X[i] + 1;
        int u2 = N - 1 - i;
        if(u1 >= u2){
           for(int j = i + 1; j < N; j++){
               if(X[j] % X[i] == 0) DP[X[j]] = max(DP[X[j]], DP[X[i]] + 1);
               debug++;
           }
        }
        if(u1 < u2){
           for(int j = 2; j < u1; j++){
               if(DP[X[i] * j] > 0) DP[X[i] * j] = max(DP[X[i] * j], DP[X[i]] + 1);
               debug++;
           }
        }
    }
    
    // 3. 良い数列の長さの最大値は？
    for(int i = 0; i < X[N - 1] + 1; i++) ans = max(ans, DP[i]), debug++;
    // ex.
    // [入力値]
    // 10000
    // 1 2 ..... 9999 1000000
    // -> debug=6576739, 1 2 4 8 16 32 64 128 256 512 1024 2048 4196 8192 の 長さ14.
    // -> 31[ms] 程度だったので, 何とかなりそう？？？
    // cout << "debug=" << debug << endl;

    // 4. 出力.
    cout << ans << endl;
    return 0;
    
}
0