結果

問題 No.390 最長の数列
コンテスト
ユーザー elphe
提出日時 2026-02-11 13:41:15
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 38 ms / 5,000 ms
コード長 918 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,184 ms
コンパイル使用メモリ 203,604 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-11 13:41:38
合計ジャッジ時間 22,587 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin().lock()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    let n: usize = stdin.next().unwrap().parse().unwrap();
    let x: Vec<u32> = (0..n)
        .map(|_| stdin.next().unwrap().parse().unwrap())
        .collect();

    use std::io::Write;
    std::io::stdout()
        .lock()
        .write_all(output(solve(x)).as_bytes())
        .unwrap();
}

fn solve(mut x: Vec<u32>) -> u32 {
    x.sort_unstable();
    let x = x;
    
    let mut count_at = vec![0; 1_000_001];
    x.into_iter().map(|x| {
        count_at[x as usize] += 1;
        let cur_count = count_at[x as usize];
        ((x * 2)..).step_by(x as usize).take_while(|&i| i <= 1_000_000).for_each(|i| count_at[i as usize] = count_at[i as usize].max(cur_count));
        cur_count
    }).max().unwrap()
}

fn output(ans: u32) -> String {
    ans.to_string() + "\n"
}
0