QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#273073#7878. Matrix Distancesucup-team296#AC ✓219ms51744kbRust23.6kb2023-12-02 21:05:472023-12-02 21:05:48

Judging History

你现在查看的是最新测评结果

  • [2023-12-02 21:05:48]
  • 评测
  • 测评结果:AC
  • 用时:219ms
  • 内存:51744kb
  • [2023-12-02 21:05:47]
  • 提交

answer

pub mod solution {
//{"name":"e","group":"Manual","url":"","interactive":false,"timeLimit":2000,"tests":[{"input":"","output":""},{"input":"","output":""}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"e"}}}

use crate::algo_lib::collections::array_2d::Array2D;
use crate::algo_lib::io::output::output;
use crate::algo_lib::io::task_io_settings::TaskIoType;
use crate::algo_lib::io::task_runner::run_task;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::task_io_settings::TaskIoSettings;
#[allow(unused)]
use crate::dbg;
use crate::out;
use crate::out_line;

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Cell {
    color: i32,
    x: i64,
    y: i64,
}

fn solve_same_c(mut all: Vec<i64>) -> i64 {
    all.sort();
    let mut res = 0;
    let mut sum_x = 0;
    let mut cnt = 0;
    for i in 0..all.len() {
        res += all[i] * cnt - sum_x;
        cnt += 1;
        sum_x += all[i];
    }
    res
}

fn solve(input: &mut Input, _test_case: usize) {
    let n = input.usize();
    let m = input.usize();
    let mut cells = vec![];
    for x in 0..n {
        for y in 0..m {
            let color = input.i32();
            cells.push(Cell {
                color,
                x: x as i64,
                y: y as i64,
            });
        }
    }
    cells.sort();
    let mut res = 0;
    let mut i = 0;
    while i != cells.len() {
        let mut j = i;
        while j != cells.len() && cells[i].color == cells[j].color {
            j += 1;
        }
        let mut all_x = vec![];
        let mut all_y = vec![];
        for k in i..j {
            all_x.push(cells[k].x);
            all_y.push(cells[k].y);
        }
        res += solve_same_c(all_x);
        res += solve_same_c(all_y);
        i = j;
    }
    out_line!(res * 2);
}

pub(crate) fn run(mut input: Input) -> bool {
    solve(&mut input, 1);
    output().flush();
    true
}

#[allow(unused)]
pub fn submit() -> bool {
    let io = TaskIoSettings {
        is_interactive: false,
        input: TaskIoType::Std,
        output: TaskIoType::Std,
    };

    run_task(io, run)
}

}
pub mod algo_lib {
pub mod collections {
pub mod array_2d {
use crate::algo_lib::io::output::Output;
use crate::algo_lib::io::output::Writable;
use crate::algo_lib::misc::num_traits::Number;
use std::io::Write;
use std::ops::Index;
use std::ops::IndexMut;
use std::ops::Mul;

// TODO: implement good Debug
#[derive(Clone, Debug)]
pub struct Array2D<T> {
    rows: usize,
    cols: usize,
    v: Vec<T>,
}

pub struct Iter<'a, T> {
    array: &'a Array2D<T>,
    row: usize,
    col: usize,
}

impl<T> Array2D<T>
where
    T: Clone,
{
    #[allow(unused)]
    pub fn new(empty: T, rows: usize, cols: usize) -> Self {
        Self {
            rows,
            cols,
            v: vec![empty; rows * cols],
        }
    }

    pub fn new_f(rows: usize, cols: usize, mut f: impl FnMut(usize, usize) -> T) -> Self {
        let mut v = Vec::with_capacity(rows * cols);
        for r in 0..rows {
            for c in 0..cols {
                v.push(f(r, c));
            }
        }
        Self { rows, cols, v }
    }

    pub fn rows(&self) -> usize {
        self.rows
    }

    #[allow(clippy::len_without_is_empty)]
    pub fn len(&self) -> usize {
        self.rows()
    }

    pub fn cols(&self) -> usize {
        self.cols
    }

    pub fn swap(&mut self, row1: usize, row2: usize) {
        assert!(row1 < self.rows);
        assert!(row2 < self.rows);
        if row1 != row2 {
            for col in 0..self.cols {
                self.v.swap(row1 * self.cols + col, row2 * self.cols + col);
            }
        }
    }

    pub fn transpose(&self) -> Self {
        Self::new_f(self.cols, self.rows, |r, c| self[c][r].clone())
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            array: self,
            row: 0,
            col: 0,
        }
    }

