#1148988 (Rust) No.527 ナップサック容量問題

• 問題: No.527 ナップサック容量問題
• ユーザー: elphe
• 提出日時: 2026-02-21 17:20:30
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 9 ms / 2,000 ms
• コード長: 8,028 bytes
• コンパイル時間: 1,009 ms
• コンパイル使用メモリ: 207,424 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-02-21 17:20:34
• 合計ジャッジ時間: 3,136 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 37

ソースコード

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    unsafe {
        read!(stdin -> (n: u8, items: Vec[(u16, u16); n], v: u32));
        write!(output(solve(items, v)));
    }
}

fn solve(items: Vec<(u16, u16)>, v: u32) -> (u32, Option<u32>) {
    let mut dp = [0; 100_002];
    items.into_iter().for_each(|(v, w)| {
        ((w as usize)..dp.len()).rev().for_each(|i| {
            dp[i] = dp[i].max(dp[i - w as usize] + v as u32);
        })
    });

    match mylib::upper_bound(&dp, &v) {
        100_002 => (mylib::lower_bound(&dp, &v).max(1) as u32, None),
        ans => (
            mylib::lower_bound(&dp, &v).max(1) as u32,
            Some((ans - 1) as u32),
        ),
    }
}

fn output((ans_l, ans_r): (u32, Option<u32>)) -> String {
    ans_l.to_string()
        + "\n"
        + &match ans_r {
            Some(ans) => ans.to_string(),
            None => String::from("inf"),
        }
}

mod mylib {
    pub fn lower_bound<T: PartialOrd>(v: &[T], border: &T) -> usize {
        if v.is_empty() || v[0] >= *border {
            return 0;
        }
        let mut l: usize = 0;
        let mut r: usize = v.len();
        while l + 1 < r {
            let c = (l + r) / 2;
            if v[c] < *border {
                l = c;
            } else {
                r = c;
            }
        }
        r
    }

    pub fn upper_bound<T: PartialOrd>(v: &[T], border: &T) -> usize {
        if v.is_empty() || v[0] > *border {
            return 0;
        }
        let mut l: usize = 0;
        let mut r: usize = v.len();
        while l + 1 < r {
            let c = (l + r) / 2;
            if v[c] <= *border {
                l = c;
            } else {
                r = c;
            }
        }
        r
    }
}

#[macro_export]
macro_rules! read {
    ($iter:ident -> ($v:ident : $t:tt)) => {
        let $v = read_value!($iter -> $t);
    };

    ($iter:ident -> ($v:ident : $t1:tt$t2:tt)) => {
        let $v = read_value!($iter -> $t1$t2);
    };

    ($iter:ident -> ($v:ident : $t:tt, $($r:tt)*)) => {
        read!($iter -> ($v : $t));
        read!($iter -> ($($r)*));
    };

    ($iter:ident -> ($v:ident : $t1:tt$t2:tt, $($r:tt)*)) => {
        read!($iter -> ($v : $t1$t2));
        read!($iter -> ($($r)*));
    };
}

#[macro_export]
macro_rules! read_value {
    ($source:ident -> ($($t:tt),*)) => {
        ( $(read_value!($source -> $t)),* )
    };

    ($source:ident -> [ $t:tt ; $len:expr ]) => {
        {
            let mut x: [::std::mem::MaybeUninit<$t>; $len] = unsafe { ::std::mem::MaybeUninit::uninit().assume_init() };
            for elem in x.iter_mut() {
                unsafe {
                    elem.as_mut_ptr().write(read_value!($source -> $t));
                }
            }
            unsafe {
                ::std::mem::transmute::<[::std::mem::MaybeUninit<$t>; $len], [$t; $len]>(x)
            }
        }
    };

    ($source:ident -> [ $c2:tt [ $t:tt $(; $len2:expr)? ] ; $len1:expr ]) => {
        {
            let mut x: [::std::mem::MaybeUninit<$c2<$t>>; $len1] = unsafe { ::std::mem::MaybeUninit::uninit().assume_init() };
            for elem in x.iter_mut() {
                unsafe {
                    elem.as_mut_ptr().write(read_value!($source -> $c2 [ $t $(; $len2)? ]));
                }
            }
            unsafe {
                ::std::mem::transmute::<[::std::mem::MaybeUninit<$c2<$t>>; $len1], [$c2<$t>; $len1]>(x)
            }
        }
    };

    ($source:ident -> $c:tt[ $t:tt ; $len:expr ]) => {
        (0..($len)).map(|_| read_value!($source -> $t)).collect::<$c<$t>>()
    };

    ($source:ident -> $c:tt[ $t:tt ]) => {
        read_value!($source -> $c[$t ; read_value!($source -> u32)])
    };

    ($source:ident -> $c1:tt[ $c2:tt [$t:tt $(; $len2:expr)?] ; $len1:expr ]) => {
        (0..($len1)).map(|_| read_value!($source -> $c2 [ $t $(; $len2)? ])).collect::<$c1<$c2<$t>>>()
    };

    ($source:ident -> $c1:tt[ $c2:tt [$t:tt $(; $len2:expr)?] ]) => {
        (0..(read_value!($source -> u32))).map(|_| read_value!($source -> $c2 [ $t $(; $len2)? ])).collect::<$c1<$c2<$t>>>()
    };

    ($source:ident -> $t:ty) => {
        my_parser::parse_without_checking::<$t>(($source).next().unwrap())
    };
}

