結果

問題 No.54 Happy Hallowe'en
ユーザー ngtkanangtkana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 {}
}
// }}}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0