結果

問題 No.1368 サイクルの中に眠る門松列
ユーザー BrightLightBrightLight
提出日時 2021-01-29 23:56:07
言語 Rust
(1.72.1)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 1,922 bytes
コンパイル時間 3,465 ms
コンパイル使用メモリ 144,216 KB
実行使用メモリ 12,220 KB
最終ジャッジ日時 2023-09-09 17:32:34
合計ジャッジ時間 5,562 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 32 ms
4,380 KB
testcase_03 AC 7 ms
4,376 KB
testcase_04 AC 12 ms
4,376 KB
testcase_05 AC 22 ms
12,172 KB
testcase_06 AC 22 ms
12,172 KB
testcase_07 AC 21 ms
12,168 KB
testcase_08 AC 22 ms
12,220 KB
testcase_09 AC 20 ms
10,216 KB
testcase_10 AC 20 ms
10,208 KB
testcase_11 AC 20 ms
10,324 KB
testcase_12 AC 20 ms
10,300 KB
testcase_13 AC 20 ms
10,304 KB
testcase_14 AC 20 ms
10,284 KB
testcase_15 AC 20 ms
10,292 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