結果
問題 | No.390 最長の数列 |
ユーザー | hanorver |
提出日時 | 2016-07-09 09:58:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 108 ms / 5,000 ms |
コード長 | 827 bytes |
コンパイル時間 | 871 ms |
コンパイル使用メモリ | 84,772 KB |
実行使用メモリ | 15,768 KB |
最終ジャッジ日時 | 2024-10-02 10:40:25 |
合計ジャッジ時間 | 2,352 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
11,136 KB |
testcase_01 | AC | 6 ms
11,008 KB |
testcase_02 | AC | 7 ms
11,104 KB |
testcase_03 | AC | 8 ms
11,008 KB |
testcase_04 | AC | 7 ms
11,104 KB |
testcase_05 | AC | 88 ms
15,728 KB |
testcase_06 | AC | 108 ms
15,744 KB |
testcase_07 | AC | 6 ms
11,136 KB |
testcase_08 | AC | 7 ms
11,008 KB |
testcase_09 | AC | 7 ms
11,112 KB |
testcase_10 | AC | 95 ms
15,688 KB |
testcase_11 | AC | 94 ms
15,748 KB |
testcase_12 | AC | 94 ms
15,768 KB |
testcase_13 | AC | 61 ms
14,720 KB |
testcase_14 | AC | 87 ms
15,724 KB |
testcase_15 | AC | 7 ms
10,992 KB |
testcase_16 | AC | 7 ms
11,008 KB |
testcase_17 | AC | 9 ms
11,248 KB |
testcase_18 | AC | 11 ms
11,392 KB |
ソースコード
#include<iostream> #include<cmath> #include<vector> #include<set> #include<algorithm> int main() { int n; const int MAX = 1000000; std::vector<int> v(MAX + 1), v2(MAX + 1); std::set<int> s; std::cin >> n; for (int i = 0; i < n; i++) { int value; std::cin >> value; v[value]++; s.insert(value); } int max = *std::max_element(s.begin(), s.end()), min = *std::min_element(s.begin(), s.end()); for (int val : s) { //std::cout << val << std::endl; v2[val] = std::max(1, v2[val]); for (int i = 2; val * i <= max; i++) { if (v[val * i] == 1) { v2[val * i] = std::max(v2[val] + 1, v2[val * i]); } } } //for (int i = 0; i <= max; i++) { // if (v2[i] > 0) { // std::cout << v2[i] << std::endl; // } //} std::cout << *std::max_element(v2.begin(), v2.end()) << std::endl; return 0; }