結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2024-03-15 19:28:15 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 116 ms / 5,000 ms |
コード長 | 4,098 bytes |
コンパイル時間 | 13,724 ms |
コンパイル使用メモリ | 378,356 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-12 13:12:56 |
合計ジャッジ時間 | 14,358 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
use crate::cmpmore::CmpMore;fn main() {let n = io::input::<usize>();let mut vt = (0..n).map(|_| io::input::<(usize, usize)>()).collect::<Vec<_>>();vt.sort_by_key(|&(v, t)| v + t);let tmax = vt.iter().map(|&(_, t)| t).sum::<usize>();let mut dp = vec![false; tmax];dp[0] = true;let mut ans = 0;for &(v, t) in &vt {for i in (0..t).rev() {if dp[i] {ans.change_max(i + v);if i + v < tmax {dp[i + v] = true;}}}}println!("{}", ans);}// io {{{// https://ngtkana.github.io/ac-adapter-rs/io/index.html#[allow(dead_code)]mod io {use std::cell::Cell;use std::io::stdin;use std::io::BufRead;use std::io::BufReader;use std::io::Lines;use std::io::Stdin;use std::sync::Mutex;use std::sync::Once;pub fn input<T: ParseLine>() -> T {ParseLine::parse_line(&line())}pub trait ParseLine {fn parse_line(s: &str) -> Self;}macro_rules! impl_parse_line {($($t:ty),*) => {$(impl ParseLine for $t {fn parse_line(s: &str) -> Self {s.parse().unwrap()}})*};}impl_parse_line!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, String, char);macro_rules! impl_parse_line_tuple {($($t:ident),*) => {impl<$($t: ParseLine),*> ParseLine for ($($t,)*) {fn parse_line(s: &str) -> Self {let mut s = s.split_whitespace();($($t::parse_line(s.next().unwrap()),)*)}}};}impl_parse_line_tuple!(T0, T1);impl_parse_line_tuple!(T0, T1, T2);impl_parse_line_tuple!(T0, T1, T2, T3);impl_parse_line_tuple!(T0, T1, T2, T3, T4);impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5);impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6);impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7);impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8);impl_parse_line_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9);impl<T: ParseLine> ParseLine for Vec<T> {fn parse_line(s: &str) -> Self {s.split_whitespace().map(T::parse_line).collect()}}static ONCE: Once = Once::new();type Server = Mutex<Lines<BufReader<Stdin>>>;struct Lazy(Cell<Option<Server>>);unsafe impl Sync for Lazy {}fn line() -> String {static SYNCER: Lazy = Lazy(Cell::new(None));ONCE.call_once(|| {SYNCER.0.set(Some(Mutex::new(BufReader::new(stdin()).lines())));});unsafe {(*SYNCER.0.as_ptr()).as_ref().unwrap().lock().unwrap().next().unwrap().unwrap()}}}// }}}// cmpmore {{{// https://ngtkana.github.io/ac-adapter-rs/cmpmore/index.html#[allow(dead_code)]mod cmpmore {pub fn change_min<T: PartialOrd>(lhs: &mut T, rhs: T) {if *lhs > rhs {*lhs = rhs;}}pub fn change_max<T: PartialOrd>(lhs: &mut T, rhs: T) {if *lhs < rhs {*lhs = rhs;}}#[macro_export]macro_rules! change_min {($lhs:expr, $rhs:expr) => {let rhs = $rhs;let lhs = $lhs;$crate::cmpmore::change_min(lhs, rhs);};}#[macro_export]macro_rules! change_max {($lhs:expr, $rhs:expr) => {let rhs = $rhs;let lhs = $lhs;$crate::cmpmore::change_max(lhs, rhs);};}pub trait CmpMore: PartialOrd + Sized {fn change_min(&mut self, rhs: Self) {change_min(self, rhs)}fn change_max(&mut self, rhs: Self) {change_max(self, rhs)}}impl<T: PartialOrd + Sized> CmpMore for T {}}// }}}