結果

問題 No.2982 Logic Battle
ユーザー Yukino DX.
提出日時 2024-12-28 13:11:16
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,772 ms / 2,000 ms
コード長 1,253 bytes
コンパイル時間 26,400 ms
コンパイル使用メモリ 376,396 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-28 13:12:27
合計ジャッジ時間 64,872 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #

use proconio::input;

fn main() {
    input! {
        n:usize,
        a:[[usize;3];n],
    }
    const M: usize = 5000;
    const INF: i64 = std::i64::MAX;

    let mut dp = vec![vec![0; 3]; M + 1];
    for i in 1..=M {
        for j in 0..3 {
            dp[i][j] = -INF;
        }
    }
    for i in 0..n {
        let mut ndp = vec![vec![-INF; 3]; M + 1];
        for j in 0..=M {
            for k in 0..3 {
                if dp[j][k] == -INF {
                    continue;
                }
                for l in 0..3 {
                    if k == l {
                        continue;
                    }

                    let atk = j + a[i][l] as usize;
                    if M < atk {
                        let over = (atk - M) * (n - i);
                        ndp[M - 1][l] = ndp[M - 1][l].max(dp[j][k] + M as i64 + over as i64);
                    } else {
                        let nj = atk.saturating_sub(1);
                        ndp[nj][l] = ndp[nj][l].max(dp[j][k] + atk as i64);
                    }
                }
            }
        }
        dp = ndp;
    }

    let mut ans = 0;
    for i in 0..=M {
        for j in 0..3 {
            ans = ans.max(dp[i][j]);
        }
    }

    println!("{}", ans);
}
0