提出 #48193921

ソースコード 拡げる

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [i64; n],
        pqlr: [(i64, Usize1, usize, usize); m],
    };
    let mut plr = vec![vec![]; n + 1];
    for (p, q, l, r) in pqlr {
        plr[q].push((p, l, r));
    }

    let inf = 1_i64 << 60;
    let mut ans = 0_i64;
    for k in 0..3 {
        let mut dp = vec![vec![-inf, -inf, -inf]; n + 1];
        dp[0][0] = 0_i64;
        for (p, l, r) in plr[0].iter().copied() {
            if l == 0 && (l + r) % 3 == k {
                dp[0][0] += p;
            }
        }
        for (i, plr_i) in plr.iter().enumerate().skip(1) {
            for j in 0..3 {
                dp[i][j] = (dp[i - 1][(j + 3 - 1) % 3] + a[i - 1]).max(dp[i - 1][j]);
                for (p, l, r) in plr_i.iter().copied() {
                    if l == j && (l + r) % 3 == k {
                        dp[i][j] += p;
                    }
                }
            }
        }
        ans = ans.max(dp[n][k]);
    }
    println!("{}", ans);
}

提出情報

提出日時
問題 L - 展覧会
ユーザ bouzuya
言語 Rust (rustc 1.70.0)
得点 6
コード長 1042 Byte
結果 AC
実行時間 59 ms
メモリ 30268 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 6 / 6
結果
AC × 3
AC × 24
セット名 テストケース
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt
ケース名 結果 実行時間 メモリ
example_00.txt AC 1 ms 1912 KiB
example_01.txt AC 1 ms 2068 KiB
example_02.txt AC 1 ms 1860 KiB
test_00.txt AC 52 ms 30268 KiB
test_01.txt AC 59 ms 29796 KiB
test_02.txt AC 58 ms 29696 KiB
test_03.txt AC 59 ms 29692 KiB
test_04.txt AC 58 ms 29648 KiB
test_05.txt AC 29 ms 14528 KiB
test_06.txt AC 12 ms 8100 KiB
test_07.txt AC 18 ms 10464 KiB
test_08.txt AC 36 ms 19952 KiB
test_09.txt AC 26 ms 13888 KiB
test_10.txt AC 32 ms 16552 KiB
test_11.txt AC 28 ms 14892 KiB
test_12.txt AC 35 ms 18512 KiB
test_13.txt AC 47 ms 22916 KiB
test_14.txt AC 32 ms 16752 KiB
test_15.txt AC 51 ms 26020 KiB
test_16.txt AC 38 ms 18872 KiB
test_17.txt AC 25 ms 13712 KiB
test_18.txt AC 39 ms 20372 KiB
test_19.txt AC 25 ms 13420 KiB
test_20.txt AC 47 ms 23788 KiB