結果

問題 No.1715 Dinner 2
ユーザー emakemak
提出日時 2021-10-22 22:12:14
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 4,610 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 189,928 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-24 13:24:34
合計ジャッジ時間 2,987 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 0 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
testcase_10 AC 1 ms
4,348 KB
testcase_11 AC 87 ms
4,348 KB
testcase_12 AC 65 ms
4,348 KB
testcase_13 AC 58 ms
4,348 KB
testcase_14 AC 70 ms
4,348 KB
testcase_15 AC 74 ms
4,348 KB
testcase_16 AC 69 ms
4,348 KB
testcase_17 AC 41 ms
4,348 KB
testcase_18 AC 1 ms
4,348 KB
testcase_19 AC 1 ms
4,348 KB
testcase_20 AC 1 ms
4,348 KB
testcase_21 AC 1 ms
4,348 KB
testcase_22 AC 1 ms
4,348 KB
testcase_23 AC 1 ms
4,348 KB
testcase_24 AC 1 ms
4,348 KB
testcase_25 AC 9 ms
4,348 KB
testcase_26 AC 6 ms
4,348 KB
testcase_27 AC 6 ms
4,348 KB
testcase_28 AC 7 ms
4,348 KB
testcase_29 AC 8 ms
4,348 KB
testcase_30 AC 7 ms
4,348 KB
testcase_31 AC 9 ms
4,348 KB
testcase_32 AC 110 ms
4,348 KB
testcase_33 AC 110 ms
4,348 KB
testcase_34 AC 113 ms
4,348 KB
testcase_35 AC 116 ms
4,348 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros, unused_imports)]
macro_rules! dbg {
    ($($xs:expr),+) => {
        if cfg!(debug_assertions) {
            std::dbg!($($xs),+)
        } else {
            ($($xs),+)
        }
    }
}

fn main() {
    input!{
        n: usize,
        d: usize,
        xs: [(i64, i64); n],
    }

    let mut xs = xs;
    xs.sort();

    let mut ok = -10_000_000_000i64;
    let mut ng = 0;
    while ng - ok > 1 {
        let x = (ok + ng) / 2;

        let mut a = 0;
        let mut j = usize::max_value();
        let mut done = false;
        for m in 0..d {
            let mut b = i64::min_value();
            let mut k = 0;
            for i in 0..n {
                if i == j { continue; }
                let c = a - xs[i].0 + xs[i].1;
                if a - xs[i].0 >= x && c >= b {
                    b = c;
                    k = i;
                }
            }

            if b == i64::min_value() {
                break;
            }

            a = b;
            j = k;
            if m == d-1 {
                done = true;
            }
        }

        if !done {
            ng = x;
        } else {
            ok = x;
        }
    }

    println!("{}", ok);
}

pub mod input {
    use std::{cell::RefCell, io::Read, mem};
    thread_local!(static DONE: RefCell<bool> = RefCell::new(false));

    #[macro_export]
    macro_rules! input{
        (read=$read:expr,$($r:tt)*)=>{
            let mut sc = input::Scanner::new($read);
            input_inner!{sc,$($r)*}
        };
        ($($r:tt)*)=>{
            let mut sc = input::Scanner::default();
            input_inner!{sc,$($r)*}
        };
    }

    #[macro_export]
    macro_rules! input_inner{
        ($sc:expr)=>{};
        ($sc:expr,)=>{};
        ($sc:expr,$var:ident:$t:tt$($r:tt)*)=>{
            let $var=read_value!($sc,$t);
            input_inner!{$sc $($r)*}
        };
    }

    #[macro_export]
    macro_rules! read_value{
        ($sc:expr,($($t:tt),*))=>{($(read_value!($sc,$t)),*)};
        ($sc:expr,[$t:tt;$len:expr])=>{
            (0..$len).map(|_|read_value!($sc,$t)).collect::<Vec<_>>()
        };
        ($sc:expr,[$t:tt])=>{{
            let len = read_value!($sc, usize);
            (0..len).map(|_|read_value!($sc,$t)).collect::<Vec<_>>()
        }};
        ($sc:expr,Chars)=>{read_value!($sc,String).chars().collect::<Vec<char>>()};
        ($sc:expr,Bytes)=>{read_value!($sc,String).bytes().collect::<Vec<u8>>()};
        ($sc:expr,Usize1)=>{read_value!($sc,usize)-1};
        ($sc:expr,$t:ty)=>{$sc.next::<$t>()};
    }
    pub fn buf_stdin() -> Box<dyn FnMut() -> String> {
        Box::new(|| {
            DONE.with(|f| {
                assert!(!*f.borrow(), "Insufficient input");
                *f.borrow_mut() = true;
            });
            let stdin = std::io::stdin();
            let mut s = String::new();
            stdin.lock().read_to_string(&mut s).unwrap();
            s
        })
    }
    pub fn line_stdin() -> Box<dyn FnMut() -> String> {
        Box::new(|| {
            let stdin = std::io::stdin();
            let mut s = String::new();
            stdin.read_line(&mut s).unwrap();
            s
        })
    }
    pub fn file<P: AsRef<std::path::Path>>(path: P) -> Box<dyn FnMut() -> String> {
        let path = path.as_ref().to_owned();
        Box::new(move || {
            DONE.with(|f| {
                assert!(!*f.borrow(), "Insufficient input");
                *f.borrow_mut() = true;
            });
            std::fs::read_to_string(&path).unwrap()
        })
    }
    pub struct Scanner {
        read_fn: Box<dyn FnMut() -> String>,
        s: Box<str>,
        input: std::str::SplitAsciiWhitespace<'static>,
    }
    impl Default for Scanner {
        fn default() -> Self {
            Self::new(if cfg!(debug_assertions) { line_stdin() } else { buf_stdin() })
        }
    }
    impl Scanner {
        pub fn new(read_fn: Box<dyn FnMut() -> String>) -> Self {
            Self {
                read_fn,
                s: "".into(),
                input: "".split_ascii_whitespace(),
            }
        }
        pub fn next<T: std::str::FromStr>(&mut self) -> T
        where
            T::Err: std::fmt::Debug,
        {
            if let Some(v) = self.input.next() {
                v.parse::<T>().expect("Parse error")
            } else {
                self.s = (&mut self.read_fn)().into_boxed_str();
                let s: &'static str = unsafe { mem::transmute(&*self.s) };
                self.input = s.split_ascii_whitespace();
                self.next()
            }
        }
    }
}
0