#827641 (Rust) No.2139 K Consecutive Sushi

• 問題: No.2139 K Consecutive Sushi
• ユーザー: 👑 zeronosu77108
• 提出日時: 2022-12-22 15:58:35
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 58 ms / 2,000 ms
• コード長: 5,756 bytes
• コンパイル時間: 2,966 ms
• コンパイル使用メモリ: 148,308 KB
• 実行使用メモリ: 15,692 KB
• 最終ジャッジ日時: 2023-08-11 11:16:30
• 合計ジャッジ時間: 7,990 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	54 ms; 14,952 KB
testcase_04	AC	58 ms; 14,948 KB
testcase_05	AC	56 ms; 15,692 KB
testcase_06	AC	52 ms; 14,952 KB
testcase_07	AC	56 ms; 14,936 KB
testcase_08	AC	47 ms; 15,592 KB
testcase_09	AC	50 ms; 14,972 KB
testcase_10	AC	53 ms; 14,944 KB
testcase_11	AC	53 ms; 14,972 KB
testcase_12	AC	45 ms; 14,860 KB
testcase_13	AC	1 ms; 4,380 KB
testcase_14	AC	1 ms; 4,380 KB
testcase_15	AC	1 ms; 4,376 KB
testcase_16	AC	1 ms; 4,376 KB
testcase_17	AC	1 ms; 4,376 KB
testcase_18	AC	2 ms; 4,376 KB
testcase_19	AC	1 ms; 4,380 KB
testcase_20	AC	1 ms; 4,376 KB
testcase_21	AC	1 ms; 4,376 KB
testcase_22	AC	1 ms; 4,384 KB
testcase_23	AC	6 ms; 4,380 KB
testcase_24	AC	19 ms; 6,460 KB
testcase_25	AC	38 ms; 11,248 KB
testcase_26	AC	6 ms; 4,380 KB
testcase_27	AC	16 ms; 5,860 KB
testcase_28	AC	16 ms; 5,908 KB
testcase_29	AC	8 ms; 4,376 KB
testcase_30	AC	20 ms; 6,892 KB
testcase_31	AC	50 ms; 14,640 KB
testcase_32	AC	8 ms; 4,376 KB

ソースコード

fn main() {
    let mut sc = Scanner::new();
    let n = sc.usize();
    let k = sc.usize();
    let a = sc.vec::<usize>(n);

    def_monoid!(M, usize, std::usize::MAX, |a:&usize,b:&usize| *a.min(b));
    let mut dp = SegmentTree::<M>::new(n + 1);
    dp.set(0, 0);

    for (i, &a) in a.iter().enumerate() {
        dp.set(i+1, dp.fold((i+1).saturating_sub(k)..=i) + a);
    }

    let ans = a.iter().sum::<usize>() - dp.fold(n-k+1..);
    println!("{}", ans);
}

struct Scanner { s : std::collections::VecDeque<String> } #[allow(unused)] impl Scanner { fn new() -> Self { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); Self { s : s.split_whitespace().map(|s| s.to_string()).collect() } } fn reload(&mut self) -> () { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); self.s = s.split_whitespace().map(|s| s.to_string()).collect(); } fn usize(&mut self) -> usize { self.input() } fn usize1(&mut self) -> usize { self.input::<usize>() - 1 } fn isize(&mut self) -> isize { self.input() } fn i32(&mut self) -> i32 { self.input() } fn i64(&mut self) -> i64 { self.input() } fn i128(&mut self) -> i128 { self.input() } fn u8(&mut self) -> u8 { self.input() } fn u32(&mut self) -> u32 { self.input() } fn u64(&mut self) -> u64 { self.input() } fn u128(&mut self) -> u128 { self.input() } fn edge(&mut self) -> (usize, usize) { (self.usize1(), self.usize1()) } fn edges(&mut self, m : usize) -> Vec<(usize, usize)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.edge()); } e } fn wedge<T:std::str::FromStr>(&mut self) -> (usize, usize, T) { (self.usize1(), self.usize1(), self.input()) } fn wedges<T:std::str::FromStr>(&mut self, m : usize) -> Vec<(usize, usize, T)> { let mut e = Vec::with_capacity(m); for _ in 0..m { e.push(self.wedge()); } e } fn input<T>(&mut self) -> T where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } if let Some(head) = self.s.pop_front() { head.parse::<T>().ok().unwrap() } else { panic!() } } fn tuple<T, U>(&mut self) -> (T, U) where T: std::str::FromStr, U: std::str::FromStr { (self.input(), self.input()) } fn vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr { if self.s.is_empty() { self.reload(); } self.s.drain(..n).map(|s| s.parse::<T>().ok().unwrap() ).collect::<Vec<T>>() } fn nvec<T>(&mut self) -> Vec<T> where T: std::str::FromStr { let n : usize = self.input(); self.vec(n) } fn chars(&mut self) -> Vec<char> { let s : String = self.input(); s.chars().collect() } fn bytes(&mut self) -> Vec<u8> { let s : String = self.input(); s.bytes().collect() } }

