結果
問題 | No.390 最長の数列 |
ユーザー | Daigo HIROOKA |
提出日時 | 2018-07-09 03:14:54 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 674 ms / 5,000 ms |
コード長 | 605 bytes |
コンパイル時間 | 4,732 ms |
コンパイル使用メモリ | 72,192 KB |
実行使用メモリ | 68,856 KB |
最終ジャッジ日時 | 2023-09-22 08:26:25 |
合計ジャッジ時間 | 12,577 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 141 ms
60,060 KB |
testcase_01 | AC | 136 ms
60,556 KB |
testcase_02 | AC | 136 ms
60,092 KB |
testcase_03 | AC | 137 ms
59,864 KB |
testcase_04 | AC | 138 ms
59,980 KB |
testcase_05 | AC | 590 ms
65,436 KB |
testcase_06 | AC | 674 ms
68,856 KB |
testcase_07 | AC | 136 ms
60,076 KB |
testcase_08 | AC | 130 ms
60,280 KB |
testcase_09 | AC | 130 ms
60,376 KB |
testcase_10 | AC | 622 ms
65,732 KB |
testcase_11 | AC | 599 ms
65,468 KB |
testcase_12 | AC | 636 ms
67,096 KB |
testcase_13 | AC | 502 ms
65,224 KB |
testcase_14 | AC | 640 ms
66,360 KB |
testcase_15 | AC | 129 ms
59,956 KB |
testcase_16 | AC | 141 ms
60,104 KB |
testcase_17 | AC | 237 ms
63,912 KB |
testcase_18 | AC | 259 ms
64,912 KB |
ソースコード
import java.util.*; public class No390{ public static void main(String[] args){ int max_x = 1000000; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] x = new int[n]; for(int i = 0; i < n; i++){ x[i] = sc.nextInt(); } Arrays.sort(x); int[] dp = new int[max_x+1]; for(int i:x){ dp[i] = 1; } int ans = 0; for(int i = 0; i <= max_x; i++){ if(dp[i] <= 0){ continue; } for(int j = i*2; j <= max_x; j += i){ if(dp[j] >= 1){ dp[j] = Math.max(dp[j], dp[i]+1); } } ans = Math.max(ans, dp[i]); } System.out.println(ans); } }