    pub fn pref_sum(&self) -> Self
    where
        T: Number,
    {
        let mut res = Self::new(T::ZERO, self.rows + 1, self.cols + 1);
        for i in 0..self.rows {
            for j in 0..self.cols {
                let value = self[i][j] + res[i][j + 1] + res[i + 1][j] - res[i][j];
                res[i + 1][j + 1] = value;
            }
        }
        res
    }
}

impl<T> Writable for Array2D<T>
where
    T: Writable,
{
    fn write(&self, output: &mut Output) {
        for r in 0..self.rows {
            self[r].write(output);
            output.write_all(&[b'\n']).unwrap();
        }
    }
}

impl<T> Index<usize> for Array2D<T> {
    type Output = [T];

    fn index(&self, index: usize) -> &Self::Output {
        &self.v[(index) * self.cols..(index + 1) * self.cols]
    }
}

impl<T> IndexMut<usize> for Array2D<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.v[(index) * self.cols..(index + 1) * self.cols]
    }
}

impl<T> Mul for &Array2D<T>
where
    T: Number,
{
    type Output = Array2D<T>;

    fn mul(self, rhs: Self) -> Self::Output {
        let n = self.rows;
        let m = self.cols;
        assert_eq!(m, rhs.rows);
        let k2 = rhs.cols;
        let mut res = Array2D::new(T::ZERO, n, k2);
        for i in 0..n {
            for j in 0..m {
                for k in 0..k2 {
                    res[i][k] += self[i][j] * rhs[j][k];
                }
            }
        }
        res
    }
}

impl<T> Array2D<T>
where
    T: Number,
{
    pub fn pown(&self, pw: usize) -> Self {
        assert_eq!(self.rows, self.cols);
        let n = self.rows;
        if pw == 0 {
            Self::new_f(n, n, |r, c| if r == c { T::ONE } else { T::ZERO })
        } else if pw == 1 {
            self.clone()
        } else {
            let half = self.pown(pw / 2);
            let half2 = &half * &half;
            if pw & 1 == 0 {
                half2
            } else {
                &half2 * self
            }
        }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.col == self.array.cols {
            self.col = 0;
            self.row += 1;
        }
        if self.row >= self.array.rows {
            return None;
        }
        let elem = &self.array[self.row][self.col];
        self.col += 1;
        Some(elem)
    }
}
}
}
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;

pub struct Input {
    input: Box<dyn Read>,
    buf: Vec<u8>,
    at: usize,
    buf_read: usize,
}

macro_rules! read_integer_fun {
    ($t:ident) => {
        #[allow(unused)]
        pub fn $t(&mut self) -> $t {
            self.read_integer()
        }
    };
}

impl Input {
    const DEFAULT_BUF_SIZE: usize = 4096;

    ///
    /// Using with stdin:
    /// ```no_run
    /// use algo_lib::io::input::Input;
    /// let stdin = std::io::stdin();
    /// let input = Input::new(Box::new(stdin));
    /// ```
    ///
    /// For read files use ``new_file`` instead.
    ///
    ///
    pub fn new(input: Box<dyn Read>) -> Self {
        Self {
            input,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            buf_read: 0,
        }
    }

    pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
        let file = std::fs::File::open(&path)
            .unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
        Self::new(Box::new(file))
    }

    pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
        Self {
            input,
            buf: vec![0; buf_size],
            at: 0,
            buf_read: 0,
        }
    }

    pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
        let file = std::fs::File::open(&path)
            .unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
        Self::new_with_size(Box::new(file), buf_size)
    }

    pub fn get(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            let res = self.buf[self.at];
            self.at += 1;
            Some(res)
        } else {
            None
        }
    }

    pub fn peek(&mut self) -> Option<u8> {
        if self.refill_buffer() {
            Some(self.buf[self.at])
        } else {
            None
        }
    }

    pub fn skip_whitespace(&mut self) {
        while let Some(b) = self.peek() {
            if !char::from(b).is_whitespace() {
                return;
            }
            self.get();
        }
    }

    pub fn next_token(&mut self) -> Option<Vec<u8>> {
        self.skip_whitespace();
        let mut res = Vec::new();
        while let Some(c) = self.get() {
            if char::from(c).is_whitespace() {
                break;
            }
            res.push(c);
        }
        if res.is_empty() {
            None
        } else {
            Some(res)
        }
    }

    //noinspection RsSelfConvention
    pub fn is_exhausted(&mut self) -> bool {
        self.peek().is_none()
    }

    pub fn has_more_elements(&mut self) -> bool {
        !self.is_exhausted()
    }

    pub fn read<T: Readable>(&mut self) -> T {
        T::read(self)
    }

    pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
        let mut res = Vec::with_capacity(size);
        for _ in 0usize..size {
            res.push(self.read());
        }
        res
    }

    pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
        let mut res = Vec::with_capacity(size);
        for _ in 0usize..size {
            res.push(self.string());
        }
        res
    }

    pub fn read_line(&mut self) -> String {
        let mut res = String::new();
        while let Some(c) = self.get() {
            if c == b'\n' {
                break;
            }
            if c == b'\r' {
                if self.peek() == Some(b'\n') {
                    self.get();
                }
                break;
            }
            res.push(c.into());
        }
        res
    }

    #[allow(clippy::should_implement_trait)]
    pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
        InputIterator {
            input: self,
            phantom: Default::default(),
        }
    }

    fn read_integer<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let res = self.read_string();
        res.parse::<T>().unwrap()
    }

    fn read_string(&mut self) -> String {
        match self.next_token() {
            None => {
                panic!("Input exhausted");
            }
            Some(res) => unsafe { String::from_utf8_unchecked(res) },
        }
    }

    pub fn string_as_string(&mut self) -> String {
        self.read_string()
    }

    pub fn string(&mut self) -> Vec<u8> {
        self.read_string().into_bytes()
    }

    fn read_char(&mut self) -> char {
        self.skip_whitespace();
        self.get().unwrap().into()
    }

    fn read_float(&mut self) -> f64 {
        self.read_string().parse().unwrap()
    }

    pub fn f64(&mut self) -> f64 {
        self.read_float()
    }

    fn refill_buffer(&mut self) -> bool {
        if self.at == self.buf_read {
            self.at = 0;
            self.buf_read = self.input.read(&mut self.buf).unwrap();
            self.buf_read != 0
        } else {
            true
        }
    }

    read_integer_fun!(i32);
    read_integer_fun!(i64);
    read_integer_fun!(i128);
    read_integer_fun!(u32);
    read_integer_fun!(u64);
    read_integer_fun!(usize);
}

pub trait Readable {
    fn read(input: &mut Input) -> Self;
}

impl Readable for String {
    fn read(input: &mut Input) -> Self {
        input.read_string()
    }
}

impl Readable for char {
    fn read(input: &mut Input) -> Self {
        input.read_char()
    }
}

impl Readable for f64 {
    fn read(input: &mut Input) -> Self {
        input.read_string().parse().unwrap()
    }
}

impl Readable for f32 {
    fn read(input: &mut Input) -> Self {
        input.read_string().parse().unwrap()
    }
}

impl<T: Readable> Readable for Vec<T> {
    fn read(input: &mut Input) -> Self {
        let size = input.read();
        input.vec(size)
    }
}

