結果

問題 No.1368 サイクルの中に眠る門松列
ユーザー BrightLightBrightLight
提出日時 2021-01-29 23:56:07
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 1,922 bytes
コンパイル時間 12,832 ms
コンパイル使用メモリ 379,672 KB
実行使用メモリ 12,320 KB
最終ジャッジ日時 2024-06-27 10:13:15
合計ジャッジ時間 12,712 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 30 ms
5,376 KB
testcase_03 AC 6 ms
5,376 KB
testcase_04 AC 10 ms
5,376 KB
testcase_05 AC 18 ms
12,192 KB
testcase_06 AC 18 ms
12,320 KB
testcase_07 AC 16 ms
12,196 KB
testcase_08 AC 18 ms
12,320 KB
testcase_09 AC 16 ms
10,140 KB
testcase_10 AC 16 ms
10,140 KB
testcase_11 AC 15 ms
10,136 KB
testcase_12 AC 15 ms
10,140 KB
testcase_13 AC 16 ms
10,264 KB
testcase_14 AC 16 ms
10,140 KB
testcase_15 AC 15 ms
10,140 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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