#697308 (Rust) No.1668 Grayscale

• 問題: No.1668 Grayscale
• ユーザー: 43flyingcar
• 提出日時: 2021-09-09 22:35:42
• 言語: Rust (1.77.0 + proconio)
• 結果: MLE
• 実行時間: -
• コード長: 9,083 bytes
• コンパイル時間: 12,510 ms
• コンパイル使用メモリ: 379,884 KB
• 実行使用メモリ: 796,800 KB
• 最終ジャッジ日時: 2024-06-10 03:16:08
• 合計ジャッジ時間: 16,214 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	0 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	MLE	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-

コンパイルメッセージ

warning: unused import: `std::cmp::min`
 --> src/main.rs:3:5
  |
3 | use std::cmp::min;
  |     ^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::BTreeMap`
 --> src/main.rs:4:5
  |
4 | use std::collections::BTreeMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::process`
 --> src/main.rs:5:5
  |
5 | use std::process;
  |     ^^^^^^^^^^^^

warning: unused import: `std::collections::HashMap`
 --> src/main.rs:7:5
  |
7 | use std::collections::HashMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::collections::BTreeSet`
  --> src/main.rs:10:5
   |
10 | use std::collections::BTreeSet;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::collections::BinaryHeap`
  --> src/main.rs:12:5
   |
12 | use std::collections::BinaryHeap;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused imports: `Hash`, `Hasher`
  --> src/main.rs:13:17
   |
13 | use std::hash::{Hash, Hasher};
   |                 ^^^^  ^^^^^^

warning: unnecessary parentheses around `while` condition
   --> src/main.rs:140:10
    |
