結果

問題 No.390 最長の数列
ユーザー lam6er
提出日時 2025-03-20 21:01:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,524 ms / 5,000 ms
コード長 1,143 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 104,692 KB
最終ジャッジ日時 2025-03-20 21:01:16
合計ジャッジ時間 9,688 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    s = list(map(int, data[1:n+1]))
    sorted_s = sorted(s)
    if not sorted_s:
        print(0)
        return
    max_x = sorted_s[-1]
    
    # Presence array
    present = [False] * (max_x + 2)
    for x in sorted_s:
        present[x] = True
    
    # DP array
    dp = {}
    max_len = 1  # Minimum sequence length is 1
    
    for x in sorted_s:
        current_max = 0
        factors = set()
        sqrt_x = math.isqrt(x)
        for i in range(1, sqrt_x + 1):
            if x % i == 0:
                if i < x and present[i]:
                    factors.add(i)
                counterpart = x // i
                if counterpart != i and counterpart < x and present[counterpart]:
                    factors.add(counterpart)
        # Check for possible factors
        for d in factors:
            if dp[d] > current_max:
                current_max = dp[d]
        dp[x] = current_max + 1
        if dp[x] > max_len:
            max_len = dp[x]
    
    print(max_len)

if __name__ == '__main__':
    main()
0