pub struct InputIterator<T: Readable> {
    input: Input,
    phantom: PhantomData<T>,
}

impl<T: Readable> Iterator for InputIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.input.skip_whitespace();
        self.input.peek().map(|_| self.input.read())
    }
}

macro_rules! read_integer {
    ($t:ident) => {
        impl Readable for $t {
            fn read(input: &mut Input) -> Self {
                input.read_integer()
            }
        }
    };
}

read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;

pub struct Output {
    output: Box<dyn Write>,
    buf: Vec<u8>,
    at: usize,
    auto_flush: bool,
}

impl Output {
    const DEFAULT_BUF_SIZE: usize = 4096;

    pub fn new(output: Box<dyn Write>) -> Self {
        Self {
            output,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            auto_flush: false,
        }
    }

    pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
        Self {
            output,
            buf: vec![0; Self::DEFAULT_BUF_SIZE],
            at: 0,
            auto_flush: true,
        }
    }

    pub fn flush(&mut self) {
        if self.at != 0 {
            self.output.write_all(&self.buf[..self.at]).unwrap();
            self.at = 0;
            self.output.flush().expect("Couldn't flush output");
        }
    }

    pub fn print<T: Writable>(&mut self, s: &T) {
        s.write(self);
    }

    pub fn put(&mut self, b: u8) {
        self.buf[self.at] = b;
        self.at += 1;
        if self.at == self.buf.len() {
            self.flush();
        }
    }

    pub fn maybe_flush(&mut self) {
        if self.auto_flush {
            self.flush();
        }
    }

    pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
        for i in arg {
            i.write(self);
            self.put(b'\n');
        }
    }

    pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
        let mut first = true;
        for e in iter {
            if first {
                first = false;
            } else {
                self.put(b' ');
            }
            e.write(self);
        }
    }

    pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
        let mut first = true;
        for e in iter {
            if first {
                first = false;
            } else {
                self.put(b' ');
            }
            e.write(self);
        }
    }
}

impl Write for Output {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        let mut start = 0usize;
        let mut rem = buf.len();
        while rem > 0 {
            let len = (self.buf.len() - self.at).min(rem);
            self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
            self.at += len;
            if self.at == self.buf.len() {
                self.flush();
            }
            start += len;
            rem -= len;
        }
        if self.auto_flush {
            self.flush();
        }
        Ok(buf.len())
    }

    fn flush(&mut self) -> std::io::Result<()> {
        self.flush();
        Ok(())
    }
}

pub trait Writable {
    fn write(&self, output: &mut Output);
}

impl Writable for &str {
    fn write(&self, output: &mut Output) {
        output.write_all(self.as_bytes()).unwrap();
    }
}

impl Writable for String {
    fn write(&self, output: &mut Output) {
        output.write_all(self.as_bytes()).unwrap();
    }
}

impl Writable for char {
    fn write(&self, output: &mut Output) {
        output.put(*self as u8);
    }
}

impl<T: Writable> Writable for [T] {
    fn write(&self, output: &mut Output) {
        output.print_iter_ref(self.iter());
    }
}

impl<T: Writable> Writable for Vec<T> {
    fn write(&self, output: &mut Output) {
        self[..].write(output);
    }
}

macro_rules! write_to_string {
    ($t:ident) => {
        impl Writable for $t {
            fn write(&self, output: &mut Output) {
                self.to_string().write(output);
            }
        }
    };
}

write_to_string!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);

impl<T: Writable, U: Writable> Writable for (T, U) {
    fn write(&self, output: &mut Output) {
        self.0.write(output);
        output.put(b' ');
        self.1.write(output);
    }
}

impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
    fn write(&self, output: &mut Output) {
        self.0.write(output);
        output.put(b' ');
        self.1.write(output);
        output.put(b' ');
        self.2.write(output);
    }
}

pub static mut OUTPUT: Option<Output> = None;