mod my_parser {
    #[allow(unused)]
    pub unsafe fn parse_without_checking<F: std::str::FromStr + Parsable>(target: &str) -> F {
        unsafe { Parsable::from_str(target) }
    }

    pub trait Parsable {
        unsafe fn from_str(s: &str) -> Self;
    }

    impl Parsable for String {
        unsafe fn from_str(s: &str) -> Self {
            Self::from(s)
        }
    }

    impl Parsable for char {
        unsafe fn from_str(s: &str) -> Self {
            s.chars().next().unwrap()
        }
    }

    macro_rules! parse_uint {
        ($s:ident) => {
            $s.bytes().fold(0, |acc, x| acc * 10 + (x - b'0') as Self)
        };
    }

    macro_rules! parse_int {
        ($s:ident) => {{
            let mut iter = $s.bytes().peekable();
            let rev_sign = match iter.peek().unwrap() {
                b'-' => {
                    iter.next();
                    1
                }
                b'+' => {
                    iter.next();
                    -1
                }
                _ => -1,
            };
            iter.fold(0, |acc, x| acc * 10 - (x - b'0') as Self) * rev_sign
        }};
    }

    macro_rules! parse_float {
        ($s:ident) => {{
            let mut iter = $s.bytes().peekable();
            let sign = match iter.peek().unwrap() {
                b'-' => {
                    iter.next();
                    -1.0
                }
                b'+' => {
                    iter.next();
                    1.0
                }
                _ => 1.0,
            };

            let mut result = 0.0;
            while let Some(cur) = iter.next() {
                if cur == b'.' {
                    break;
                }
                result = result * 10.0 + (cur - b'0') as Self;
            }
            let mut digit = 1.0;
            (result
                + iter
                    .map(|cur| {
                        digit *= 0.1;
                        digit * (cur - b'0') as Self
                    })
                    .sum::<Self>())
                * sign
        }};
    }

    impl Parsable for u8 {
        unsafe fn from_str(s: &str) -> Self {
            parse_uint!(s)
        }
    }

    impl Parsable for u16 {
        unsafe fn from_str(s: &str) -> Self {
            parse_uint!(s)
        }
    }

    impl Parsable for u32 {
        unsafe fn from_str(s: &str) -> Self {
            parse_uint!(s)
        }
    }

    impl Parsable for u64 {
        unsafe fn from_str(s: &str) -> Self {
            parse_uint!(s)
        }
    }

    impl Parsable for u128 {
        unsafe fn from_str(s: &str) -> Self {
            parse_uint!(s)
        }
    }

    impl Parsable for i8 {
        unsafe fn from_str(s: &str) -> Self {
            parse_int!(s)
        }
    }

    impl Parsable for i16 {
        unsafe fn from_str(s: &str) -> Self {
            parse_int!(s)
        }
    }

    impl Parsable for i32 {
        unsafe fn from_str(s: &str) -> Self {
            parse_int!(s)
        }
    }

    impl Parsable for i64 {
        unsafe fn from_str(s: &str) -> Self {
            parse_int!(s)
        }
    }

    impl Parsable for i128 {
        unsafe fn from_str(s: &str) -> Self {
            parse_int!(s)
        }
    }

    impl Parsable for f32 {
        unsafe fn from_str(s: &str) -> Self {
            parse_float!(s)
        }
    }

    impl Parsable for f64 {
        unsafe fn from_str(s: &str) -> Self {
            parse_float!(s)
        }
    }
}

#[macro_export]
macro_rules! write {
    ($out:expr) => {{
        use std::io::Write;
        std::io::stdout()
            .lock()
            .write_all(($out).as_bytes())
            .unwrap();
    }};
}