結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-08-25 13:58:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#![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]};}