pub fn set_global_output_to_stdout() {
    unsafe {
        OUTPUT = Some(Output::new(Box::new(std::io::stdout())));
    }
}

pub fn set_global_output_to_file(path: &str) {
    unsafe {
        let out_file =
            std::fs::File::create(path).unwrap_or_else(|_| panic!("Can't create file {}", path));
        OUTPUT = Some(Output::new(Box::new(out_file)));
    }
}

pub fn set_global_output_to_none() {
    unsafe {
        match &mut OUTPUT {
            None => {}
            Some(output) => output.flush(),
        }
        OUTPUT = None;
    }
}

pub fn output() -> &'static mut Output {
    unsafe {
        match &mut OUTPUT {
            None => {
                panic!("Global output wasn't initialized");
            }
            Some(output) => output,
        }
    }
}

#[macro_export]
macro_rules! out {
    ($first: expr $(,$args:expr )*) => {
        output().print(&$first);
        $(output().put(b' ');
        output().print(&$args);
        )*
        output().maybe_flush();
    }
}

#[macro_export]
macro_rules! out_line {
    ($first: expr $(, $args:expr )* ) => {
        {
            out!($first $(,$args)*);
            output().put(b'\n');
            output().maybe_flush();
        }
    };
    () => {
        {
            output().put(b'\n');
            output().maybe_flush();
        }
    };
}
}
pub mod task_io_settings {
pub enum TaskIoType {
    Std,
    File(String),
}

pub struct TaskIoSettings {
    pub is_interactive: bool,
    pub input: TaskIoType,
    pub output: TaskIoType,
}
}
pub mod task_runner {
use std::io::Write;

use super::input::Input;
use super::output::Output;
use super::output::OUTPUT;
use super::task_io_settings::TaskIoSettings;
use super::task_io_settings::TaskIoType;

pub fn run_task<Res>(io: TaskIoSettings, run: impl FnOnce(Input) -> Res) -> Res {
    let output: Box<dyn Write> = match io.output {
        TaskIoType::Std => Box::new(std::io::stdout()),
        TaskIoType::File(file) => {
            let out_file = std::fs::File::create(file).unwrap();
            Box::new(out_file)
        }
    };

    unsafe {
        OUTPUT = Some(Output::new(output));
    }

    let input = match io.input {
        TaskIoType::Std => {
            let sin = std::io::stdin();
            Input::new(Box::new(sin))
        }
        TaskIoType::File(file) => Input::new_file(file),
    };

    run(input)
}
}
}
pub mod misc {
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
    ($first_val:expr, $($val:expr),+ $(,)?) => {
        eprint!("[{}:{}] {} = {:?}",
                    file!(), line!(), stringify!($first_val), &$first_val);
        ($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
        eprintln!();
    };
    ($first_val:expr) => {
        eprintln!("[{}:{}] {} = {:?}",
                    file!(), line!(), stringify!($first_val), &$first_val)
    };
}
}
pub mod num_traits {
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Sub;
use std::ops::SubAssign;

pub trait HasConstants<T> {
    const MAX: T;
    const MIN: T;
    const ZERO: T;
    const ONE: T;
    const TWO: T;
}

pub trait ConvSimple<T> {
    fn from_i32(val: i32) -> T;
    fn to_i32(self) -> i32;
    fn to_f64(self) -> f64;
}

pub trait Signum {
    fn signum(&self) -> i32;
}

pub trait Number:
    Copy
    + Add<Output = Self>
    + AddAssign
    + Sub<Output = Self>
    + SubAssign
    + Mul<Output = Self>
    + MulAssign
    + Div<Output = Self>
    + DivAssign
    + PartialOrd
    + PartialEq
    + HasConstants<Self>
    + Default
    + Debug
    + Sized
    + ConvSimple<Self>
{
}

impl<
        T: Copy
            + Add<Output = Self>
            + AddAssign
            + Sub<Output = Self>
            + SubAssign
            + Mul<Output = Self>
            + MulAssign
            + Div<Output = Self>
            + DivAssign
            + PartialOrd
            + PartialEq
            + HasConstants<Self>
            + Default
            + Debug
            + Sized
            + ConvSimple<Self>,
    > Number for T
{
}

macro_rules! has_constants_impl {
    ($t: ident) => {
        impl HasConstants<$t> for $t {
            // TODO: remove `std` for new rust version..
            const MAX: $t = std::$t::MAX;
            const MIN: $t = std::$t::MIN;
            const ZERO: $t = 0;
            const ONE: $t = 1;
            const TWO: $t = 2;
        }

        impl ConvSimple<$t> for $t {
            fn from_i32(val: i32) -> $t {
                val as $t
            }

            fn to_i32(self) -> i32 {
                self as i32
            }

            fn to_f64(self) -> f64 {
                self as f64
            }
        }
    };
}

has_constants_impl!(i32);
has_constants_impl!(i64);
has_constants_impl!(i128);
has_constants_impl!(u32);
has_constants_impl!(u64);
has_constants_impl!(u128);
has_constants_impl!(usize);
has_constants_impl!(u8);

impl ConvSimple<Self> for f64 {
    fn from_i32(val: i32) -> Self {
        val as f64
    }

