結果
問題 | No.2218 Multiple LIS |
ユーザー |
![]() |
提出日時 | 2023-02-17 21:45:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 221 ms / 3,000 ms |
コード長 | 1,362 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 89,088 KB |
最終ジャッジ日時 | 2024-07-19 12:55:17 |
合計ジャッジ時間 | 5,509 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
class PrimeNumbers: def __init__(self,nmax): rootnmax = isqrt(nmax) self.prime_judgement = [True]*(rootnmax+1) self.prime_judgement[0] = self.prime_judgement[1] = False for i in range(2,rootnmax+1): if self.prime_judgement[i]: for j in range(2,rootnmax//i+1): self.prime_judgement[i*j] = False self.prime_list = [] for i,flag in enumerate(self.prime_judgement): if flag: self.prime_list.append(i) def prime_factorization(self,n): return_list = [] for i in self.prime_list: if n==1 or i*i>n: break if n%i==0: return_list.append([i,0]) while n%i==0: return_list[-1][1] += 1; n //= i if n!=1: return_list.append([n,1]) return return_list def divisors_enumeration(self,n): divisors = [1] for p,v in self.prime_factorization(n): for i in range(len(divisors)): for j in range(v): divisors.append(divisors[i]*p**(j+1)) return divisors def isqrt(n): m = int(n**0.5) if m**2>n: m -= 1 return m n = int(input()) dp = [0]*(10**5+1) pn = PrimeNumbers(10**5) for v in map(int,input().split()): m = 0 for d in pn.divisors_enumeration(v): m = max(m,dp[d]) dp[v] = max(dp[v],m+1) print(max(dp))