結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:00:48 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 4,871 bytes |
コンパイル時間 | 11,815 ms |
コンパイル使用メモリ | 387,504 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-15 02:50:21 |
合計ジャッジ時間 | 13,189 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
// ---------- begin Foldable Deque ----------struct FoldableDeque<T, F> {front: Vec<(T, T)>,back: Vec<(T, T)>,op: F,}#[allow(dead_code)]impl<T, F> FoldableDeque<T, F>where T: Clone,F: Fn(&T, &T) -> T,{fn new(op: F) -> Self {FoldableDeque {front: Vec::new(),back: Vec::new(),op: op,}}fn find(&self) -> Option<T> {match (self.front.last(), self.back.last()) {(Some(a), Some(b)) => Some((self.op)(&a.1, &b.1)),(Some(a), None) => Some(a.1.clone()),(None, Some(b)) => Some(b.1.clone()),(None, None) => None,}}fn clear(&mut self) {self.front.clear();self.back.clear();}fn len(&self) -> usize {self.front.len() + self.back.len()}fn push_back(&mut self, val: T) {let sum = if let Some(p) = self.back.last() {(self.op)(&p.1, &val)} else {val.clone()};self.back.push((val, sum));}fn push_front(&mut self, val: T) {let sum = if let Some(p) = self.front.last() {(self.op)(&val, &p.1)} else {val.clone()};self.front.push((val, sum));}fn pop_front(&mut self) -> Option<T> {if self.len() == 0 {return None;}if self.front.is_empty() {let a = self.back.clone();let m = (self.back.len() + 1) / 2;self.back.clear();let (f, b) = a.split_at(m);for v in f.iter().rev() {self.push_front(v.0.clone());}for v in b.iter() {self.push_back(v.0.clone());}}self.front.pop().map(|p| p.0)}fn pop_back(&mut self) -> Option<T> {if self.len() == 0 {return None;}if self.back.is_empty() {let a = self.front.clone();let m = self.front.len() / 2;self.front.clear();let (f, b) = a.split_at(m);for v in f.iter().rev() {self.push_front(v.0.clone());}for v in b.iter() {self.push_back(v.0.clone());}}self.back.pop().map(|p| p.0)}}// ---------- end Foldable Deque ----------//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 よりmacro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}//fn run() {input! {n: usize,v: usize,l: usize,p: [(usize, usize, u64); n],}let mut p = p;p.reverse();p.push((0, v, 0));p.reverse();p.push((l, v, 0));for p in p.iter_mut() {p.1 = std::cmp::min(p.1, v);}let inf = 1_000_000_000u64 * 2000 + 1;let mut dp = vec![0; v + 1];for p in p.windows(2) {let d = p[1].0 - p[0].0;if d > v {println!("-1");return;}let mut next = vec![inf; v + 1];for i in d..=v {next[i - d] = dp[i];}let (_, a, w) = p[1];let min = |a: &u64, b: &u64| std::cmp::min(*a, *b);let mut deq = FoldableDeque::new(min);let mut k = v + 1;for i in (a..=v).rev() {while k > 0 && i - (k - 1) <= a {k -= 1;deq.push_back(next[k]);}next[i] = std::cmp::min(next[i], next[i - a] + w);deq.pop_front();}dp = next;}let ans = dp.into_iter().min().unwrap();if ans >= inf {println!("-1");} else {println!("{}", ans);}}fn main() {run();}