    fn to_i32(self) -> i32 {
        self as i32
    }

    fn to_f64(self) -> f64 {
        self
    }
}

impl HasConstants<Self> for f64 {
    const MAX: Self = Self::MAX;
    const MIN: Self = -Self::MAX;
    const ZERO: Self = 0.0;
    const ONE: Self = 1.0;
    const TWO: Self = 2.0;
}

impl<T: Number + Ord> Signum for T {
    fn signum(&self) -> i32 {
        match self.cmp(&T::ZERO) {
            Ordering::Greater => 1,
            Ordering::Less => -1,
            Ordering::Equal => 0,
        }
    }
}
}
}
}
fn main() {
    crate::solution::submit();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 2080kb

input:

2 2
1 1
2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 2072kb

input:

4 4
1 3 2 4
2 1 2 3
1 3 3 2
3 2 1 4

output:

152

result:

ok 1 number(s): "152"

Test #3:

score: 0
Accepted
time: 154ms
memory: 48448kb

input:

1000 1000
227980299 227980299 227980299 227980299 227980299 776958596 227980299 227980299 227980299 227980299 227980299 227980299 227980299 227980299 227980299 227980299 776958596 227980299 227980299 329001637 227980299 227980299 227980299 329001637 227980299 227980299 227980299 227980299 227980299 ...

output:

506784086339644

result:

ok 1 number(s): "506784086339644"

Test #4:

score: 0
Accepted
time: 151ms
memory: 39132kb

input:

1000 1000
701031019 701031019 902550481 515963342 902550481 701031019 902550481 701031019 701031019 701031019 701031019 701031019 701031019 902550481 701031019 701031019 701031019 902550481 701031019 902550481 701031019 902550481 902550481 902550481 902550481 515963342 701031019 701031019 701031019 ...

output:

293351133301656

result:

ok 1 number(s): "293351133301656"

Test #5:

score: 0
Accepted
time: 152ms
memory: 37384kb

input:

1000 1000
584147147 584147147 771066621 584147147 814776600 814776600 584147147 814776600 814776600 814776600 771066621 814776600 814776600 771066621 584147147 814776600 814776600 771066621 814776600 584147147 771066621 584147147 814776600 771066621 814776600 584147147 814776600 584147147 771066621 ...

output:

222221591276684

result:

ok 1 number(s): "222221591276684"

Test #6:

score: 0
Accepted
time: 157ms
memory: 49372kb

input:

1000 1000
451748258 451748258 205399494 451748258 451748258 451748258 451748258 451748258 953934338 451748258 580264463 451748258 451748258 451748258 451748258 588594555 451748258 451748258 451748258 451748258 451748258 451748258 451748258 451748258 451748258 451748258 953934338 451748258 451748258 ...

output:

450794820267988

result:

ok 1 number(s): "450794820267988"

Test #7:

score: 0
Accepted
time: 166ms
memory: 36236kb

input:

1000 1000
548583482 635446288 548583482 635446288 635446288 548583482 548583482 635446288 801198618 548583482 635446288 635446288 548583482 635446288 548583482 548583482 548583482 548583482 635446288 635446288 635446288 635446288 635446288 635446288 548583482 726064808 635446288 801198618 548583482 ...

output:

237272499061426

result:

ok 1 number(s): "237272499061426"

Test #8:

score: 0
Accepted
time: 163ms
memory: 34240kb

input:

1000 1000
596800174 215475167 727165477 215475167 596800174 479596632 596800174 479596632 340778824 596800174 340778824 340778824 596800174 727165477 792552295 215475167 825136342 215475167 15133890 15133890 792552295 215475167 15133890 15133890 215475167 792552295 186221070 596800174 825136342 7925...

output:

66666979915604

result:

ok 1 number(s): "66666979915604"

Test #9:

score: 0
Accepted
time: 167ms
memory: 48772kb

input:

1000 1000
283321818 144879541 144879541 144879541 144879541 144879541 144879541 144879541 351529453 755622562 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 144879541 ...

output:

429192094084416

result:

ok 1 number(s): "429192094084416"

Test #10:

score: 0
Accepted
time: 159ms
memory: 36020kb

input:

1000 1000
161743512 416078170 855756681 889314339 416481165 889314339 855756681 889314339 855756681 889314339 855756681 264524276 855756681 855756681 855756681 889314339 855756681 889314339 889314339 889314339 494796476 889314339 889314339 889314339 889314339 855756681 855756681 855756681 855756681 ...

output:

216113198146626

result:

ok 1 number(s): "216113198146626"

Test #11:

score: 0
Accepted
time: 182ms
memory: 33824kb

input:

1000 1000
111711290 83219409 652958381 160096781 438510184 979014841 96096837 793714095 266288718 28912730 675001370 464693704 642313963 565598413 429830978 233570610 775904524 969001190 158819374 451251731 210397449 83219409 766749559 473545004 517036030 851023554 166176740 96096837 160096781 63151...

output:

6666591233498

result:

ok 1 number(s): "6666591233498"

Test #12:

score: 0
Accepted
time: 165ms
memory: 51744kb

input:

1000 1000
206885994 206885994 206885994 206885994 206885994 206885994 206885994 206885994 206885994 484082914 206885994 737061221 206885994 206885994 206885994 206885994 206885994 206885994 206885994 206885994 206885994 206885994 206885994 885540330 206885994 15312403 206885994 206885994 206885994 2...

output:

426348228198774

result:

ok 1 number(s): "426348228198774"

Test #13:

score: 0
Accepted
time: 164ms
memory: 37180kb

input:

1000 1000
119021511 262340498 119021511 571262579 262340498 119021511 119021511 262340498 262340498 262340498 262340498 262340498 119021511 119021511 119021511 262340498 262340498 262340498 119021511 119021511 16968046 262340498 262340498 119021511 616963806 119021511 119021511 119021511 616963806 2...

output:

213349390292676

result:

ok 1 number(s): "213349390292676"

Test #14:

score: 0
Accepted
time: 199ms
memory: 35204kb

input:

1000 1000
294834416 710159087 71576000 771158418 734800928 519231261 66958341 846593614 842762889 266263223 449970247 393627406 452797162 702159979 103716509 528121669 411977733 41875663 181065802 366920699 973794257 627741675 408432509 319085147 24347426 209592388 529269033 798345726 138118120 1776...

output:

666600092404

result:

ok 1 number(s): "666600092404"

Test #15:

score: 0
Accepted
time: 168ms
memory: 47516kb

input:

1000 1000
774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 991718494 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 774400533 ...

output:

427191601662978

result:

ok 1 number(s): "427191601662978"

Test #16:

score: 0
Accepted
time: 174ms
memory: 36452kb

input:

1000 1000
786051867 749266154 786051867 336663633 786051867 786051867 336663633 786051867 786051867 786051867 336663633 786051867 786051867 800962293 786051867 786051867 786051867 223735788 786051867 336663633 336663633 786051867 148679559 336663633 786051867 336663633 336663633 786051867 73949921 6...

output:

213692206718908

result:

ok 1 number(s): "213692206718908"

Test #17:

score: 0
Accepted
time: 200ms
memory: 35840kb

input:

1000 1000
589040181 665125243 509194312 722650288 704530640 677647760 941069621 844686966 269308659 817746365 703209818 600393306 651385133 624370978 615782335 583567534 607685482 258818547 960735386 920234049 589990452 396294522 54789277 611895702 401553455 423080336 45108579 47104502 265933176 774...

output:

66671759372

result:

ok 1 number(s): "66671759372"

Test #18:

score: 0
Accepted
time: 165ms
memory: 46916kb

input:

1000 1000
340219853 340219853 340219853 439933175 340219853 340219853 340219853 321321381 68352466 340219853 340219853 340219853 340219853 340219853 3205688 340219853 262286151 340219853 340219853 921123028 340219853 340219853 340219853 831324481 740878043 340219853 340219853 340219853 809209277 340...

output:

427237509950002

result:

ok 1 number(s): "427237509950002"

Test #19:

score: 0
Accepted
time: 177ms
memory: 38808kb

input:

1000 1000
312807013 312807013 671631100 312807013 312807013 312807013 671631100 671631100 671631100 671631100 671631100 707041060 312807013 671631100 312807013 671631100 671631100 671631100 312807013 312807013 671631100 671631100 671631100 671631100 312807013 315186901 312807013 312807013 312807013 ...

output:

213105139802108

result:

ok 1 number(s): "213105139802108"

Test #20:

score: 0
Accepted
time: 215ms
memory: 35640kb

input:

1000 1000
968334296 124281306 602304677 823629809 4594569 888524150 464787481 66467938 740368986 98259485 609892270 10390448 306213053 649927667 507023218 743709660 259153419 9610640 278544598 763827885 452113052 834395597 591175799 165403867 53538577 69976033 120747719 800800356 966618685 95535293 ...

output:

6665934902

result:

ok 1 number(s): "6665934902"

Test #21:

score: 0
Accepted
time: 167ms
memory: 47920kb

input:

1000 1000
917320864 917320864 917320864 917320864 917320864 917320864 917320864 917320864 279445549 917320864 917320864 917320864 917320864 917320864 917320864 917320864 917320864 917320864 917320864 168955665 917320864 917320864 67798067 451366625 917320864 917320864 917320864 917320864 917320864 9...

output:

426406609284792

result:

ok 1 number(s): "426406609284792"

Test #22:

score: 0
Accepted
time: 184ms
memory: 36020kb

input:

1000 1000
563910894 248691777 502346207 502346207 563910894 502346207 563910894 124707688 563910894 502346207 563910894 674899337 502346207 563910894 322714828 563910894 880755660 563910894 502346207 563910894 502346207 502346207 563910894 623520096 821743885 563910894 563910894 563910894 563910894 ...

output:

213337139288624

result:

ok 1 number(s): "213337139288624"

Test #23:

score: 0
Accepted
time: 219ms
memory: 34436kb

input:

1000 1000
73364669 160660181 892922167 705497300 862628574 77538387 281208292 899898205 132405130 749782378 940763807 919799196 943173556 657398506 921058988 192689732 309195568 999117035 726766947 8645595 568429846 372621995 976592332 626494982 740333029 234304386 641643560 572521033 682509489 1057...

output:

665074264

result:

ok 1 number(s): "665074264"

Test #24:

score: 0
Accepted
time: 0ms
memory: 2208kb

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Extra Test:

score: 0
Extra Test Passed