#[macro_export]
macro_rules! def_monoid { ($m:ident, $t:ty, $id:expr, $op:expr) => { pub struct $m; impl Monoid for $m { type Type = $t; fn identity() -> Self::Type { $id } fn operator(x:&Self::Type, y:&Self::Type) -> Self::Type {$op(x, y) } }}; }
pub trait Monoid { type Type: Copy + Clone + std::fmt::Debug; fn identity() -> Self::Type; fn operator(a: &Self::Type, b: &Self::Type) -> Self::Type; }
struct SegmentTree<T : Monoid> { n : usize, seg: Vec<T::Type>, }
#[allow(unused)]
impl<T: Monoid> SegmentTree<T> {
    pub fn new(n : usize) -> Self { SegmentTree {n, seg:vec![T::identity(); 2*n + 1]} }
    pub fn from(s : &[T::Type]) -> Self {
        let n = s.len();
        let mut seg = vec![T::identity(); 2*n+1];
        for (i, &si) in s.iter().enumerate() { seg[i+n] = si; }
        for i in (1..n).rev() { seg[i] = T::operator(&seg[2*i], &seg[2*i+1]); }
        SegmentTree {n,seg}
    }

    pub fn set(&mut self, i:usize, x:T::Type) {
        let mut index = i + self.n;
        self.seg[index] = x;
        while index > 0 {
            index /= 2;
            self.seg[index] = T::operator(&self.seg[2*index], &self.seg[2*index+1]);
        }
    }

    fn _fold(&self, mut l:usize, mut r:usize) -> T::Type {
        let mut left = T::identity();
        let mut right = T::identity();
        while l < r {
            if l%2 == 1 { left = T::operator(&self.seg[l], &left); l+=1; }
            if r%2 == 1 { r-=1; right = T::operator(&right, &self.seg[r]); }
            l/=2; r/=2;
        }
        T::operator(&left, &right)
    }

    pub fn fold<R:std::ops::RangeBounds<usize>>(&self, range: R) -> T::Type {
        let l = self.n + match range.start_bound() {
            std::ops::Bound::Unbounded => 0,
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let r = self.n + match range.end_bound() {
            std::ops::Bound::Unbounded => self.n,
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };
        self._fold(l, r)
    }

    pub fn get(&self, index:usize) -> T::Type { self.seg[index + self.n].clone() }

    fn _first_left<F: Fn(&T::Type)->bool>(&self, mut l:usize, r:usize, f : F) -> Option<usize> {
        if !f(&self.fold(l..r)) { return None; }
        l += self.n;
        loop {
            if f(&self.seg[l]) {
                if l >= self.n { return Some(l - self.n); }
                l *= 2;
            } else {
                if l%2 == 0 { l += 1; }
                else { l = l/2 + 1; }
            }
        }
    }

    pub fn first_left<R: std::ops::RangeBounds<usize>, F: Fn(&T::Type)->bool>(&self, range : R, f : F) -> Option<usize> {
        let l = match range.start_bound() {
            std::ops::Bound::Unbounded => 0,
            std::ops::Bound::Included(&l) => l,
            _ => unreachable!()
        };
        let r = match range.end_bound() {
            std::ops::Bound::Unbounded => self.n,
            std::ops::Bound::Included(&x) => x + 1,
            std::ops::Bound::Excluded(&x) => x,
        };
        self._first_left(l, r, f)
    }
}