結果

問題 No.1368 サイクルの中に眠る門松列
コンテスト
ユーザー BrightLight
提出日時 2021-01-29 23:56:07
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 1,922 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,832 ms
コンパイル使用メモリ 379,672 KB
実行使用メモリ 12,320 KB
最終ジャッジ日時 2024-06-27 10:13:15
合計ジャッジ時間 12,712 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::cmp;

fn main() {
    let t: usize = read();

    for _ in 0..t {
        let n: usize = read();
        let mut a: Vec<usize> = read_vec();
        a.push(a[0]);
        a.push(a[1]);

        let mut v: Vec<usize> = Vec::new();
        for i in 0..n {
            let ac: Vec<usize> = vec![a[i], a[i + 1], a[i + 2]];

            if ac[0] != ac[1] && ac[0] != ac[2] && ac[1] != ac[2] 
             && ((ac[0] < ac[1] && ac[2] < ac[1]) || (ac[0] > ac[1] && ac[2] > ac[1])) {
                v.push(ac[0]);
            } else {
                v.push(0);
            }
        }

        let v0 = &v[0..v.len() - 2];
        let v1 = &v[1..v.len() - 1];
        let v2 = &v[2..];

        let mut dp0: Vec<usize> = Vec::new();
        let mut dp1: Vec<usize> = Vec::new();
        let mut dp2: Vec<usize> = Vec::new();

        dp0.push(v0[0]);
        dp1.push(v1[0]);
        dp2.push(v2[0]);

        if v.len() > 3 {
            dp0.push(cmp::max(v0[1], dp0[0]));
            dp1.push(cmp::max(v1[1], dp1[0]));
            dp2.push(cmp::max(v2[1], dp2[0]));
        }

        if v.len() > 4 {
            dp0.push(cmp::max(v0[2], dp0[1]));
            dp1.push(cmp::max(v1[2], dp1[1]));
            dp2.push(cmp::max(v2[2], dp2[1]));
        }

        for i in 3..v.len() - 2 {
            dp0.push(cmp::max(dp0[i - 1], dp0[i - 3] + v0[i]));
            dp1.push(cmp::max(dp1[i - 1], dp1[i - 3] + v1[i]));
            dp2.push(cmp::max(dp2[i - 1], dp2[i - 3] + v2[i]));
        }

        let ans = cmp::max(dp0[v.len() - 3], cmp::max(dp1[v.len() - 3], dp2[v.len() - 3]));
        println!("{}", ans);
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}
0