結果
問題 | No.390 最長の数列 |
ユーザー |
|
提出日時 | 2022-12-06 19:42:41 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,188 bytes |
コンパイル時間 | 135 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 26,056 KB |
最終ジャッジ日時 | 2024-10-13 08:28:46 |
合計ジャッジ時間 | 6,880 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 1 TLE * 1 -- * 13 |
ソースコード
from collections import deque def is_multiple_except_self(num, base) -> True: return num % base == 0 and num != base def main(): N = int(input()) x = list(map(int, input().split())) x.sort() multiple_set = {} searching = deque() for idx, elm in enumerate(x): if elm in multiple_set: continue multiple_set[elm] = list( filter(lambda num: is_multiple_except_self(num, elm), x[idx:])) searching = deque((num, elm) for num in multiple_set[elm]) while searching: current = searching.popleft() if current[0] in multiple_set: continue multiple_set[current[0]] = list( filter(lambda num: is_multiple_except_self( num, current[0]), multiple_set[current[1]])) searching.extendleft((num, current[0]) for num in multiple_set[current[0]]) dp_table = {num: 1 for num in x} for num in x: for dest in multiple_set[num]: dp_table[dest] = max(dp_table[dest], dp_table[num]+1) print(max(dp_table.values())) if __name__ == "__main__": main()