結果

問題 No.2495 Three Sets
ユーザー 37kt37kt
提出日時 2024-11-25 13:19:14
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 484 ms / 3,000 ms
コード長 5,343 bytes
コンパイル時間 17,230 ms
コンパイル使用メモリ 402,772 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-25 13:21:38
合計ジャッジ時間 21,187 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 1 ms
6,816 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 3 ms
6,816 KB
testcase_12 AC 5 ms
6,820 KB
testcase_13 AC 470 ms
6,816 KB
testcase_14 AC 474 ms
6,816 KB
testcase_15 AC 481 ms
6,820 KB
testcase_16 AC 484 ms
6,816 KB
testcase_17 AC 479 ms
6,820 KB
testcase_18 AC 1 ms
6,820 KB
testcase_19 AC 15 ms
6,816 KB
testcase_20 AC 13 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use chminmax::chmax;
use div::div_ceil;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};

const M: i64 = 3010;

fn main() {
    input! {
        na: usize,
        nb: usize,
        nc: usize,
        mut a: [i64; na],
        mut b: [i64; nb],
        mut c: [i64; nc],
    }
    a.sort_unstable_by_key(|&x| -x);
    b.sort_unstable_by_key(|&x| -x);
    c.sort_unstable_by_key(|&x| -x);

    let mut cnt = vec![0; (M * 2) as usize];
    let mut sum = vec![0; (M * 2) as usize];
    for &x in &a {
        cnt[(x + M) as usize] += 1;
        sum[(x + M) as usize] += x;
    }
    for i in (1..cnt.len()).rev() {
        cnt[i - 1] += cnt[i];
        sum[i - 1] += sum[i];
    }

    let mut cand_b = vec![(0, 0)];
    let mut sum_b = 0;
    for cnt_b in 1..=nb {
        sum_b += b[cnt_b - 1];
        if cnt_b < nb && b[cnt_b - 1] == b[cnt_b] {
            continue;
        }
        cand_b.push((cnt_b, sum_b));
    }

    let mut cand_c = vec![(0, 0)];
    let mut sum_c = 0;
    for cnt_c in 1..=nc {
        sum_c += c[cnt_c - 1];
        if cnt_c < nc && c[cnt_c - 1] == c[cnt_c] {
            continue;
        }
        cand_c.push((cnt_c, sum_c));
    }

    let mut res = 0;
    for &(cnt_b, sum_b) in &cand_b {
        for &(cnt_c, sum_c) in &cand_c {
            if cnt_b == 0 {
                chmax!(res, sum_c * na as i64);
                continue;
            }
            let mut x = div_ceil(-sum_c, cnt_b as i64);
            chmax!(x, -3000);
            let x = (x + M) as usize;
            if x >= cnt.len() {
                continue;
            }
            let cnt_a = cnt[x];
            let sum_a = sum[x];
            chmax!(
                res,
                sum_a * cnt_b as i64 + sum_b * cnt_c as i64 + sum_c * cnt_a as i64,
            );
        }
    }
    println!("{}", res);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `chminmax 0.1.0 (path+████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::chminmax`
///  - `div 0.1.0 (path+█████████████████████████████████████████████)`             published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::div`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod chminmax {pub use crate::__cargo_equip::macros::chminmax::*;#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_min{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::min($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::min($a,$crate::__cargo_equip::crates::chminmax::min!($($rest),+))}};}macro_rules!min{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_min!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_max{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::max($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::max($a,$crate::__cargo_equip::crates::chminmax::max!($($rest),+))}};}macro_rules!max{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_max!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmin{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_min=$crate::__cargo_equip::crates::chminmax::min!($($cmps),+);if$base>cmp_min{$base=cmp_min;true}else{false}}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmin!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmax{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_max=$crate::__cargo_equip::crates::chminmax::max!($($cmps),+);if$base<cmp_max{$base=cmp_max;true}else{false}}};}macro_rules!chmax{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmax!{$($tt)*})}}
        pub mod div {use std::ops::{Add,BitXor,Div,Rem,Sub};pub trait Zero{fn zero()->Self;fn is_zero(&self)->bool;}pub trait One{fn one()->Self;fn is_one(&self)->bool;}macro_rules!impl_zero_one{($($t:ty)*)=>{$(impl$crate::__cargo_equip::crates::div::Zero for$t{fn zero()->Self{0}fn is_zero(&self)->bool{*self==0}}impl$crate::__cargo_equip::crates::div::One for$t{fn one()->Self{1}fn is_one(&self)->bool{*self==1}})*};}impl_zero_one!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);pub fn div_ceil<T>(a:T,b:T)->T where T:Copy+Zero+One+Add<Output=T>+Div<Output=T>+Rem<Output=T>+BitXor<Output=T>+PartialOrd,{let zero=T::zero();let one=T::one();a/b+if a^b>=zero&&a%b!=zero{one}else{zero}}pub fn div_floor<T>(a:T,b:T)->T where T:Copy+Zero+One+Sub<Output=T>+Div<Output=T>+Rem<Output=T>+BitXor<Output=T>+PartialOrd,{let zero=T::zero();let one=T::one();a/b-if a^b<zero&&a%b!=zero{one}else{zero}}}
    }

    pub(crate) mod macros {
        pub mod chminmax {pub use crate::{__cargo_equip_macro_def_chminmax_chmax as chmax,__cargo_equip_macro_def_chminmax_chmin as chmin,__cargo_equip_macro_def_chminmax_max as max,__cargo_equip_macro_def_chminmax_min as min};}
        pub mod div {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod chminmax {}
        pub mod div {}
    }
}
0