結果
| 問題 | No.1037 exhausted |
| ユーザー |
 くれちー
|
| 提出日時 | 2020-04-24 23:27:19 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 147 ms / 2,000 ms |
| コード長 | 8,488 bytes |
| コンパイル時間 | 12,800 ms |
| コンパイル使用メモリ | 403,744 KB |
| 実行使用メモリ | 64,768 KB |
| 最終ジャッジ日時 | 2024-10-15 03:51:28 |
| 合計ジャッジ時間 | 14,881 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 |
ソースコード
// The main code is at the very bottom.#[allow(unused_imports)]use {lib::byte::ByteChar,std::cell::{Cell, RefCell},std::cmp::{self,Ordering::{self, *},Reverse,},std::collections::*,std::convert::identity,std::fmt::{self, Debug, Display, Formatter},std::io::prelude::*,std::iter::{self, FromIterator},std::marker::PhantomData,std::mem,std::num::Wrapping,std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},std::process,std::rc::Rc,std::thread,std::time::{Duration, Instant},std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},};#[allow(unused_imports)]#[macro_use]pub mod lib {pub mod byte {pub use self::byte_char::*;mod byte_char {use std::error::Error;use std::fmt::{self, Debug, Display, Formatter};use std::str::FromStr;#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]#[repr(transparent)]pub struct ByteChar(pub u8);impl Debug for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "b'{}'", self.0 as char)}}impl Display for ByteChar {fn fmt(&self, f: &mut Formatter) -> fmt::Result {write!(f, "{}", self.0 as char)}}impl FromStr for ByteChar {type Err = ParseByteCharError;fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {match s.as_bytes().len() {1 => Ok(ByteChar(s.as_bytes()[0])),0 => Err(ParseByteCharErrorKind::EmptyStr.into()),_ => Err(ParseByteCharErrorKind::TooManyBytes.into()),}}}#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]pub struct ParseByteCharError {kind: ParseByteCharErrorKind,}impl Display for ParseByteCharError {fn fmt(&self, f: &mut Formatter) -> fmt::Result {f.write_str(match self.kind {ParseByteCharErrorKind::EmptyStr => "empty string",ParseByteCharErrorKind::TooManyBytes => "too many bytes",})}}impl Error for ParseByteCharError {}#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]enum ParseByteCharErrorKind {EmptyStr,TooManyBytes,}impl From<ParseByteCharErrorKind> for ParseByteCharError {fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {ParseByteCharError { kind }}}}}pub mod io {pub use self::scanner::*;mod scanner {use std::io::{self, BufRead};use std::iter;use std::str::FromStr;#[derive(Debug)]pub struct Scanner<R> {reader: R,buf: String,pos: usize,}impl<R: BufRead> Scanner<R> {pub fn new(reader: R) -> Self {Scanner {reader: reader,buf: String::new(),pos: 0,}}pub fn next(&mut self) -> io::Result<&str> {let start = loop {match self.rest().find(|c| c != ' ') {Some(i) => break i,None => self.fill_buf()?,}};self.pos += start;let len = self.rest().find(' ').unwrap_or(self.rest().len());let s = &self.buf[self.pos..][..len]; // self.rest()[..len]self.pos += len;Ok(s)}pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>whereT: FromStr,{Ok(self.next()?.parse())}pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>whereT: FromStr,{iter::repeat_with(|| self.parse_next()).take(n).collect()}pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>whereF: FnMut(u8) -> T,{Ok(self.next()?.bytes().map(&mut f).collect())}pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>whereF: FnMut(u8) -> T,{iter::repeat_with(|| self.map_next_bytes(&mut f)).take(n).collect()}fn rest(&self) -> &str {&self.buf[self.pos..]}fn fill_buf(&mut self) -> io::Result<()> {self.buf.clear();self.pos = 0;let read = self.reader.read_line(&mut self.buf)?;if read == 0 {return Err(io::ErrorKind::UnexpectedEof.into());}if *self.buf.as_bytes().last().unwrap() == b'\n' {self.buf.pop();}Ok(())}}}}}const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(128);const INTERACTIVE: bool = false;fn main() -> std::io::Result<()> {match CUSTOM_STACK_SIZE_MIB {Some(stack_size_mib) => std::thread::Builder::new().name("run_solver".to_owned()).stack_size(stack_size_mib * 1024 * 1024).spawn(run_solver)?.join().unwrap(),None => run_solver(),}}fn run_solver() -> std::io::Result<()> {let stdin = std::io::stdin();let reader = stdin.lock();let stdout = std::io::stdout();let writer = stdout.lock();macro_rules! with_wrapper {($($wrapper:expr)?) => {{let mut writer = $($wrapper)?(writer);solve(reader, &mut writer)?;writer.flush()}};}if cfg!(debug_assertions) {with_wrapper!()} else if INTERACTIVE {with_wrapper!(std::io::LineWriter::new)} else {with_wrapper!(std::io::BufWriter::new)}}fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>whereR: BufRead,W: Write,{let mut _scanner = lib::io::Scanner::new(reader);#[allow(unused_macros)]macro_rules! scan {($T:ty) => {_scanner.parse_next::<$T>()?.unwrap()};($($T:ty),+) => {($(scan!($T)),+)};($T:ty; $n:expr) => {_scanner.parse_next_n::<$T>($n)?.unwrap()};($($T:ty),+; $n:expr) => {iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) }).take($n).collect::<std::io::Result<Vec<_>>>()?};}#[allow(unused_macros)]macro_rules! scan_bytes_map {($f:expr) => {_scanner.map_next_bytes($f)?};($f:expr; $n:expr) => {_scanner.map_next_bytes_n($n, $f)?};}#[allow(unused_macros)]macro_rules! print {($($arg:tt)*) => {write!(writer, $($arg)*)?};}#[allow(unused_macros)]macro_rules! println {($($arg:tt)*) => {writeln!(writer, $($arg)*)?};}#[allow(unused_macros)]macro_rules! eprint {($($arg:tt)*) => {if cfg!(debug_assertions) {std::eprint!($($arg)*)}};}#[allow(unused_macros)]macro_rules! eprintln {($($arg:tt)*) => {if cfg!(debug_assertions) {std::eprintln!($($arg)*)}};}#[allow(unused_macros)]macro_rules! dbg {($($arg:tt)*) => {if cfg!(debug_assertions) {std::dbg!($($arg)*)} else {($($arg)*)}};}{let (n, max_v, l) = scan!(usize, i64, u64);let s = scan!(u64, i64, u64; n);fn dp(memo: &mut Vec<Vec<Option<Option<u64>>>>,s: &[(u64, i64, u64)],max_v: i64,l: u64,i: usize,mut v: i64,) -> Option<u64> {let crt_x = s.get(i).map(|s| s.0).unwrap_or(l);let prv_x = if i == 0 {0} else {s.get(i - 1).map(|s| s.0).unwrap_or(0)};let d = crt_x - prv_x;v -= d as i64;if v < 0 {return None;}if let Some(ans) = memo[i][v as usize] {return ans;}if i == s.len() {return Some(0);}let ans = match (dp(memo, s, max_v, l, i + 1, v),dp(memo, s, max_v, l, i + 1, cmp::min(max_v, v + s[i].1)).map(|a| a + s[i].2),) {(Some(a), Some(b)) => Some(cmp::min(a, b)),(Some(a), None) | (None, Some(a)) => Some(a),(None, None) => None,};memo[i][v as usize] = Some(ans);ans}let mut memo = vec![vec![None; (max_v + 1) as usize]; n + 1];match dp(&mut memo, &s, max_v, l, 0, max_v) {Some(ans) => println!("{}", ans),None => println!("-1"),}}Ok(())}