140 |     while(b>0){
    |          ^   ^
    |
    = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
    |
140 -     while(b>0){
140 +     while b>0 {
    |

warning: unnecessary parentheses around `while` condition
   --> src/main.rs:156:14
    |
156 |         while(n != 0){
    |              ^      ^
    |
help: remove these parentheses
    |
156 -         while(n != 0){
156 +         while n != 0 {
    |

warning: unnecessary parentheses around `if` condition
   --> src/main.rs:157:16
    |
157 |             if (n&1 == 1){ans = ans*x%MODu;}
    |                ^        ^
    |
help: remove these parentheses
    |
157 -             if (n&1 == 1){ans = ans*x%MODu;}
157 +             if n&1 == 1 {ans = ans*x%MODu;}
    |

warning: type `x` should have an upper camel case name
   --> src/main.rs:177:8
    |
177 | struct x{    
    |       

ソースコード

use std::cmp::Ordering;
use std::cmp;
use std::cmp::min;
use std::collections::BTreeMap;
use std::process;
use std::cmp::Ord;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::mem;
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};

pub struct Scanner<R> {
    stdin: R,
}
 
impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf).unwrap()
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


pub trait BinarySearch<T> {
    fn lower_bound(&self, x:&T) -> usize;
    fn upper_bound(&self, x:&T) -> usize;
}

impl<T: Ord> BinarySearch<T> for VecDeque<T>{
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
impl<T: Ord> BinarySearch<T> for [T]{
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
fn comb(a:usize, b:usize,  fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
        let mut a = a;
        let mut b = b;
        if a == 0 && b == 0{return 1;}
        if a<b || a<0{return 0;}
        let mut tmp = ifac[a-b]*ifac[b]%MODu;
        return tmp * fac[a]%MODu;
}
fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
    return comb(n+r-1, r, fac, ifac);
}
fn modinv(a:usize, M:usize)->usize{
    let mut b = M as i64;
    let mut u = 1 as i64;
    let mut v = 0 as i64;
    let mut a = a as i64;
    let mut m = M as i64;
    while(b>0){
        let mut t = a/b;
        a -= t*b;
        mem::swap(&mut a, &mut b);
        u-=t*v;
        mem::swap(&mut u, &mut v);
    }
    u%=m;
    if u<0{u+=m;}
    return u as usize;

}
fn modpow(x:usize, n:usize) -> usize{
        let mut ans = 1;
        let mut n = n as usize;
        let mut x = x;
        while(n != 0){
            if (n&1 == 1){ans = ans*x%MODu;}
            x = x*x%MODu;
            n = n>>1;
        }
        ans
}
fn invs(max:usize)->(Vec<usize>, Vec<usize>){
    let mut fac = vec![0;max+1];
    let mut ifac = vec![0;max+1];
    fac[0] = 1;
    ifac[0] = 1;
    for i in 0..max{

        fac[i+1] = fac[i] * (i+1)%MODu;
        ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;
    }
    (fac, ifac)
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct x{    
             a:i64,   
             b:i64, 
             c:i64,   
             d:i64,   
}            
impl Ord for x{
    fn cmp(&self, other:&Self)->Ordering{
                 (other.b * (self.a)).cmp(&((self.b)*other.a))
             }        
         }            
         impl PartialOrd for x {
             fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                 Some(self.cmp(other))
             }        
         }          
fn gcd(a:usize, b:usize)->usize{
    if b==0{return a;}
    return gcd(b, a%b);
}
fn solve(){
    let sssss = std::io::stdin();

    let mut sc = Scanner { stdin: sssss.lock() };
    let mut H:usize = sc.read();
    let mut W:usize = sc.read();
    let mut N:usize = sc.read();
    let mut C = vec![vec![0usize;W];H];
    let mut c= vec![vec![];N];
    for i in 0..H{
        for j in 0..W{
            C[i][j] = sc.read();
            C[i][j]-=1;
            c[C[i][j]].push((i, j));
        }
    }
    let mut dp = vec![vec![INFu;N+1];N+1];
    let mut s = 0;
    let mut t = 1;
    let mut used = vec![vec![false;W];H];
    fn add(cc:usize, 
           dx:&Vec<i64>, 
           dy:&Vec<i64>, 
           used:&mut Vec<Vec<bool>>, 
           now:&mut Vec<Vec<usize>>, 
           bad:&mut Vec<HashSet<(usize, usize)>>,
           c:&Vec<Vec<(usize, usize)>>,
           H:usize,
           W:usize,
           C:&Vec<Vec<usize>>
           ){
        for i in 0..c[cc].len(){
            used[c[cc][i].0][c[cc][i].1] = true;
        }
        for i in 0..c[cc].len(){
            for j in 0..4{
                let mut nx = c[cc][i].0 as i64 + dx[j];
                let mut ny = c[cc][i].1 as i64 + dy[j];
                if 0<=nx && nx<H as i64 && 0<=ny && ny<W as i64{
                    let mut nx = nx as usize;
                    let mut ny = ny as usize;
                    if used[nx][ny]{
                        continue;
                    }
                    if now[nx][ny] == 0{
                        bad[C[nx][ny]].insert((nx, ny));
                    }
                    now[nx][ny]+=1;
                }
            }
        }
    }
    fn subtract(cc:usize,
           dx:&Vec<i64>,
           dy:&Vec<i64>,
           used:&mut Vec<Vec<bool>>,
           now:&mut Vec<Vec<usize>>,
           bad:&mut Vec<HashSet<(usize, usize)>>,
           c:&Vec<Vec<(usize, usize)>>,
           H:usize,
           W:usize,
           C:&Vec<Vec<usize>>
           ){
        for i in 0..c[cc].len(){
            for j in 0..4{
                let mut nx = c[cc][i].0 as i64 + dx[j];
                let mut ny = c[cc][i].1 as i64 + dy[j];
                if 0<=nx && nx<H as i64 && 0<=ny && ny<W as i64{
                    let mut nx = nx as usize;
                    let mut ny = ny as usize;
                    if used[nx][ny]{
                        continue;
                    }
                    now[nx][ny]-=1;
                    if now[nx][ny] == 0{
                        bad[C[nx][ny]].remove(&(nx, ny));
                    }
                }
            }

        }
        for i in 0..c[cc].len(){
            used[c[cc][i].0][c[cc][i].1] = false;
        }

    }
    let mut s = 0;
    let mut t = 0;

    let mut bad = vec![HashSet::new();N];
    let mut now = vec![vec![0;W];H];
    let mut dx = vec![0, 0, -1, 1];
    let mut dy = vec![1, -1, 0, 0];
    dp[s][t] = 1;
    let mut span = HashSet::new();
    while(s<N){
        while(t<N && bad[t].len() == 0){
            add(t, &dx, &dy, &mut used, &mut now, &mut bad,&c, H, W, &C);
            t+=1;
            for ss in s..t{

                dp[ss][t] = 1;
                span.insert((ss, t));
            }
        }
        subtract(s, &dx, &dy, &mut used, &mut now, &mut bad,&c, H, W, &C);
        s+=1;
    }
    fn dfs(l:usize, r:usize, dp:&mut Vec<Vec<usize>>, span:&HashSet<(usize, usize)>)->usize{
        let mut res = INFu;
        if dp[l][r]  != INFu{
            return dp[l][r];
        }
        for i in l+1..r{
            if span.contains(&(l, i)){
                res = cmp::min(res, 1+dfs(i, r, dp, span));
            }
            else{
                res = cmp::min(res, i-l+dfs(i, r, dp, span));
            }
        }
        dp[l][r] = res;
        return res;
    }
    println!("{}", dfs(0, N, &mut dp, &span));





}
    
fn main(){
    solve();
}


const PI:f64 = std::f64::consts::PI;
pub static MOD:i64    = 998244353;
pub static MODu:usize = 1000000007;
pub static MODi32:i32 = 1000000007;
pub static eps:f64 = 1e-6;
const INF: i64 = 1 << 60;
const INFu:usize = 1<<56;
const INFu128:u128 = 1<<126;