結果
問題 | No.2855 Move on Grid |
ユーザー | QiToY |
提出日時 | 2024-08-25 13:58:07 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 157 ms / 3,000 ms |
コード長 | 1,961 bytes |
コンパイル時間 | 11,997 ms |
コンパイル使用メモリ | 400,800 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 13:58:37 |
合計ジャッジ時間 | 17,588 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
6,812 KB |
testcase_01 | AC | 48 ms
6,816 KB |
testcase_02 | AC | 30 ms
6,940 KB |
testcase_03 | AC | 22 ms
6,940 KB |
testcase_04 | AC | 15 ms
6,940 KB |
testcase_05 | AC | 33 ms
6,940 KB |
testcase_06 | AC | 31 ms
6,940 KB |
testcase_07 | AC | 4 ms
6,940 KB |
testcase_08 | AC | 26 ms
6,944 KB |
testcase_09 | AC | 11 ms
6,944 KB |
testcase_10 | AC | 113 ms
6,944 KB |
testcase_11 | AC | 111 ms
6,940 KB |
testcase_12 | AC | 109 ms
6,940 KB |
testcase_13 | AC | 109 ms
6,944 KB |
testcase_14 | AC | 109 ms
6,940 KB |
testcase_15 | AC | 107 ms
6,940 KB |
testcase_16 | AC | 107 ms
6,944 KB |
testcase_17 | AC | 113 ms
6,940 KB |
testcase_18 | AC | 112 ms
6,944 KB |
testcase_19 | AC | 114 ms
6,944 KB |
testcase_20 | AC | 157 ms
6,944 KB |
testcase_21 | AC | 131 ms
6,944 KB |
testcase_22 | AC | 157 ms
6,940 KB |
testcase_23 | AC | 156 ms
6,940 KB |
testcase_24 | AC | 157 ms
6,944 KB |
testcase_25 | AC | 136 ms
6,940 KB |
testcase_26 | AC | 156 ms
6,940 KB |
testcase_27 | AC | 132 ms
6,944 KB |
testcase_28 | AC | 150 ms
6,940 KB |
testcase_29 | AC | 156 ms
6,944 KB |
testcase_30 | AC | 137 ms
6,940 KB |
testcase_31 | AC | 135 ms
6,944 KB |
testcase_32 | AC | 133 ms
6,944 KB |
testcase_33 | AC | 132 ms
6,944 KB |
testcase_34 | AC | 130 ms
6,944 KB |
testcase_35 | AC | 130 ms
6,940 KB |
testcase_36 | AC | 131 ms
6,940 KB |
testcase_37 | AC | 134 ms
6,940 KB |
testcase_38 | AC | 136 ms
6,944 KB |
testcase_39 | AC | 132 ms
6,940 KB |
ソースコード
#![allow(unused_imports)] fn main() { input! { n: usize, m: usize, k: usize, a: [[i64; m]; n], } let (mut ok, mut ng) = (0i64, 1_000_000_001); while ok.abs_diff(ng) > 1 { let mid = (ok + ng) / 2; let mut b = mvec![0; (n, m)]; for i in 0..n { for j in 0..m { if a[i][j] < mid { b[i][j] = 1; } } } let mut q = VecDeque::<(usize, usize)>::new(); let mut cost = mvec![1<<30; (n, m)]; cost[0][0] = b[0][0]; q.push_back((0, 0)); while let Some((i, j)) = q.pop_front() { for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)] { let ni = i.wrapping_add_signed(di); let nj = j.wrapping_add_signed(dj); if ni < n && nj < m && chmin!(cost[ni][nj], cost[i][j] + b[ni][nj]) { if b[ni][nj] == 0 { q.push_front((ni, nj)); } else { q.push_back((ni, nj)); } } } } *if cost[n - 1][m - 1] <= k { &mut ok } else { &mut ng } = mid; } println!("{ok}"); } use proconio::{input, marker::*}; use std::{cmp::Reverse, collections::*}; #[macro_export] macro_rules! chmax { ($a:expr, $b:expr) => {{ let tmp = $b; if $a < tmp { $a = tmp; true } else { false } }}; } #[macro_export] macro_rules! chmin { ($a:expr, $b:expr) => {{ let tmp = $b; if $a > tmp { $a = tmp; true } else { false } }}; } #[macro_export] /// mvec![] macro_rules! mvec { ($val:expr; ()) => { $val }; ($val:expr; ($size:expr $(,$rest:expr)*)) => { vec![mvec![$val; ($($rest),*)]; $size] }; }