結果
| 問題 | No.777 再帰的ケーキ |
| ユーザー |
 ngtkana
|
| 提出日時 | 2023-04-20 13:53:26 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 168 ms / 2,000 ms |
| コード長 | 15,390 bytes |
| コンパイル時間 | 12,973 ms |
| コンパイル使用メモリ | 377,764 KB |
| 実行使用メモリ | 13,792 KB |
| 最終ジャッジ日時 | 2024-10-15 12:14:43 |
| 合計ジャッジ時間 | 15,922 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 33 |
ソースコード
use crate::segtree::Segtree;use segtree::Ops;use slicemore::SliceMore;use std::{cmp::Reverse, convert::TryFrom, io::stdin, iter::repeat_with};fn main() {let stdin = stdin();let mut stdin = stdin.lines().map(Result::unwrap);let n = stdin.next().unwrap().parse::<usize>().unwrap();let mut abc = repeat_with(|| {<[_; 3]>::try_from(stdin.next().unwrap().split_whitespace().map(|x| x.parse::<u64>().unwrap()).collect::<Vec<_>>(),).unwrap()}).take(n).collect::<Vec<_>>();abc.sort_by_key(|&[a, b, _]| (a, Reverse(b)));let mut b_sorted = abc.iter().map(|&[_, b, _]| b).collect::<Vec<_>>();b_sorted.sort();let mut dp = vec![0; n].into_iter().collect::<Segtree<O>>();for &[_, b, c] in &abc {let b = b_sorted.lower_bound(&b);let value = dp[b].max(c + dp.fold(..b));change_max!(&mut *dp.entry(b), value);}let ans = dp.fold(..);println!("{}", ans);}enum O {}impl Ops for O {type Value = u64;fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value {(*lhs).max(*rhs)}fn identity() -> Self::Value {0}}// cmpmore {{{#[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 {}}// }}}// segtree {{{#[allow(dead_code)]mod segtree {use std::{collections::VecDeque,fmt::Debug,iter::{repeat_with, FromIterator},ops::{Bound, Deref, DerefMut, Index, Range, RangeBounds},slice::SliceIndex,};// 演算pub trait Ops {type Value: Debug + Default;fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value;fn identity() -> Self::Value;}// 本体pub struct Segtree<O: Ops> {table: Box<[O::Value]>,}impl<O: Ops> Segtree<O> {pub fn new<I: ExactSizeIterator<Item = O::Value>,T: IntoIterator<Item = O::Value, IntoIter = I>,>(iter: T,) -> Self {let iter = iter.into_iter();let n = iter.len();let mut table = repeat_with(O::Value::default).take(n).collect::<Vec<_>>();table.extend(iter);(1..n).rev().for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1]));let table = table.into_boxed_slice();Self { table }}pub fn is_empty(&self) -> bool {self.table.is_empty()}pub fn len(&self) -> usize {self.table.len() / 2}pub fn fold(&self, range: impl RangeBounds<usize>) -> O::Value {let mut left = O::identity();let mut right = O::identity();let Range { mut start, mut end } = into_slice_range(self.len(), range);if end < start {segtree_index_order_fail(start, end);}if self.len() < end {segtree_end_index_len_fail(end, self.len());}start += self.len();end += self.len();while start != end {if start % 2 == 1 {left = O::op(&left, &self.table[start]);start += 1;}if end % 2 == 1 {end -= 1;right = O::op(&self.table[end], &right);}start /= 2;end /= 2;}O::op(&left, &right)}pub fn max_right(&self,range: impl RangeBounds<usize>,mut pred: impl FnMut(&O::Value) -> bool,) -> usize {let Range { mut start, mut end } = into_slice_range(self.len(), range);if start == end {start} else {start += self.len();end += self.len();let orig_end = end;let mut crr = O::identity();let mut shift = 0;while start != end {if start % 2 == 1 {let nxt = O::op(&crr, &self.table[start]);if !pred(&nxt) {return self.max_right_subtree(crr, start, pred);}crr = nxt;start += 1;}start /= 2;end /= 2;shift += 1;}for p in (0..shift).rev() {let end = (orig_end >> p) - 1;if end % 2 == 0 {let nxt = O::op(&crr, &self.table[end]);if !pred(&nxt) {return self.max_right_subtree(crr, end, pred);}crr = nxt;}}orig_end - self.len()}}fn max_right_subtree(&self,mut crr: O::Value,mut root: usize,mut pred: impl FnMut(&O::Value) -> bool,) -> usize {while root < self.len() {let nxt = O::op(&crr, &self.table[root * 2]);root = if pred(&nxt) {crr = nxt;root * 2 + 1} else {root * 2};}root - self.len()}pub fn max_left(&self,range: impl RangeBounds<usize>,mut pred: impl FnMut(&O::Value) -> bool,) -> usize {let Range { mut start, mut end } = into_slice_range(self.len(), range);if start == end {start} else {start += self.len();end += self.len();let orig_start_m1 = start - 1;let mut crr = O::identity();let mut shift = 0;while start != end {if end % 2 == 1 {end -= 1;let nxt = O::op(&self.table[end], &crr);if !pred(&nxt) {return self.max_left_subtree(crr, end, pred);}crr = nxt;}start = (start + 1) >> 1;end >>= 1;shift += 1;}for p in (0..shift).rev() {let start = (orig_start_m1 >> p) + 1;if start % 2 == 1 {let nxt = O::op(&self.table[start], &crr);if !pred(&nxt) {return self.max_left_subtree(crr, start, pred);}crr = nxt;}}orig_start_m1 + 1 - self.len()}}fn max_left_subtree(&self,mut crr: O::Value,mut root: usize,mut pred: impl FnMut(&O::Value) -> bool,) -> usize {while root < self.len() {let nxt = O::op(&self.table[root * 2 + 1], &crr);root = if pred(&nxt) {crr = nxt;root * 2} else {root * 2 + 1};}root + 1 - self.len()}pub fn entry(&mut self, idx: usize) -> Entry<'_, O> {Entry { idx, seg: self }}pub fn as_slice(&self) -> &[O::Value] {self.as_ref()}pub fn as_slice_mut(&mut self) -> &mut [O::Value] {self.as_mut()}}// 要素アクセスimpl<O: Ops, Idx: SliceIndex<[O::Value], Output = O::Value>> Index<Idx> for Segtree<O> {type Output = O::Value;fn index(&self, index: Idx) -> &Self::Output {&self.as_slice()[index]}}pub struct Entry<'a, O: Ops> {idx: usize,seg: &'a mut Segtree<O>,}impl<'a, O: Ops> Drop for Entry<'a, O> {fn drop(&mut self) {self.idx += self.seg.len();self.idx /= 2;while self.idx != 0 {self.seg.table[self.idx] = O::op(&self.seg.table[2 * self.idx],&self.seg.table[2 * self.idx + 1],);self.idx /= 2;}}}impl<O: Ops> Deref for Entry<'_, O> {type Target = O::Value;fn deref(&self) -> &Self::Target {&self.seg.as_slice()[self.idx]}}impl<O: Ops> DerefMut for Entry<'_, O> {fn deref_mut(&mut self) -> &mut Self::Target {&mut self.seg.as_slice_mut()[self.idx]}}// 変換impl<O: Ops> From<Vec<O::Value>> for Segtree<O> {fn from(v: Vec<O::Value>) -> Self {Self::new(v)}}impl<O: Ops> FromIterator<O::Value> for Segtree<O> {fn from_iter<T: IntoIterator<Item = O::Value>>(iter: T) -> Self {let mut v = iter.into_iter().collect::<VecDeque<_>>();let n = v.len();let mut table = repeat_with(O::Value::default).take(n).collect::<VecDeque<_>>();table.append(&mut v);(1..n).rev().for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1]));let table = Vec::from(table).into_boxed_slice();Self { table }}}impl<O: Ops> AsRef<[O::Value]> for Segtree<O> {fn as_ref(&self) -> &[O::Value] {&self.table[self.len()..]}}impl<O: Ops> AsMut<[O::Value]> for Segtree<O> {fn as_mut(&mut self) -> &mut [O::Value] {let n = self.len();&mut self.table[n..]}}// フォーマットimpl<O: Ops> Debug for Segtree<O> {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {self.as_slice().fmt(f)}}// プライベート - RangeBounds 関連fn into_slice_range(len: usize, range: impl RangeBounds<usize>) -> Range<usize> {#[allow(clippy::redundant_closure)]let start = match range.start_bound() {Bound::Included(&start) => start,Bound::Excluded(&start) => start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail()),Bound::Unbounded => 0,};#[allow(clippy::redundant_closure)]let end = match range.end_bound() {Bound::Included(&end) => end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail()),Bound::Excluded(&end) => end,Bound::Unbounded => len,};start..end}fn segtree_end_index_len_fail(index: usize, len: usize) -> ! {panic!("range end index {} out of range for segtree of length {}",index, len);}fn segtree_index_order_fail(index: usize, end: usize) -> ! {panic!("segtree index starts at {} but ends at {}", index, end);}fn slice_start_index_overflow_fail() -> ! {panic!("attempted to index slice from after maximum usize");}fn slice_end_index_overflow_fail() -> ! {panic!("attempted to index slice up to maximum usize");}// テスト}// }}}// slicemore {{{#[allow(dead_code)]mod slicemore {use std::cmp::Ordering::{self, Equal, Greater, Less};pub trait SliceMore<T> {fn partition_point<F: FnMut(&T) -> bool>(&self, pred: F) -> usize;fn lower_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize;fn upper_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize;fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize;fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize;fn lower_bound(&self, x: &T) -> usizewhereT: Ord;fn upper_bound(&self, x: &T) -> usizewhereT: Ord;}impl<T> SliceMore<T> for [T] {fn partition_point<F: FnMut(&T) -> bool>(&self, pred: F) -> usize {partition_point(self, pred)}fn lower_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize {lower_bound_by(self, f)}fn upper_bound_by<F: FnMut(&T) -> Ordering>(&self, f: F) -> usize {upper_bound_by(self, f)}fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize {lower_bound_by_key(self, b, f)}fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, b: &B, f: F) -> usize {upper_bound_by_key(self, b, f)}fn lower_bound(&self, x: &T) -> usizewhereT: Ord,{lower_bound(self, x)}fn upper_bound(&self, x: &T) -> usizewhereT: Ord,{upper_bound(self, x)}}pub fn partition_point<T, F: FnMut(&T) -> bool>(slice: &[T], mut pred: F) -> usize {slice.binary_search_by(|x| if pred(x) { Less } else { Greater }).unwrap_err()}pub fn lower_bound_by<T, F: FnMut(&T) -> Ordering>(slice: &[T], mut f: F) -> usize {partition_point(slice, |x| matches!(f(x), Less))}pub fn upper_bound_by<T, F: FnMut(&T) -> Ordering>(slice: &[T], mut f: F) -> usize {partition_point(slice, |x| matches!(f(x), Less | Equal))}pub fn lower_bound_by_key<T, B: Ord, F: FnMut(&T) -> B>(slice: &[T], b: &B, mut f: F) -> usize {lower_bound_by(slice, |x| f(x).cmp(b))}pub fn upper_bound_by_key<T, B: Ord, F: FnMut(&T) -> B>(slice: &[T], b: &B, mut f: F) -> usize {upper_bound_by(slice, |x| f(x).cmp(b))}pub fn lower_bound<T: Ord>(slice: &[T], x: &T) -> usize {lower_bound_by(slice, |p| p.cmp(x))}pub fn upper_bound<T: Ord>(slice: &[T], x: &T) -> usize {upper_bound_by(slice, |p| p.cmp(x))}}// }}}