結果
問題 | No.390 最長の数列 |
ユーザー | @abcde |
提出日時 | 2019-04-30 22:37:58 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 61 ms / 5,000 ms |
コード長 | 1,553 bytes |
コンパイル時間 | 1,274 ms |
コンパイル使用メモリ | 162,600 KB |
実行使用メモリ | 7,756 KB |
最終ジャッジ日時 | 2024-06-10 02:58:09 |
合計ジャッジ時間 | 2,515 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 36 ms
6,940 KB |
testcase_06 | AC | 61 ms
7,632 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,944 KB |
testcase_10 | AC | 46 ms
7,756 KB |
testcase_11 | AC | 43 ms
7,756 KB |
testcase_12 | AC | 43 ms
7,628 KB |
testcase_13 | AC | 29 ms
7,688 KB |
testcase_14 | AC | 35 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 4 ms
6,940 KB |
testcase_17 | AC | 6 ms
7,280 KB |
testcase_18 | AC | 7 ms
7,396 KB |
ソースコード
#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; }