Submission #62299779

---

Source Code Expand

use std::cmp::Reverse;
use std::collections::{BTreeSet, BinaryHeap};
#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;

fn main() {
    input!{
        n: usize,
        k: usize,
        mut v: [[i64; n]; 3]
    }
    fn func(a: i64, b:i64, c:i64) -> i64 {
         a*b + b*c + c*a
    }
    for i in 0..3 {
        v[i].sort();
    }

    let mut seen = BTreeSet::new();
    let mut heap = BinaryHeap::new();

    let mut s = func(v[0][n-1],v[1][n-1], v[2][n-1]);

    let mut count = k;
    seen.insert(vec![n-1, n-1, n-1]);
    heap.push((s, vec![n-1, n-1, n-1]));

    while let Some((sum, vec)) = heap.pop() {
        count -= 1;
        if count == 0 {
            println!("{}", sum);
            return;
        }
        let mut new_v = vec;
        for i in 0..3 {
            if new_v[i] != 0 {
                new_v[i] -= 1;
                if seen.insert(new_v.clone()) {
                    heap.push((func(v[0][new_v[0]], v[1][new_v[1]], v[2][new_v[2]]), new_v.clone()));
                }
                new_v[i] += 1;
            }
        }
    }

}

pub trait Debuggable {
    fn debug_string(&self) -> String;
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for Vec<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        use std::iter::repeat;
        if let Some(max_size) = self.iter()
            .enumerate()
            .map(|(i, x)| (format!("{:?}", x).len()).max(format!("{:?}", i).len()))
            .max() {
                let mut idx = String::from("idx |");   
                let mut val = String::from("val |");   
                for (i, xi) in self.iter().enumerate() {
                    idx.push_str(
                        &format!(" {:>w$} |", i, w=max_size)
                    );
                    val.push_str(
                        &format!(" {:>w$} |", xi, w=max_size)
                    );
                }

                format!("{}\n{}\n{}\n", idx, repeat('-').take(idx.len()).join(""), val)
            } else {
                format!("idx | \nval |\n")
            }
    }
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for std::collections::BTreeSet<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!("{{ {} }}", self.iter().join(", "))
    }
}

impl<T, U> Debuggable for std::collections::BTreeMap<T, U> 
where T: std::fmt::Debug + std::fmt::Display, U: std::fmt::Debug + std::fmt::Display
{
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!(
            "{{\n{}\n }}", self.iter()
                .map(|(k, v)| format!("{k} -> {v}, "))
                .join("\n")
        )
    }
}

// lg! マクロの定義
#[macro_export]
macro_rules! lg {
    ($val:expr) => {
        #[cfg(feature = "local")]
        {
            {
                use Debuggable;
                let val = &$val;
                eprintln!(
                    "[{}:{}] {} = \n{}",
                    file!(),
                    line!(),
                    stringify!($val),
                    val.debug_string()
                );
                val
            }
        }
    }
}
    

Submission Info

Compile Error

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

warning: the item `Itertools` is imported redundantly
  --> src/main.rs:55:13
   |
4  | use itertools::Itertools;
   |     -------------------- the item `Itertools` is already imported here
...
55 |         use itertools::Itertools;
   |             ^^^^^^^^^^^^^^^^^^^^

warning: the item `Itertools` is imported redundantly
  --> src/main.rs:81:13
   |
4  | use itertools::Itertools;
   |     -------------------- the item `Itertools` is already imported here
...
81 |         use itertools::Itertools;
   |             ^^^^^^^^^^^^^^^^^^^^

warning: the item `Itertools` is imported redundantly
  --> src/main.rs:90:13
   |
4  | use itertools::Itertools;
   |     -------------------- the item `Itertools` is already imported here
...
90 |         use itertools::Itertools;
   |             ^^^^^^^^^^^^^^^^^^^^

warning: variable does not need to be mutable
  --> src/main.rs:23:9
   |
23 |     let mut s = func(v[0][n-1],v[1][n-1], v[2][n-1]);
   |         ----^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

Judge Result